Question

ACM一道简单博弈论题目 解答给高分

假设现在总共n(n<=100)堆石子，每堆石子有Si(Si<=1000)颗石子。两人轮流取石子，规则是每次可以任选第i堆石子取，但是这堆石子的个数需要大于i，而且若取的话只能取走i颗石子。最终无法取石子者败。给定一个局面，并假设博弈两人都使用最优策略，问先手是否有必胜策略。
输入
3
1 2 3
应当输出
YES

Answer 1

#include<stdio.h>
int main()
{
int n,count,i,s;
while(scanf("%d",&n)!=EOF)
{
count=0;//最多取几次，显然count是奇数时先手就赢啦
for(i=1;i<=n;i++)
{
scanf("%d",&s);
count+=(a/i);
}
//printf("%d",count);
if(count%2==1)
printf("YES\n");
else printf("NO\n");//count==0时信息不足，情况怎么样不太确定
}
return 0;
}
//俺也不是很确定算法对不对，错的话勿喷啊，俺也是新手一个

追问

count+=(a/i); a是哪出来的

追答

不好意思，原来是int a的，不过我看你的题是要si的，我怕你看不懂，就把a改掉了，可惜改的不够彻底啊，抱歉啦

Answer 2

赞同楼上，我也用c++写了下。
#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;

void main()
{
int N = 0 , x = 0;

cout << "请输入堆数："<<endl;
cin >> N;

vector<int> S(3);

for( int i=0 ; i<N ; ++i )
{
cout << "输入第" << i <<"堆石子个数：" ;
cin >> x;
if( x>=i)
S[i] = x;
else
{
cout << "输入错误！" << endl;
exit(1);
}
}
int sum = 0 ; //两人总共可以出手次数

for( int j=0; j<N; ++j )
{
sum += S[j] / ( j+1 );
}
if( sum%2 == 0 )
cout << "NO" <<endl;
else
cout << "YES" <<endl;

system(" pause ");
}