小花梨的取石子游戏
Problem D、小花梨的取石子游戏
时间限制：1000ms 空间限制：512MB
Description
小花梨有?堆石子，第?堆石子数量为??，?堆石子顺时针编号为1 − ?（如图）。
游戏将进行?轮，每轮游戏单独进行，互不干扰，每轮初始时第?堆石子数目为??。
第?轮从编号为?的那堆石子为起点，顺时针来取石子。两人轮流取石子，不可不取，最少取
一个石子，最多把当前这一堆取完，只有取完一堆后才走到下一堆石子。走完一圈后石子都
被取完，不能取石子的人就失败。假设两人以最优策略进行取石子操作，请分别输出?轮游
戏是先手胜还是后手胜。
Input
第一行为正整数?，表示石子的堆数 (1 ≤ ? ≤ 100000)
第二行输入?个正整数表示每一堆的石子数目??(1 ≤ ?? ≤ 109
)
Output
输出?行，第?行表示第?轮游戏的结果。如果先手胜则输出"?????"，后手胜输出"??????"。
Example
Sample Input Sample Output
3
2 1 3
First
Second
First
2
2 2
First
First
Note
样例1：
游戏进行3轮
第1轮游戏石子堆下标的顺序为1 2 3，此时石子数目按顺序为2 1 3，先手胜
第2轮游戏石子堆下标的顺序为2 3 1，此时石子数目按顺序为1 3 2，后手胜
第3轮游戏石子堆下标的顺序为3 1 2，此时石子数目按顺序为3 2 1，先手胜
接下来先说一下我对这道题的看法：
当看到这道题的时候我发现它是一个博弈论；于是我便开始拿着我的板子判断它是属于尼姆博弈，巴什博弈和威佐夫博弈中的哪一种，结果发现，哪一种也不是，所以我认为它是一道思维题；
不断在WA中探索正确的道路，终于被我找到了，但可能是由于复杂度太高，导致超时，还好最后改进了一下，过了。
在这道题中，一共wa了貌似是19次，很悲，希望在比赛的过程中一定要细心一点，不要看着接过去改程序了，考虑要全面一点；
接下来说一下这一题的算法，由于本人表达能力不好，又与题解考虑得近乎一样，就直接用题解了，原谅；
-
现在只考虑每一轮游戏；
-
一堆的时候是必胜态；
-
多堆的时候：
起点数目大于1，是必胜态
因为可以取完或者取得只剩下一个，这两种状态的胜负一定不同，也就是说一定可以到达必败状态，所以此时为必胜态；起点数目等于1，和下一点的状态相反；（我这这里就主要是判断1的个数了）；
运用到的方法主要就是两次遍历数组，一次从前交往后，一次从后往前，
以下附上我的ac代码：
package 登;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
public class D_1 {
static int n;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
n=Integer.parseInt(sc.readLine());
String s=sc.readLine();
String[] ss=s.split(" ");
int[] ch=new int[n];
int[] test=new int[n];
for(int i=0;i<n;i++) {
ch[i]=Integer.parseInt(ss[i]);
if(ch[i]!=1) {
test[i]=0;
}
else {
test[i]=1;
}
}
if(n==1) {
System.out.println("First");
return;
}
for(int i=(n-1);i>0;i--) {
if(ch[i-1]==1) {
if(ch[i]==1) {
test[i-1]=test[i]+1;
}else {
test[i-1]=1;
}
}else {
test[i-1]=0;
}
}
if(test[0]==n) {
Arrays.fill(test, n);
}else {
if(test[0]!=0&&test[n-1]!=0) {
test[n-1]=test[0]+1;
for(int i=n-2;i>=0;i--) {
if(test[i]==0)
break;
else {
test[i]=test[i+1]+1;
}
}
}
}
for(int i=0;i<n;i++) {
if(test[i]%2==0&&test[i]!=n) {
out.println("First");
}else if(test[i]%2==0&&test[i]==n) {
out.println("Second");
}else if(test[i]%2!=0&&test[i]!=n) {
out.println("Second");
}else if(test[i]%2!=0&&test[i]==n) {
out.println("First");
}
}
out.flush();
out.close();
}
}
为了便于大家的理解，附上我的另一组代码，虽然没有ac，但思路是正确的就是有点超时:
package 登;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class D_2 {
static int n;
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
n=Integer.parseInt(sc.readLine());
String s=sc.readLine();
String[] ss=s.split(" ");
int[] ch=new int[n];
for(int i=0;i<n;i++) {
ch[i]=Integer.parseInt(ss[i]);
}
for(int i=0;i<n;i++) {
int m=countOne(ch,i);
if(m%2==0&&m!=n) {
out.println("First");
}else if(m%2==0&&m==n) {
out.println("Second");
}else if(m%2!=0&&m!=n) {
out.println("Second");
}else if(m%2!=0&&m==n) {
out.println("First");
}
}
out.flush();
out.close();
}
private static int countOne(int[] ch, int i) {
// TODO Auto-generated method stub
int count=0;
if(ch[i]!=1)return count;
else {
while(ch[i]==1) {
if(count==n) {
break;
}
count++;
i++;
if(i==n) {
i=0;
}
}
return count;
}
}
}
