A - Card Game
题意：两个玩家，每次各出一张卡，每张卡是不同的，然后出分数大的卡的玩家收走两张卡。求最优策略下谁把所有卡拿走。
题解：每次都出最大的那张。
void test_case() {
int n, k1, k2;
scanf("%d%d%d", &n, &k1, &k2);
int max1 = 0, max2 = 0;
for(int i = 1; i <= k1; ++i) {
int a;
scanf("%d", &a);
max1 = max(max1, a);
}
for(int i = 1; i <= k2; ++i) {
int a;
scanf("%d", &a);
max2 = max(max2, a);
}
if(max1 > max2)
puts("YES");
else
puts("NO");
}
B - Interesting Subarray
题意：当一个数组中，出现一个子数组，其中的最大值-最小值>=子数组长度，那么这个数组就是有趣的。问一个数组是不是有趣的。
题解：一开始还搞什么双指针？保留窗口的两端是极值。但是这个算法是错的因为并不一定是极值才能导致数组有趣。正确的做法是判断是不是有一对相邻元素相差>=2。
证明：当有一对相邻元素相差>=2，那么取这一对元素就是答案，充分性得证。
否则，相邻元素的差至多为1，l长度的数组至多向同一个方向改变l-1，不满足题意，必要性得证。
int a[200005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 2; i <= n; ++i) {
if(abs(a[i] - a[i - 1]) >= 2) {
puts("YES");
printf("%d %d
", i - 1, i);
return;
}
}
puts("NO");
}
C - Make Good
题意：给一个序列，往这个序列后加至多3个元素，使得加法和是其异或和的两倍。
题解：异或和……数据结构就分解，构造就先搞个异或和上去。假如某个神秘力量启示我们搞个异或和上去，那么原来的序列就变成：
加法和：某个非负数x
异或和：0
问题变成加至多2个元素，使得加法和是异或和的两倍。
那么就加个x。
其中，上面的步骤可以分开做的原因是加法和异或都满足结合律。
ll a[200005];
void test_case() {
int n;
scanf("%d", &n);
ll sum = 0, xorsum = 0;
for(int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
xorsum ^= a[i];
sum += a[i];
}
ll b[10];
b[1] = xorsum;
sum += xorsum;
b[2] = sum;
printf("2
%lld %lld
", b[1], b[2]);
}
所以这个题还真是1500的，怪不得是手速场。
*D - Strange Device
题意：交互题。有一个装置，其中有 (n) 个不同元素。每次询问恰好 (k(1leq k< n)) 个位置，然后装置会回答这些位置中，第 (m) 小的元素的位置和值，需要使用不超过 (n) 次询问，求出 (m) 的值（回答不算询问）。
题解：大小是无关紧要的，直接离散化。一开始考虑选一个区间平移来询问，事实上不能这么做，但是思路是相似的，用相邻的询问的特征来判断改变的元素与 (m) 的大小关系。选取其中的 (k+1) 个元素，第 (i) 次询问就除了第 (i) 个位置不询问，其他的这些位置都询问，这时若去掉了比 (m) 的元素小的元素或 (m) 本身，例如 (n=6,a=(1,2,3,4,5,6),k=5,m=4,q_1=(2,3,4,5,6),a_1=5,q_2=(1,3,4,5,6),a_2=5,q_3=(1,2,4,5,6),a_3=5,q_4=(1,2,3,5,6),a_3=5) 回答的都是的 (m+1) 。若去掉了比 (m) 大的元素，那么返回的就显然是 (m) 。
那么就统计一下他们出现的次数，注意到，若 (m=1) 则上面会回答1次2,5次1。若 (m=2) 则上面会回答2次3,4次2。依次类推，也就是，大的那个数出现的次数，就是 (m) 。
反思：其实假如不进行想象和形式化很重的推理，说不定能在当时观察到规律。所以还是要沉下心推几个样例。因为这个只告诉询问的第 (m) 大，所以确实从与 (m) 的大小关系入手是自然的。
int x, y;
int cntx, cnty;
void query(int id, int k) {
putchar('?');
for(int i = 1; i <= k + 1; ++i) {
if(i == id)
continue;
putchar(' ');
printf("%d", i);
}
putchar('
');
fflush(stdout);
int p, v;
scanf("%d%d", &p, &v);
if(x == 0 || v == x) {
x = v;
++cntx;
} else {
y = v;
++cnty;
}
}
void test_case() {
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= k + 1; ++i)
query(i, k);
if(x > y) {
swap(x, y);
swap(cntx, cnty);
}
printf("! %d
", cnty);
}