http://codeforces.com/contest/1161

A. Hide and Seek

 

题意：有n个位置，Alice在某个位置放了一个球，Bob猜m次，每次猜之前或之后Alice可以把球换到相邻的位置，但是整个过程最多只能换一次，要Bob一次都猜不对，问有几种初始放球和最终球位置的情况数。

判断每个位置作为初始位置，能不能向左或向右交换，或者不动。

仅当交换之后Bob的序列里没有换完之后的位置才能交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k, a[N], l[N], r[N];
ll ans;
int main() {
	scanf("%d%d", &n, &k);
	memset(l, 0x3f, sizeof(l));
	for (int i = 1; i <= k; i++) {
		scanf("%d", &a[i]);
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = max(r[a[i]], i);
	}
	for (int i = 1; i <= n; i++) {
		if (r[i]) {
			if (i < n&&r[i + 1] < l[i])ans++;
			if (i > 1 && r[i - 1] < l[i])ans++;
		}
		else {
			ans++;
			if (i > 1)ans++;
			if (i < n)ans++;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

B. Chladni Figure

 

题意：有一个圆被n个点均分成n份，点之间有一些连边，问连出的图形是否是旋转对称图形，即旋转完某个角度与原图相同。

对于一个角度，只要判断所有连边的端点旋转后是否仍然连边。

但是枚举所有角度显然超时。

但是旋转对称只要枚举n的因子即可，这个结论已经遇到几次了。

旋转角度a后对称等价于旋转角度gcd(a,n)后对称。

充分性：旋转a相当于整数个gcd(a,n)，所以旋转角度gcd(a,n)后对称   ⟹  \implies 旋转角度a后对称.

必要性：旋转角度n，即360度，一定等于原图，所以可以旋转任意次n。斐蜀定理得xa+yn=gcd(a,n)一定有解，所以一定可以通过旋转n和旋转a这两种操作得到旋转gcd(a,n)，每次旋转操作完都等于原图，那么最终一定也等于原图，即旋转gcd(a,n)也对称。所以旋转角度a后对称   ⟹  \implies 旋转角度gcd(a,n)后对称.

即只要枚举n的因子，每次 O(m)O(m) 检查。复杂度 O(mn)O(m\sqrt n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
typedef pair<int, int>pii;
map<pii, int>mp;
vector<pii>vc;
bool check(int x) {
	for (pii p : vc) {
		int u = p.first, v = p.second;
		if (!mp.count(pii((u + x) % n, (v + x) % n)))return false;
	}
	return true;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--; v--;
		mp[pii(u, v)] = 1;
		mp[pii(v, u)] = 1;
		vc.push_back(pii(u, v));
	}
	for (int i = 1; i < n; i++) {
		if (n%i)continue;
		if (check(i)) { puts("Yes"); return 0; }
	}
	puts("No");
	return 0;
}

 

C. Thanos Nim

 

题意：有n堆石子，两个人轮流操作，每次选n/2堆，从每堆各拿正数个石子，先没法拿得人输，问先手还是后手赢。

博弈

结论：设各堆最少石子数a，则若等于a的堆数大于n/2，先手必败，否则后手必败。

可以发现先拿空至少一堆的人必败。因为另一个人可以拿完n/2堆，而再轮到我时就没法找到n/2堆了。

若等于a的堆数大于n/2，则先手一定会选到至少一堆有最少的石子，这样最少的石子数就一定会减小，后手再把n/2堆拿到剩下新的最少石子数，这样始终保持最少石子数堆数大于n/2，且最少石子数不断减小，最终一定是先手先拿完一堆，则先手败。

若等于a的堆数小于等于n/2，则先手一定可以选择不等于最少石子数的n/2堆拿，拿到剩下最少石子数，使得等于最少石子数的堆数大于n/2，使得后手面临情况1，则后手败。

至于为什么能想到，可能还是和n/2这个特殊的数字有关吧，以及先拿空的人必败这个结论，每次至少拿一个的限制使得最少石子数一定在减小，迫使一方先拿空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], mn = INF, cnt;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &a[i]), mn = min(mn, a[i]);
	for (int i = 0; i < n; i++)if (a[i] == mn)cnt++;
	puts((cnt > n / 2) ? "Bob" : "Alice");
	return 0;
}