[博弈论] P10398 『STA - R5』Remove and Decrease Game

_Cheems · 2024-05-19 17:30:45 · 题解

令 a_1\dots a_n 升序排列。

• * $n=2$ 做法的拓展：不难发现，操作过程可以看成直接挪走 $a_1\dots a_{n-2}$、依次取走 $a_{n-1}$、最后直接挪走 $a_n$。即总步骤是 $a_{n-1}+n-1$，若为奇数先手必胜，称其为“胜方”（反之后手为“胜方”）。 * hack：$a_1=1$ 就能 hack 上述做法，称其为特殊堆。 * 先手为“胜方”：因为 $a_1<a_2\dots <a_n$，因此只要“胜方”优先使用操作二，那么任意局面都不可能出现特殊堆。因此，先手为“胜方”时一定必胜。 * 先手为 “败方”：$a_1=1$ 时先手必然会使用操作一，使得自己逆袭为“胜方”。$a_1>1$ 时先手怎么操作都无法逆袭了。依次类推，不难发现双方会轮流挪走特殊堆实现逆袭，直到特殊堆不存在。具体地，记 $cnt$ 为特殊堆操作次数，则 $2\nmid cnt$ 时先手必胜，反之后手必胜。 * 小细节：$cnt$ 只应该计算 $a_1\dots a_{n-2}$，而不能算 $a_{n-1}$。这是因为挪走 $a_{n-1}$ 后必输无疑。 ### 代码 ```cpp #include<bits/stdc++.h> using namespace std;

const int N = 2e5 + 5; int T, n, a[N];

int main(){ cin >> T; while(T--){ scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a + 1, a + 1 + n); if(n == 1) printf("Alice\n"); else if(n == 2) printf("%s\n", (a[1] & 1) ? "Bob" : "Alice"); else{ int cnt = 0; for(int i = 1; i <= n - 2; ++i) cnt += (a[i] == i); //a[i]=i时可以进行特殊操作。不用break是因为a[i]!=i则后面都不满足条件 if((n - 1 + a[n - 1]) & 1) printf("Alice\n"); else printf("%s\n", (cnt & 1) ? "Alice" : "Bob"); } } return 0; }