题解：P7339 『MdOI R4』Kotori
SheepGod33
·
·
题解
思路
贪心是不行的，具体为啥可以看这个。
然后可以想到分治。
只要给 Shido 找到一个小于等于 a_1 + m 的对手就行。
用函数 cmp(x) 表示 Shido 是否是 1 到 x 的胜者：如果 cmp(x) 为 1，则 x 是是 1 到 x 的胜者；如果 cmp(x) 为 0，则 x 是是 1 到 x 的胜者。\
显然，如果 cmp(x / 2) 为 0，则 cmp(x) 一定为 0。\
如果 cmp(x / 2) 不为 0，就要给 Shido 在 x \div 2 + 1 到 x 之间给 Shido 找一个对手，这个对手尽量得是 Shido 可以打败的，即这个对手的票数要小于等于 a_1 + m。
考虑用一个函数实现这个找对手的功能，用 find(l, r, x) 表示在 l 到 r 之间找到一个小于等于 x 的对手的票数，如果没找着那 find(l, r, x) 的返回值为 -1。\
把 l 到 r 分成两份，用 w1 表示左半部分 cmp 函数的返回值，用 w2 表示右半部分 cmp 函数的返回值。\
如果 w1 和 w2 都不为 -1，就返回大的那一个，因为在 w1 和 w2 都小于等于 x 的情况下，肯定要留下那个更能打的人。\
如果 w1 不为 -1，而 w2 为 -1，就在右半边找小于等于 w1 + m 的值（即 find(mid + 1, r, w1 + m)），代表 w1 能打得过的对手，找着了就两个数中小的一个，如果没找着就返回 -1。\
如果他俩都是 $-1$，就返回 $-1$。
其他细节见代码。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int t, k, m, a[1000010];
int find(int l, int r, int x)
{
if (l == r)
return a[l] <= x ? a[l] : -1;
int mid = l + r >> 1;
int w1 = find(l, mid, x), w2 = find(mid + 1, r, x);
if (w1 != -1 && w2 != -1)
return max(w1, w2);
if (w1 != -1)
w2 = find(mid + 1, r, w1 + m);
else if (w2 != -1)
w1 = find(l, mid, w2 + m);
return min(w1, w2);
}
bool cmp(int x)
{
if (x == 1)
return true;
if (!cmp(x >> 1))
return false;
return find((x >> 1) + 1, x, a[1] + m) != -1;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &k, &m);
for (int i = 1; i <= 1 << k; i++)
scanf("%d", &a[i]);
if (cmp(1 << k))
printf("Kotori\n");
else
printf("Yoshino\n");
}
return 0;
}
```