谷歌中國算法比賽解題報告 APAC2016A

Problem A. Googol String

Problem B. gCube

Problem C. gCampus

Problem D. gSnake

1. 這題不要被10的100次方吓到了，其實這題思路很簡單，注意長度上S2=S1*2+1，是以先找到第k個數字屬于S幾，然後倒着找，如果數字在倒着的左串就不改變，在右串就等于左串對應位置的數字改變（0變1,1變0），在中間就等于0. 此題得解

2.這個題其實就是求k個數字的乘積的k次方根，因為有精度要求是以暴力解法精度不達标……，那麼該怎麼做呢，求log

利用log2 函數，可以輕松解出來。。。這裡要注意stl預設的log是以e為底的，别搞錯了

3.這個題，如果想把每兩個節點的最短路徑都求出來是不可能的，主要因為有可能有很多最短路徑，時間相同但路不同，最典型的，考慮一個網格，從左上角到右下角有多少不同的最短路徑？

那麼換個思路，其實對任意兩點，求出最短路徑，用floyd 五行搞定，然後對于每條路，如果所需的時間大于最短路徑所需時間，這條路就要删除，否則不删除。問題得解

注意題目可能會給先給一個 1到2有一條耗時為3的路，再給一個 1到2有一條耗時為4的路，初始化floyd矩陣時要注意取最小值

4.這道題時間來不及（被2017APAC虐的太慘，本打算趕在3周内刷完所有APAC...但我太高估自己了）

如果能通過APAC2017E,我會回來把它補上……（雖然我覺得希望渺茫。。。）

最後 附上代碼

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <hash_map>
#include <hash_set>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <queue>
#include <list>
#include <iomanip>

using namespace std;

#define ll long long


class PA
{
public:
	PA(){}
	ll K;

	int DFS(ll t, ll k)
	{
		ll m = (t - 1) / 2;
		if (m == k) return 0;
		if (m > k) return DFS(m, k);
		if (m < k) return DFS(m, m-(k-m))^1;
	}


	void SingleProcess(ofstream& fout)
	{
		long long t = 0;
		K--;
		while (K >= t)
		{
			t = t * 2 + 1;
		}
		int num=DFS(t, K);
		fout << num;
	}

	void run()
	{
		FILE* fp = freopen("in.txt", "r", stdin);
		ofstream fout("out.txt");
		int Cases = 0;
		scanf("%d", &Cases);
		for (int time = 0; time < Cases; time++)
		{
			scanf("%lld", &K);


			fout << "Case #" << (time + 1) << ": ";
			SingleProcess(fout);
			fout << endl;
			std::cout << time << endl;
		}
		fclose(fp);
		fout.close();
	}
};

class PB
{
public:
	PB(){}
	int M, N;
	vector<int> dimensions;
	vector<vector<int>> queries;

	void SingleProcess(ofstream& fout)
	{
		double len = 1;
		for (int i = 0; i < queries.size(); i++)
		{
			len = 0;
			for (int l = queries[i][0]; l <= queries[i][1]; l++)
			{
				len += log2((double)dimensions[l]);
			}
			len = len / (queries[i][1] - queries[i][0] + 1);

			len = powl(2, len);

			fout << endl << setiosflags(ios::fixed) << setprecision(8) << len;
		}
	}

	void run()
	{
		FILE* fp = freopen("in.txt", "r", stdin);
		ofstream fout("out.txt");
		int Cases = 0;
		scanf("%d", &Cases);
		for (int time = 0; time < Cases; time++)
		{
			scanf("%d %d", &N, &M);
			dimensions.clear();
			dimensions.resize(N, 0);
			queries.clear();
			queries.resize(M, vector<int>(2, 0));

			for (int i = 0; i < N; i++)
			{
				scanf("%d", &dimensions[i]);
			}

			for (int i = 0; i < M; i++)
			{
				scanf("%d %d", &queries[i][0], &queries[i][1]);
			}

			fout << "Case #" << (time + 1) << ": ";
			SingleProcess(fout);
			fout << endl;
			std::cout << time << endl;
		}
		fclose(fp);
		fout.close();
	}
};

class PC
{
public:
	PC(){}
	int M, N;
	vector<bool> efficientRoad;
	vector<vector<int>> roads;
	struct Node
	{
		int val;
		vector<pair<Node*,int>> connects;
		Node(){ val = 0; }
	};

	vector<int> visited;
	vector<Node> offices;
	map<int, map<int, int>> roadNoMap;
	vector<vector<int>> floydMatrix;

