题解 AT2305 【[AGC010D] Decrementing】

· · 题解

\texttt{Soultion}

考虑什么样的局面是必胜的

容易发现是 k,k,k,k+1,...,k,k 的类型

对唯一的 k+1 项减1之后对面就输了

然而，再思考一步，k 一定等于 1

因为 k>1 时，前一步对手的状态所有数都大于1，只要避免来到该状态即可，随意减一个为 k 的位置即可

故必胜的状态应该是 1,1,2,...,1,1

首先，当序列出现1时，游戏已经结束，奇偶性就能判断

具体判断是有奇个偶元素则先手胜，反之后手胜

其他情况只需考虑偶数元素奇偶性的变化即可

下面提及的奇数指大于1的奇数

若目前有奇个偶数，显然我们是优的，只要保持这奇个偶数，最后就能取得胜利

我们只要选一个偶数减一，所有数的奇偶性不发生改变

对面怎么选都改变不了偶数元素个数的奇偶性，先手必胜

若目前有偶个偶数，我们不优，改变奇偶性的唯一办法就是令2|gcd

若有多个奇数，我们这一轮让一个变成偶数，下一轮对面就能把它成奇数，无法除2，先手必败

唯一的特例是只有一个奇数时，我们这一轮就能至少除2，这也是我们唯一的翻盘机会

考虑做完上面提及的操作，将决策扔给对手

至此，我们所有情况都讨论完了，小结下

  1. 若元素中出现1，判断奇偶性即可
  2. 若有奇个偶元素，先手必胜
  3. 若有偶个偶元素且奇元素数量大于1，后手必胜
  4. 若有偶个偶元素且奇元素数量等于1，操作唯一的奇元素后将先手权交给后手，后手继续判断

由于继续的只有 Case4，在 Case4 中元素至少全部除2

求gcd暴力求会多带一个log

复杂度 O(nlog^2W)

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<48||ch>57){if(ch==45)y=-1;ch=getchar();}
    while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
int gcd(int x,int y){
    while(y){
        x%=y;
        swap(x,y);
    }
    return x;
}
int main(){
//    freopen("AT2305.in","r",stdin);
//    freopen("AT2305.out","w",stdout);
    int n;
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int op=0;
    while(1){
        int c=0,d=0,p;
        bool flag=0;
        for(int i=1;i<=n;i++){
            if(a[i]>1&&(a[i]&1)){c++;p=i;}
            else if(a[i]%2==0)d++;
            if(a[i]==1)flag=1;
        }
        if(flag){
            if(d&1){
                if(!op)puts("First");
                else puts("Second");
            }
            else{
                if(op)puts("First");
                else puts("Second");
            }
            return 0;
        }
        if(d&1){
            if(!op)puts("First");
            else puts("Second");
            return 0;
        }
        if((d%2==0)&&c>1){
            if(!op)puts("Second");
            else puts("First");
            return 0;
        }
        if((d%2==0)&&c==1){
            a[p]--;
            int g=0;
            for(int i=1;i<=n;i++)g=gcd(g,a[i]);
            for(int i=1;i<=n;i++)a[i]/=g;
            op^=1;
        }
    }
    return 0;
}

本题最重要的就是想到考虑偶元素数量的奇偶性，将原本难以下手的除以gcd变成了只要考虑奇偶性的简单问题