https://acm.ecnu.edu.cn/contest/375/

D. 关于小方的爆款桌游还没面世就要夭折这回事

 

题意：n*m的棋盘，n 为偶数，每个棋子 1*2，可以横着或竖着放，无法落子的输，问先手胜负。

博弈

考虑模仿对手。

若 m 为偶数，则后手始终放在与先手中心对称的位置，则后手必胜。

若 m 为奇数，则先手放在最中心处，之后始终模仿后手，则先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m;
int main() {
	scanf("%d%d", &n, &m);
	if (m & 1) {
		puts("Yes");
	}
	else puts("No");
	return 0;
}

 

A. 读不懂古神语的程序员不是一个合格的探险家

 

题意：交互题。给定 n，在环上是数字 11 到 2n2^n 的一个排列，从数字 11 顺时针与逆时针走到 2n2^n 的路径上都是递增的，从某个位置起从 1 开始编号，每次询问返回位置 xx 上的数字，要求不超过 2n+22n+2 次询问确定数字 2n2^n 所在位置。

二分

总共有四种情况：先增再减，先减再增，先增再减再增，先减再增再减。

首先询问 位置 1 和 2，判断 a1,a2a_1,a_2 这一段是增还是减。

再二分。

如果 a1<a2a_1<a_2，则说明 a1,a2a_1,a_2 这一段是增：

若 amid<a1a_{mid}<a_1，则最高点一定在 midmid 左边；

若 amid>a1a_{mid}>a_1，则还要判断若 amid<amid+1a_{mid}<a_{mid+1}，则 amid,amid+1a_{mid},a_{mid+1} 这一段是也增，则最高点一定在 mid+1mid+1 右边，否则一定在 midmid 左边。

如果 a1>a2a_1>a_2 也类似讨论。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int ask(int x) {
	cout << "? " << x << endl;
	int ans;
	cin >> ans;
	if (ans == (1 << n)) {
		cout << "! " << x << endl;
		exit(0);
	}
	return ans;
}
int main() {
	cin >> n;
	int a1 = ask(1), a2 = ask(2);
	int m = (1 << n);
	if (a1 < a2) {
		int L = 3, R = m;
		while (L < R) {
			int mid = (L + R) / 2;
			int a = ask(mid);
			if (a < a1) {
				R = mid - 1;
			}
			else {
				int b = ask(mid + 1);
				if (a < b) {
					L = mid + 2;
				}
				else {
					R = mid - 1;
				}
			}
		}
		cout << "! " << L << endl;
	}
	else {
		int L = 3, R = m;
		while (L < R) {
			int mid = (L + R) / 2;
			int a = ask(mid);
			if (a < a2) {
				L = mid + 1;
			}
			else {
				int b = ask(mid + 1);
				if (a < b) {
					L = mid + 2;
				}
				else {
					R = mid - 1;
				}
			}
		}
		cout << "! " << L << endl;
	}
	return 0;
}

 

C. 不会吧不会吧不会这道题还有同学答案错误吧

 

题意：给定一种树的分治策略：每次选择一条边满足删去后得到的两棵子树点数差最小，删去这条边，递归至两棵子树，若没有边则返回。要求构造一棵树并给出分治方法，使得用你给出的分支方法的最大递归深度小于用题目给定的分治策略的最大递归深度。

构造

如上图构造，一条长链尾部一朵花。

如果只是一条链的话深度必定是 log，但是加上一朵花会使得分割点偏向花，使得另一边的递归深度变大。

1
2
3
4
5
6
7
8
9
10
11
12
13
12
1 12
12 9
12 10
12 11
4 5
2 3
1 2
3 4
6 7
7 8
5 6

 

E. 蟹老板的梦幻传送门真的能让宅男走出家门吗

 

题意：n 个点左边分别为 aia_i，要在两个坐标（不需要是给定点）放一对传送门直接传送，满足距离最远的两个点的距离尽可能短，输出这个距离。

枚举+贪心

发现可以把所有点分成两部分，左部分点要么不用传送门要么一定用左边的传送门，右部分点要么不用传送门要么一定用右边的传送门。

枚举这个分界线，左边的传送门一定设在左部分点的中点处，右部分的传送门一定设在右部分点的中点处。

假设 [1,i][1,i] 的点为左部分，[i+1,n][i+1,n] 的点为右部分。

则左部分最远的两个点为 11 和 ii，距离为 ai−a1a_i-a_1，右部分最远的两个点为 i+1i+1 和 nn，距离为 an−ai+1a_n-a_{i+1}。

一点在左另一点在右的情况中最远的点为 11 和 nn，（ii 和 i+1i+1 或 ii 和 nn 可以通过讨论发现必定不大于 11 和 nn），距离为 ai−a1+an−ai+12\frac{a_i-a_1+a_n-a_{i+1}}{2}，发现这个值小于等于 max⁡(ai−a1,an−ai+1)\max(a_i-a_1,a_n-a_{i+1})。

所以最终结果为 max⁡(ai−a1,an−ai+1)\max(a_i-a_1,a_n-a_{i+1})。

注意先排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int ans = INF;
	for (int i = 1; i < n; i++) {
		ans = min(ans, max(a[i] - a[1], a[n] - a[i + 1]));
	}
	printf("%d\n", ans);
	return 0;
}