HDU 1847 博弈

sg[0]=0;

sg[i]=mex{sg[i-2^(j)]}  (i>=2^j)

mex()为不在此集合的最小非负整数

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
using namespace std;
int main()
{
int sg[];
int n;
int i;
vector <int> nim;
while (scanf("%d",&n)!=EOF)
{
sg[]=;
for (i = ; i <= n; i++)
{
nim.clear();
int tmp=i;
int each=;
while (tmp>=each)
{
nim.push_back(sg[tmp-each]);
each<<=;
}
int x=;
sort(nim.begin(),nim.end());
for (int j=;j<nim.size();j++)
{
if (nim[j]==x)
x++;
else
{
if (nim[j]>x)
break;
}
}
sg[i]=x;
}
if (sg[n]==)
printf("Cici\n");
else
printf("Kiki\n");
}
return ;
}
上一篇:bzoj 2281 [Sdoi2011]黑白棋(博弈+组合计数)


下一篇:【[SDOI2014]数表】