C. Even Number Addicts

Problem - C - Codeforces

题意是给你一串序列，每个人轮流，如果Alice最后的总和是偶数就赢，不然Alice最后的总和是奇数就输，Bob就赢，问最后谁赢了

博弈论

我感觉博弈论有点难懂，然后专门问了一下大佬。

要分清楚必胜和必输的状态

本题来看

A的本质是想让自己赢，所以她需要偶数

B的本质是想让自己赢，所以他需要A是奇数

对于一个数来说，加上一个偶数对这个数的奇偶性没有任何的影响，加上一个奇数会改变这个数的奇偶性。

所以来分析一下：

如果此时的A选了一个偶数，那B必定也选偶数，因为B想把奇数留下让A选，改变A的奇偶性

如果此时的A选了一个奇数，那B必定也选奇数，因为B想把偶数留下让A选，不改变A的奇偶性

那么此时就好选了，因为奇数和偶数完全可以分开选了

看到别人的思路：

以4个奇数或者偶数为一组

比如以4个奇数为一组，那一组数中的偶数就是n-奇数

①（奇数的数量%4==0） ：先手必胜

不管这里先选偶数还是先选奇数，偶数选完选奇数或者奇数选完选偶数，偶数没啥影响不用在意个数，现在奇数是4的整数倍，那必定分到一半的奇数到A，所以A必胜

②（奇数的数量%4==1）：分类讨论

这里不知道多出来的奇数会分配到A的上面还是B的上面

所以要分类讨论：

1）先手必输：如果n为奇数，此时偶数为偶数个，然后AB刚好可以分配完，所以多出来的奇数分配到A上面，那这种情况A是必输态

2）先手必胜：如果n为偶数，此时偶数为奇数个，B少了一个，正好多余的这一个可以补上

③（奇数的数量%4==2）：先手必输（各分配一个）

④（奇数的数量%4==3）：先手必胜。A正好变成偶数

下面就是代码了，看代码再理解理解：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5005,INF=1e18,mod=1e9+7;
int a[N],b[N];
signed main(){
    //IOS;
    int T;
    //T=1;
    cin>>T;
    while(T--)
    {
		int sum = 0;
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			if(x&1) sum++;
		} 
		if(sum % 4 == 0)
		{
			cout<<"Alice\n";
			continue;
		}
		if(sum % 4 == 1)//看看这个奇数是分配到谁的上面 
		{
			if(n&1) cout<<"Bob\n";
			else cout<<"Alice\n";
			continue;
		}
		if(sum % 4 == 2)
		{
			cout<<"Bob\n";
			continue;
		}
		if(sum % 4 == 3)
		{
			cout<<"Alice\n";
			continue;
		}
    }
    return 0;
} 
/*
博弈论
其实只有奇数才能发挥作用，偶数没有用 
 
*/