题解：CF1738C Even Number Addicts

_JF_ · 2025-12-03 11:58:32 · 题解

Link

压制，手法，绝境，突破，自我

打农打的。

明显考虑对奇偶分组，然后想到取偶数是不影响结果的奇偶性的，并且我们只关心取的个数而并非具体值。

明显对于先手，是要取 \lceil \frac{n}{2} \rceil 个的。

不妨从结果出发，假设先手在奇数组里面取了 x 个，那么偶数组里面就会取 \lceil \frac{n}{2} \rceil-x 个。

那么我后手显然是要防止先手取到这样的结果的。

思路也比较容易，因为后手要取 \lfloor \frac{n}{2} \rfloor 个，假设奇数组有 a 个数，如果 x+\lfloor \frac{n}{2} \rfloor>a，那明显是不合法的。

对于偶数组进行同样的验证。

如果有一种取法使得先手必胜，那么先手就赢了，如果所有取法先手都必败，那么后手必胜。

到这里其实这个做法已经可以过了。

其实更进一步的，如果要满足这样的结果，我们发现先手一定是在某个组取到 x 个 （或者 \lceil \frac{n}{2} \rceil-x 个），然后再在另外一个组取，这样一定不劣。

如果交替的话显然是给对方机会。

所以就能想到，一定是先手在一个组里面取了 \lceil \frac{a}{2} \rceil 个，然后再在另外一个组取。

故而分类讨论是在奇数组先取还是偶数组取，然后只要能找到一种合法方案就先手必胜。

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define int long long
#define DEBUG cout<<"when can get npy"<<endl;
int n,pre,pre1;
int Get(int x){
    if(x%2==0)  return x/2;
    else    return x/2+1; 
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        pre=pre1=0;
        cin>>n;
        for(int i=1,x;i<=n;i++){
            cin>>x; 
            if(x%2==0)  pre++;
            else pre1++;
        }
        // first get %2=0
        bool f=true;
        if(pre%2==0){
            if(Get(pre1)%2==0)  f=false;
        } 
        else{
            int now=pre1-Get(pre1);
            if(now%2==0)    f=false;
        }
         // first get %2=1
         if(Get(pre1)%2==0){
            f=false;
         } 
         if(!f) cout<<"Alice"<<endl;
         else   cout<<"Bob"<<endl;
    }
    return 0;
}