	void DFSFindPath(map<int, vector<int>>& paths, int curr)
	{
		map<int, vector<int>>::iterator iter = paths.find(curr);
		if (iter == paths.end()) return;

		for (int i = 0; i < iter->second.size(); i++)
		{
			int roadNo = roadNoMap[iter->first][iter->second[i]];
			efficientRoad[roadNo] = true;
			if (visited[iter->second[i]] == 0)
			{
				visited[iter->second[i]] = 1;
				DFSFindPath(paths, iter->second[i]);
			}
		}
	}


	void Dijkstra(int from, int to)
	{
		map<int, Node*> record;
		visited.clear();
		visited.resize(N, INT_MAX);
		record[0] = &offices[from];
		visited[from] = 0;
		map<int, vector<int>> paths;
		while (!record.empty())
		{
			if (record.begin()->first >= visited[to]) break;

			Node* curr = record.begin()->second;
			record.erase(record.begin());
			for (int i = 0; i < curr->connects.size(); i++)
			{
				pair<Node*, int>& pi = curr->connects[i];
				if (visited[curr->val] + pi.second < visited[pi.first->val])
				{
					visited[pi.first->val] = visited[curr->val] + pi.second;
					record[visited[curr->val] + pi.second] = pi.first;
					paths[pi.first->val].push_back(curr->val);
				}
			}
		}

		visited.clear();
		visited.resize(N, 0);
		DFSFindPath(paths, to);
	}

	void Floyd(ofstream& fout)
	{
		floydMatrix.clear();
		floydMatrix.resize(N, vector<int>(N, 1e9));
		for (int i = 0; i < roads.size(); i++)
		{
			floydMatrix[roads[i][0]][roads[i][1]] = min(roads[i][2], floydMatrix[roads[i][0]][roads[i][1]]); //好陰……
			floydMatrix[roads[i][1]][roads[i][0]] = floydMatrix[roads[i][0]][roads[i][1]];
		}

		for (int i = 0; i < N; i++)
		{
			floydMatrix[i][i] = 0;
		}

		for (int k = 0; k < N; k++)
		{
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < N; j++)
				{
					floydMatrix[i][j] = min(floydMatrix[i][k] + floydMatrix[k][j], floydMatrix[i][j]);
				}
			}
		}

		for (int i = 0; i < roads.size(); i++)
		{
			if (floydMatrix[roads[i][0]][roads[i][1]] < roads[i][2]) fout << "\n" << i;
		}
	}


	void SingleProcess(ofstream& fout)
	{
		Floyd(fout);
	}

	void run()
	{
		FILE* fp = freopen("in.txt", "r", stdin);
		ofstream fout("out.txt");
		int Cases = 0;
		scanf("%d", &Cases);
		for (int time = 0; time < Cases; time++)
		{
			scanf("%d %d", &N, &M);
			roads.clear();
			roads.resize(M, vector<int>(3, 0));
			for (int i = 0; i < M; i++)
			{
				scanf("%d %d %d", &roads[i][0], &roads[i][1], &roads[i][2]);
			}


			fout << "Case #" << (time + 1) << ":";
			SingleProcess(fout);
			fout << endl;
			std::cout << time << endl;
		}
		fclose(fp);
		fout.close();
	}
};

class PD
{
public:
	PD(){}
	int R, C;

	set<pair<int, int>> visited;

	struct snake
	{
		list<pair<int, int>> keyBody;
		int length;
		pair<int, int> headDir;

		snake(){}

		void init(int r, int c)
		{
			keyBody.clear();
			keyBody.push_back(make_pair(r, c));
			length = 1;
			headDir.first = 0;
			headDir.second = 1;
		}

		void moveOneStep(set<pair<int,int>>& visited,int R,int C)
		{
			int nr = keyBody.back().first + headDir.first;
			int nc = keyBody.back().second + headDir.second;
			nr %= R;
			nc %= C;
			if ((nr + nc) % 2 != 0 && visited.find(make_pair(nr, nc)) == visited.end())
			{
				keyBody.back().first = nr;
				keyBody.back().second = nc;
				visited.insert(keyBody.back());
			}
			else
			{
				keyBody.back().first = nr;
				keyBody.back().second = nc;

			}
		}

	};

	void SingleProcess(ofstream& fout)
	{
		
	}

	void run()
	{
		FILE* fp = freopen("in.txt", "r", stdin);
		ofstream fout("out.txt");
		int Cases = 0;
		scanf("%d", &Cases);
		for (int time = 0; time < Cases; time++)
		{
			//scanf("%d %d", &M, &N);


			fout << "Case #" << (time + 1) << ": ";
			SingleProcess(fout);
			fout << endl;
			std::cout << time << endl;
		}
		fclose(fp);
		fout.close();
	}
};





int main()
{
	//PA p;
	//PB p;
	PC p;
	//PD p;
	p.run();
	
	return 0;
}