Category Archives: hihoCoder

hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在玩一个拼图游戏。如下图所示,整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标,你能找出缺失的那块小矩形的顶点坐标吗?

输入

第一行包含一个整数,N。
第二行包含四个整数,(X0, Y0), (X'0, Y'0),代表大矩形左下角和右上角的坐标。
以下N-1行每行包含四个整数,(Xi, Yi), (X'i, Y'i),代表其中一个小矩形的左下角和右上角坐标。
对于30%的数据, 1 <= N <= 1000
对于100%的数据,1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X', Y')代表缺失的那块小矩形的左下角和右上角的坐标。

样例输入
5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5
样例输出
2 1 3 2

一个矩形由N个小矩形拼接而成,现在丢了一个小矩形,怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。
这一题也很有意思,丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数,如果出现偶数次,则这个点所在的矩形是出现过的,否则这个点就是缺失矩形的某个顶点。最后,从缺失的4个顶点中找出左下角坐标和右上角坐标。
完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	map<Point, int> hash;
	int a, b, c, d;
	while (n--) {
		Point left_bottom, right_top;
		scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
		Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
		++hash[left_bottom];
		++hash[right_top];
		++hash[left_top];
		++hash[right_bottom];
	}
	set<Point> ans;
	for (auto p : hash) {
		if (p.second % 2 == 1) {
			ans.insert(p.first);
		}
	}
	a = c = ans.begin()->first;
	b = d = ans.begin()->second;
	for (auto p : ans) {
		a = min(a, p.first);
		b = min(b, p.second);
		c = max(c, p.first);
		d = max(d, p.second);
	}
	printf("%d %d %d %d\n", a, b, c, d);
	return 0;
}

本代码提交AC,用时432MS。

hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

#1551 : 合并子目录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件,例如:
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录:
/hihocoder
/hihocoder/offer22
/hihocoder/offer22/solutions
/hihocoder/challenge30
/hihocoder/challenge30/p1
/game
/game/moba
/game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000)
以下N行每行包含一个字符串,代表一个文件的绝对路径。保证路径从根目录"/"开始,并且文件名和目录名只包含小写字母和数字。
对于80%的数据,N个文件的绝对路径长度之和不超过10000
对于100%的数据,N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。

样例输入
3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
样例输出
8

给定很多个文件的绝对路径,问从这些文件的绝对路径中,我们可以知道其一共有多少个不同文件夹出现过。
常规思路很简单,直接解析每个文件所在的每一级文件夹路径,存到一个set里面,最后返回unordered_set的大小。但是这种方法TLE,看了一下,内存基本也用完了。因为对于100%的数据,路径长度太长了,hash的时间和空间都随之增长。
后来马上想到,路径问题是一层一层的,有可能很多文件的路径前缀都是相同的,那么我们可以构建一个Trie树,每个节点仅是当前文件夹的名称。最后我们统计一下构建好的Trie树的节点个数,就是文件夹的个数。
完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct Node {
	string key_;
	map<string, Node*> children_;
	Node(string key) :key_(key) {};
};
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d\n", &n);
	string line;
	Node* root = new Node("");
	while (n--) {
		getline(cin, line);
		int pre = 0;
		int pos = line.find('//');
		Node* cur = root;
		while (pos != string::npos) {
			if (pos != 0) {
				string tmp = line.substr(pre + 1, pos - pre - 1);
				if (cur->children_[tmp] == NULL) {
					cur->children_[tmp] = new Node(tmp);
				}
				cur = cur->children_[tmp];
			}
			pre = pos;
			pos = line.find('//', pos + 1);
		}
	}
	ll ans = 0;
	queue<Node*> q;
	q.push(root);
	while (!q.empty()) {
		Node* cur = q.front();
		q.pop();
		++ans;
		for (auto it : cur->children_) {
			q.push(it.second);
		}
	}
	printf("%lld\n", ans - 1);
	return 0;
}

本代码提交AC,用时126MS。

hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, ... AN],已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak

输入

第一行包含一个整数N
第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)
对于30%的数据,1 ≤ N ≤ 100
对于80%的数据,1 ≤ N ≤ 1000
对于100%的数据,1 ≤ N ≤ 100000

输出

一个整数表示答案

样例输入
6
1 3 2 1 2 3
样例输出
3

