J. Alice and Bob-1
先看这个题，题意很简单，一个序列中，小A每次拿一个数，小B每次拿一个数,然后各自的得分为取得的数的和的绝对值。问两个人都采取最优策略，谁将获胜？
我们假设A为小A最后取得的数的和B同理，S为总的和，即小A的想法就是(ans=|A|-|B|)足够大，我们适当的代换一下这个式子,即(ans=|A|-|B|=|A|-|S-A|),这个时候可以进行分类讨论来将绝对值去掉。可以得到以下式子：
(f(x) = left{
egin{array}{lr}
2*A-S & : A>=0,S>=A\
S & : A>=0,S<A \
-S & : A<0,S>=A \
-2A+S & :A<0,S<A\
end{array}
ight.)
之后可以根据S>0和S<0的情况再讨论，通过画图可以得出当S<0时，图是不增的，S>0时图是不减的。注意这个图像的含义，其中S是我们(小A和小B)无法控制的量，而他们能控制的就是他们各自的值即(A,B).通过观察A和ans的图像可以得到，当S<0时，小A只要使得自己的A值足够小就行了，所以他每次直接选剩下值最小的即可。而S>0时则相反，选最大的即可。小B与小A相同。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010;
int n,a[N];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
sort(a+1,a+n+1);
ll A=0,B=0;
if(sum>0)
{
int id=0;
for(int i=n;i>=1;--i)
{
if(!id) A+=a[i];
else B+=a[i];
id^=1;
}
}
else
{
int id=0;
for(int i=1;i<=n;++i)
{
if(!id) A+=a[i];
else B+=a[i];
id^=1;
}
}
if(A<0) A=-A;
if(B<0) B=-B;
printf("%lld",A-B);
return 0;
}
K. Alice and Bob-2
在淦这个题之前就需要一些知识做铺垫...
首先我们先了解什么是ICG公平游戏，与有向图游戏，这个可以自己百度。
最后得知有向图游戏的和为所有有向图游戏的异或。即可。这个题由于每个字符串的大小就40，我们直接暴力找每个字符串的SG函数即可。（记忆化+爆搜yyds）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=101;
int T,n,cnt;
char c[N];
map<vector<int>,int>SG;
inline bool check(vector<int>x)//检查是否到末节点。
{
for(int i=0;i<=25;++i) if(x[i]) return false;
return true;
}
inline int find(vector<int>x)
{
++cnt;
if(SG.find(x)!=SG.end()) return SG[x];
if(check(x)) return SG[x]=0;
vector<int>v;
for(int i=0;i<=25;++i)
{
if(x[i])
{
vector<int>y=x;
y[i]--;
sort(y.begin(),y.end());
v.push_back(find(y));
}
}
for(int i=0;i<=25;++i)
{
if(x[i])
{
for(int j=0;j<=25;++j)
{
if(i!=j&&x[j])
{
vector<int>y=x;
y[i]--;y[j]--;
sort(y.begin(),y.end());
v.push_back(find(y));
}
}
}
}
for(int i=0;;++i)
{
bool flag=false;
for(auto zs:v)
{
if(zs==i)
{
flag=true;
break;
}
}
if(!flag) return SG[x]=i;
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
vector<int>vs;
for(int i=1;i<=26;++i) vs.push_back(0);
while(T--)
{
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;++i)
{
scanf("%s",c+1);
for(int j=0;j<26;++j) vs[j]=0;
int num=strlen(c+1);
for(int j=1;j<=num;++j) vs[c[j]-'a']++;
sort(vs.begin(),vs.end());
ans^=find(vs);
}
if(ans>0) puts("Alice");
else puts("Bob");
}
return 0;
}
更新一下，我自己之前的错误的观念。公平游戏的每个子游戏，我们不能仅看当前局面是否必胜就完事了，因为总的游戏的SG函数为各个子游戏的SG函数的异或和，所以我们必须求出每个子游戏的SG函数值才行。
定理：当且仅当当前的SG函数>0,当前游戏必胜，否则必输。