首页 > 代码库 > HDU 1847 博弈
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[10000]; int n; int i; vector <int> nim; while (scanf("%d",&n)!=EOF) { sg[0]=0; for (i = 1; i <= n; i++) { nim.clear(); int tmp=i; int each=1; while (tmp>=each) { nim.push_back(sg[tmp-each]); each<<=1; } int x=0; sort(nim.begin(),nim.end()); for (int j=0;j<nim.size();j++) { if (nim[j]==x) x++; else { if (nim[j]>x) break; } } sg[i]=x; } if (sg[n]==0) printf("Cici\n"); else printf("Kiki\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。