给定一个数组,只包含1,2,3这三个数,问数组中有多少个三元组下标(i,j,k),满足a[i]<a[j]<a[k]。
我一开始的想法是,找出所有1,2,3出现的下标,对于每一个1的下标i,去2的下标数组中找一个lowerbound j,然后用j在3的下标数组中找一个lowerbound k,则3的下标数组中k往后的下标都是符合条件的。这需要两层循环,过了90%的数据,然后TLE了。
后来经过大神点拨,要想得到符合条件的三元组,则2一定要在中间,所以我们可以遍历原数组,对于每一个出现的2,用其左边的1的频数乘以其右边3的频数,就是这个2可以构成的合法三元组的个数。
为了不重复计算,我们可以提前算好每个位置左边和右边1和3的频数,到时候直接用left[1]*right[3]就好了。完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main() {
	//freopen("input.txt", "r", stdin);
	int n = 0;
	scanf("%d", &n);
	vector<int> nums(n, 0);
	map<int, int> left, right;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &nums[i]);
		++right[nums[i]];
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		--right[nums[i]];
		if (nums[i] == 2) {
			ans += left[1] * right[3];
		}
		++left[nums[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时18MS。

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。
小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。
以下 T 行每行一个正整数N。
对于30%的数据,1 ≤ N ≤ 1000
对于80%的数据,1 ≤ N ≤ 100000
对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。
要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		} else {
			ll i = 1, j = 2;
			ll sum = i + j, ans = 0;
			while (true) {
				while (j <= n && sum < n) {
					++j;
					sum += j;
				}
				if (j > n)break;
				while (i < j && sum > n) {
					sum -= i;
					++i;
				}
				if (sum == n) {
					//printf("%d\n", j - i + 1);
					ans = max(ans, j - i + 1);
					break;
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

无奈,提交后TLE,只过了80%的数据。
实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。
后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。
举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。
所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		}
		else {
			ll ans = 1;
			for (ll i = 1; i < n; ++i) {
				ll sum = (1 + i)*i / 2;
				if (sum > n)break;
				ll left = sum - n;
				if (left%i == 0) {
					ans = max(ans, i);
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

本代码提交AC,用时10MS。

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N
以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N
输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。

样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。
简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
	parent[node] = pre;
	graph[node][pre] = 0;
	graph[pre][node] = 0;
	for (int i = 1; i <= n; ++i) {
		if (graph[node][i] == 1) {
			DFS(i, node);
		}
	}
	graph[node][pre] = 1;
	graph[pre][node] = 1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	int a, b;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	DFS(k, 0);
	for (int i = 1; i <= n; ++i)
		printf("%d ", parent[i]);
	return 0;
}

本代码提交AC,用时42MS。

hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

#1519 : 逃离迷宫II

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。
有些格子是小Hi可以经过的,我们用'.'表示;有些格子上有障碍物小Hi不能经过,我们用'#'表示。小Hi的起始位置用'S'表示,他需要到达用'T'表示的格子才能逃离迷宫。
麻烦的是小Hi被坏女巫施了魔法,他只能选择上下左右某一个方向,沿着这个方向一直走,直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界……
小Hi想知道他最少改变几次方向才能逃离这个迷宫。

输入

第一行包含两个整数N和M。  (1 <= N, M <= 500)
以下N行每行M个字符,代表迷宫。

输出

一个整数代表答案。如果小Hi没法逃离迷宫,输出-1。

样例输入
5 5
S.#.T
.....
.....
.....
.....
样例输出
2

给定一个迷宫,S表示起点,T表示终点,#表示障碍物。行走的时候,只能沿着直线走,直到遇到障碍物或者碰壁,问从S到T,最少需要改变多少次方向。
我一开始是用DFS做的,每次朝一个方向DFS下去,但是因为每次DFS时走了一长条直线,所以回溯的时候需要把之前走过的直线复位。代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
void dfs(int sx,int sy, int step) {
	for (int i = 0; i < 4; ++i) {
		int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
		if (ok(newx, newy) && visited[newx][newy] == '0') {
			visited[newx][newy] = '1';
			bool done = false;
			while (ok(newx, newy)) {
				visited[newx][newy] = '1';
				if (newx == endx&&newy == endy) {
					done = true;
					break;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			if (done) {
				ans = min(ans, step);
			}
			else {
				dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
			}
			while (!(newx == sx&&newy == sy)) {
				if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
				newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	visited[startx][starty] = '1';
	dfs(startx, starty, 0);
	if (ans == INT_MAX)printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

本代码提交TLE,很明显会TLE,因为DFS必须把所有方案都走一遍才能得到最小值。
比赛的时候脑子短路,这种搜索问题要求最短XX的肯定用BFS比DFS快呀,因为第一次BFS到的方案肯定就是最优方案呀。只不过这题判断距离用的是转弯次数,以前都是算走过的步数。
对于这题,用BFS也是一样的,BFS的下一个点肯定就是走直线走到无法再走的那个拐角点(cornor)。不过为了防止死循环,要把以前走过的拐角都记录下来,只走那些以前没走过的拐点。
代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
typedef struct P {
	int x, y, step;
	P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;
bool ok(int x, int y) {
	if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
	return false;
}
int id(int x, int y) {
	return x*n + y;
}
int bfs() {
	queue<P> q;
	P p(startx, starty, 0);
	q.push(p);
	while (!q.empty()) {
		p = q.front();
		q.pop();
		points.insert(id(p.x, p.y));
		for (int i = 0; i < dirs.size(); ++i) {
			int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
			while (ok(newx, newy)) {
				if (newx == endx&&newy == endy) {
					return p.step;
				}
				newx = newx + dirs[i][0], newy = newy + dirs[i][1];
			}
			int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
			if (points.find(id(cornorx, cornory)) == points.end()) {
				P tmp(cornorx, cornory, p.step + 1);
				q.push(tmp);
			}
		}
	}
	return -1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c);
		for (int j = 0; j < m; ++j) {
			scanf("%c", &maze[i][j]);
			if (maze[i][j] == 'S') {
				startx = i;
				starty = j;
			}
			else if (maze[i][j] == 'T') {
				endx = i;
				endy = j;
			}
		}
	}
	printf("%d\n", bfs());
	return 0;
}

本代码提交AC,用时718MS。

hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

#1518 : 最大集合

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个1-N的排列A[1], A[2], ... A[N],定义集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... }。
显然对于任意的K=1..N,S[K]都是有限集合。
你能求出其中包含整数最多的S[K]的大小吗?

输入

第一行包含一个整数N。(1 <= N <= 100000)
第二行包含N个两两不同的整数,A[1], A[2], ... A[N]。(1 <= A[i] <= N)

输出

最大的S[K]的大小。

样例输入
7
6 5 1 4 2 7 3
样例输出
4

给定一个1~N的排列A,然后定义关于k的集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... },要求最大的S[K]的大小。
分析一下样例,当k=1时,S[1]={6,7,3,1,6...},循环节是{6,7,3,1},然后又从6开始循环,但是S是集合,所以|S[1]|=4。当k=2时,S[2]={5,2,5...},循环节是{5,2},所以|S[2]|=2。当k=3时,S[3]={1,6,7,3,1...},发现规律了吗,根据集合的无序性,S[3]==S[1]的。
其实这有点像置换群,6开始的循环节中,对于{6,7,3,1}中的任意一个数K,都有S[K]=4。同理对于另一个循环节{2,5}中的任意一个数K,都有S[K]=2。所以其实我们不需要对A中的所有数都求S[K],只需要求出一个循环节之后,其循环内的所有K的S[K]都相等,这样可以节省很多重复计算。
最后从多个不相交的循环中求最大的S[K]即可。
代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
unordered_map<int, int> result;
void solve(vector<int>& A, int start) {
	unordered_set<int> si;
	si.insert(start);
	int last = start;
	while (si.find(A[last]) == si.end()) {
		si.insert(A[last]);
		last = A[last];
	}
	int ans = si.size();
	unordered_set<int>::iterator it = si.begin();
	while (it != si.end()) {
		result[*it] = ans; // 循环内的所有S[K]都相等
		++it;
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	vector<int> A(n + 1, 0);
	for (int i = 1; i <= n; ++i)scanf("%d", &A[i]);
	for (int i = 1; i <= n; ++i) {
		if (result.find(A[i]) == result.end())solve(A, A[i]);
	}
	int ans = 0;
	for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second);
	printf("%d\n", ans);
	return 0;
}

本代码提交AC,用时271MS。

hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

#1504 : 骑士游历

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在8x8的国际象棋棋盘上给定一只骑士(俗称“马”)棋子的位置(R, C),小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。

输入

第一行包含三个整数,N,R和C。
对于40%的数据, 1 <= N <= 1000000
对于100%的数据, 1 <= N <= 1000000000 1 <= R, C <= 8

输出

从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大,你只需要输出答案模1000000007的余数。

样例输入
2 1 1
样例输出
12

在国际象棋上,给定马的起点(R,C),问走N步共有多少种走法。
这题我最开始是用DFS做的,但是只能过一部分数据,对于100%的数据,N最大居然可以达到1000000000,太恐怖了。
后来问了大神,说是用矩阵快速幂来做,恍然大悟。
在我介绍的马尔可夫聚类算法博客中,初始时给定一个图的邻接矩阵A,则B=A^n中B[i][j]表示从i点到j点走n步的方案数。MCL算法为了满足随机游走,还加上了单位矩阵,具体的例子可以看我那篇博客的图。
这个题就是用MCL的方法来做的。国际象棋的棋盘是8*8的,也就是有64个位置,初始时我们可以算到每个点走一步能走到的位置,这样就能得到一个64*64的邻接矩阵A。然后使用快速幂计算B=A^n。最后把起始点(R,C)转换为一个1*64的行向量,左乘B矩阵,得到一个1*64的行向量。这样做的含义就是从(R,C)出发,走n步到达每个点的方案数。把结果行向量的元素累加起来就是总的方案数。
完整代码如下,最后一步时,直接取出幂矩阵的第idx行即可,没必要再构造一个只含一个元素的矩阵,再左乘了。

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
vector<vector<int>> dirs = { { 1,2 },{ 1,-2 },{ 2,1 },{ 2,-1 },{ -2,1 },{ -2,-1 },{ -1,2 },{ -1,-2 } };
const int MAXN = 8;
const LL MOD = 1000000007;
vector<vector<LL>> matrix(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
inline bool ok(const int &x, const int &y) {
	return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
inline int id(const int &x, const int &y) {
	return x*MAXN + y;
}
void init() {
	for (int i = 0; i < MAXN; ++i) {
		for (int j = 0; j < MAXN; ++j) {
			for (int k = 0; k < dirs.size(); ++k) {
				int x = i + dirs[k][0], y = j + dirs[k][1];
				if (ok(x, y))matrix[id(i, j)][id(x, y)] = 1;
			}
		}
	}
}
vector<vector<LL>> multi(const vector<vector<LL>>& mat1, const vector<vector<LL>>& mat2) {
	vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
	for (int i = 0; i < MAXN*MAXN; ++i) {
		for (int j = 0; j < MAXN*MAXN; ++j) {
			for (int k = 0; k < MAXN*MAXN; ++k) {
				ans[i][j] = (ans[i][j] + mat1[i][k] * mat2[k][j]) % MOD;
			}
		}
	}
	return ans;
}
vector<vector<LL>> pow(vector<vector<LL>>& mat, int n) {
	vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
	for (int i = 0; i < MAXN*MAXN; ++i)ans[i][i] = 1; // 单位阵
	while (n != 0) {
		if (n & 1)ans = multi(ans, mat);
		mat = multi(mat, mat);
		n >>= 1;
	}
	return ans;
}
int main() {
	int n, r, c;
	scanf("%d %d %d", &n, &r, &c);
	--r;
	--c;
	init();
	vector<vector<LL>> finalMat = pow(matrix, n);
	int idx = id(r, c);
	// first way:
	long long ans = 0;
	for (int i = 0; i < MAXN*MAXN; ++i)ans = (ans + finalMat[idx][i]) % MOD;
	printf("%lld\n", ans);
	// second way:
	//vector<vector<LL>> one(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
	//one[idx][idx] = 1;
	//one = multi(one, finalMat);
	//long long ans = 0;
	//for (int i = 0; i < MAXN*MAXN; ++i) {
	//	for (int j = 0; j < MAXN*MAXN; ++j) {
	//		ans = (ans + one[i][j]) % MOD;
	//	}
	//}
	//printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时412MS。

hihoCoder 1507-可疑的记录

hihoCoder 1507-可疑的记录

#1507 : 可疑的记录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一棵N个节点的树,编号1-N,其中1号节点是整棵树的根。他把这棵树的N-1条边记录成N-1行,每行2个整数a和b,表示a是b的父节点。
喜欢恶作剧的小Ho在小Hi的记录里加了一行两个整数,于是小Hi不得设法找出这行可疑的记录。具体来说,如果去掉某一行之后,余下N-1行按小Hi的规则(a是b的父节点)恰好能构成一棵N个节点的树,并且满足编号恰好是1-N且1号节点是根,那么被去掉的一行就被视为可疑的。
你能帮小Hi找出所有可疑的记录吗?

输入

第一行包含一个整数N,表示树的节点数目。
以下N行每行两个整数a和b,表示a是b的父节点。
对于30%的数据,1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N
输入保证合法。

输出

输出一行包含若干个从小到大的整数,表示可疑的行号。(行号从1开始)

样例输入
3
1 2
1 3
1 3
样例输出
2 3

有一棵编号从1~N的树,其中根节点为1。这棵树的n-1条边用n-1行x y表示,其中x是y的父亲节点。现在小Ho在其中增加了一行,导致不满足上述性质,要求找出增加的那行。
这一题我用了BFS,DFS等乱七八糟的方法,最终WA。。。看过大神的代码之后,其实这题根本不需要用这些高深的策略,因为只添加了一行,所以用一些简单的规则即可找出。

  1. 首先,如果这一行x,y中y如果出现1,则这一行肯定是有问题的,因为1是根节点,不可能在右边。
  2. 其次,如果出现x==y,也有问题,因为树没有自回路。
  3. 最后,正常的树中除了根节点,每个节点有且仅有一个父亲节点,如果添加了一行,且不满足上面两种情况,则肯定会出现某个点的父亲节点有两个!所以我们只需要找出出现两个父亲节点的节点即可,而且这两个父亲都有可疑。

根据上述三条规则,马上写出代码:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int n, x, y;
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	vector<int> xarry(n + 1, 0), yarry(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d", &xarry[i], &yarry[i]);
	}
	vector<vector<int>> parent(n + 1, vector<int>());
	for (int i = 0; i < n; ++i) {
		if (yarry[i] == 1) { // 根节点不可能在右边
			printf("%d\n", i + 1);
			break;
		}
		if (xarry[i] == yarry[i]) { // 没有自回路
			printf("%d\n", i + 1);
			break;
		}
		parent[yarry[i]].push_back(i + 1);
	}
	for (int i = 1; i <= n; ++i) {
		if (parent[i].size() > 1) {
			printf("%d %d ", parent[i][0], parent[i][1]);
			break; // 因为只添加了一行,所以只可能有一个节点有两个父亲
		}
	}
	return 0;
}

本代码提交AC,用时253MS。

hihoCoder 1508-剑刃风暴

hihoCoder 1508-剑刃风暴

#1508 : 剑刃风暴

时间限制:20000ms
单点时限:2000ms
内存限制:256MB

描述

主宰尤涅若拥有一招非常厉害的招式——剑刃风暴,“无论是战士还是法师,都害怕尤涅若的武士刀剑技”。
现在战场上有N名敌对英雄,他们的位置分别为(Xi, Yi),而剑刃风暴的伤害范围是一个半径为R的圆形,尤涅若可以选择一个坐标作为剑刃风暴的中心,所有处于这个圆形范围内的英雄都会受到剑刃风暴的伤害。
现在尤涅若想要知道,他的剑刃风暴最多可以同时伤害到多少敌对英雄。

输入

第一行为两个整数N和R,分别敌对英雄的数量以及剑刃风暴的半径。
接下来的N行,每行两个整数Xi和Yi,描述一个英雄的坐标。
对于30%的数据,满足1<=N<=10
对于60%的数据,满足1<=N<=100
对于100%的数据,满足1<=N<=2000, 0<=Xi, Yi<=108, 1<=R<=108,可能有两名英雄的坐标是相同的。

输出

输出一行Ans,表示尤涅若的剑刃风暴最多能够伤害到的英雄数量。

样例输入
10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7
样例输出
3

简化题意:给定平面上n个点,和一个半径为r的圆,这个圆可以任意放置,问最多能覆盖多少个点。
这题类似poj1981(单位圆),我是参考这个题解来做的。
暴力方法。最优的圆肯定是能覆盖最多的点,且有些点落在圆周上,导致这个圆只要稍微往旁边移一下,覆盖的点就会减少。所以枚举任意两个点,假设这两个点正好落在最优圆的圆周上,则由此可以确定一个圆心,然后统计所有落在这个圆内的点的个数,并更新最大值。时间复杂度是O(n^3)
有一点需要注意的是两个圆周上的点,如果它们的距离不是刚好等于直径,则能确定两个圆心,但只需算一个就好了。比如有三个点A,B,C确定的最优圆是下图中的实线,如果我们在由两点确定圆心的过程中,始终统一确定“下边”的圆,则虽然A,B确定的圆是虚线的(虽然A,B确定的圆还可以是实线,但根据我们的规定,统一取“下边”的圆),不是最优。但当遍历到A,C点对时,根据规则,这两个点确定的圆是实线的,也就是说,只要根据统一的规则确定圆心,肯定能找到那个最优圆的。

已知两点求圆心的方法请看这篇博客中的GetCenter函数,下图作了一些辅助线帮助理解。关于atan和atan2的区别,请看这篇博客

暴力方法在hiho上TLE,需要寻求更高效的算法。
假设以两个点i,j为圆心画半径为R的圆,如果两个圆相交,则在相交的弧上任意一点画圆,都能覆盖原来的i,j两点。基于这个思想,假设现在固定点i为圆心,R为半径画圆,求出所有以其他点为圆心画的圆和圆i相交的弧,则在相交重叠次数最多的那段弧上的点为圆心画的圆肯定能覆盖最多的点,覆盖的点数就是这段弧被重叠的次数。每个点i都能求出这样一个最大值,则所有点的这个最大值的最大值就是全局能覆盖的最多点。
怎样表示两个圆相交的那段弧呢,使用极坐标,因为弧是由两条半径张成的,所以可以表示成两条半径的极坐标夹角,并且标明夹角的开始(is=1)和结束(is=-1)。求重叠次数最多的弧的方法是,把所有重叠弧的起止半径的极坐标夹角排个序,然后遍历一下,当夹角开始(is=1)次数最多且结束(is=-1)次数最少时,说明重叠次数最多,所以就是is的累加和的最大值。
完整代码借鉴这篇博客,注意原代码是针对R=1的情况,如果是任意的R,则计算角差那里还需除以半径R。完整代码如下:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 2005;
const double PI = acos(-1.0);
//const double R = 1.0;//定义覆盖圆半径为R
int T, n, total, R;
struct Point {
	double x, y;
}point[MAX_N];
struct Angle {
	double data;
	int is;
	bool operator < (const Angle& rhs) const {
		return data<rhs.data;
	}
}angle[MAX_N * 2];
inline double Dis(Point a, Point b)//计算线段ab的长度
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
inline double God(Point a, Point b)//计算向量ab的极角
{
	double res = atan(fabs((b.y - a.y) / (b.x - a.x)));
	if (b.y<a.y) {
		if (b.x<a.x) res += PI;
		else res = 2 * PI - res;
	}
	else {
		if (b.x<a.x) res = PI - res;
	}
	return res;
}
void solve()
{
	int res = 1;
	for (int i = 0; i<n; i++) {
		total = 0;
		for (int j = 0; j<n; j++) {
			if (i == j) continue;
			double dist = Dis(point[i], point[j]);
			if (dist>2.0 * R) continue;
			double base = God(point[i], point[j]);
			double extra = acos((dist / 2.0) / R); //计算差角
			angle[total].data = base - extra; // in
			angle[total++].is = 1;
			angle[total].data = base + extra; // out
			angle[total++].is = -1;
		}
		if (total <= res) continue;
		sort(angle, angle + total);
		int tmp = 1;
		for (int j = 0; j<total; j++) {
			tmp += angle[j].is;
			res = max(res, tmp);
		}
	}
	printf("%d\n", res);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &R);
	for (int i = 0; i<n; i++) {
		scanf("%lf %lf", &point[i].x, &point[i].y);
	}
	solve();
	return 0;
}

本代码提交AC,用时1345MS。
平时几乎没做过计算几何的题目,发现好难呀。