题解
想去学习一下博弈论的 SG 函数
不过貌似这道题就是猜结论并且证明
题意是, 随便选择一堆石子, 扔掉至少一个, 然后从扔石子的这堆里选择任意多 (可以不选) 放到其他任意多的未选择完的石堆里
一堆石子, 先手必胜
两堆石子, 如果两堆石子相同, 那么后手必胜, 先手一定会使两堆不同, 那么后手把两堆恢复相同, 最后先手的局面就是(1,1), 此时后手必胜
如果两堆石子不同, 先手必胜, 因为先手让两堆石子相同即可
三堆石子, 先手必胜, 先手也可以让两堆石子相同
四堆石子, 由于三堆必胜, 那么只有局面 1 1 1 1 的时候, 此时后手必胜, 先手不得不扔走一个, 那么猜测一下, 只有偶数堆石子并且石子两两相等可以配对的时候, 后手必胜
然后证明一下这个结论
我们认为, 必败态是, 石子堆为偶数, 且石子堆每一堆可以和另一堆相等的石子堆形成配对的时候, 先手必败
必胜态必胜(即必胜态可以转化到一个必败态)
奇数堆石子时, 先手挑选石子堆最多的那一堆, 扔掉至少一个, 我们将剩下的偶数个数从小到大排序, 差分不会超过石子堆最多的那一堆数量 - 1, 然后我们使剩余石子堆形成必败态, 扔掉多余的石子
偶数堆石子且至少有一个不配对的时候, 删掉配对的部分, 那么剩下的偶数个石堆从小到大排序, 令石子数最多的堆先扔掉一个, 和石子数最少的匹配, 那么我们还可以分配, 最大 - 最小 - 1 个石子, 由于第二大的石堆和第一大的石堆不匹配, 至少相差 1, 那么剩余的石子按照差分可以给剩下的石堆分配石子, 多余的扔掉
必败态必败(即必败态不能走到一个必败态)
扔掉一个石子一定会出现两堆不同
代码
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- //#define ivorysi
- #define MAXN 105
- #define eps 1e-8
- using namespace std;
- typedef long long int64;
- typedef double db;
- int N;
- int a[105];
- void Solve() {
- for(int i = 1 ; i <= N ; ++i) {
- scanf("%d",&a[i]);
- }
- sort(a + 1,a + N + 1);
- if(N & 1) {puts("1");return;}
- for(int i = 1 ; i <= N ; i += 2) {
- if(a[i] != a[i + 1]) {puts("1");return;}
- }
- puts("0");
- }
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- while(scanf("%d",&N) != EOF && N) {
- Solve();
- }
- }
- [POJ] 1740.A New Stone Game
来源: http://www.bubuko.com/infodetail-2601603.html