【Codeforces】#658 B.Sequential Nim 博弈

B.Sequential Nim

题意

有 n 堆石子,第 i 堆石子有 (a_i) 个石子,现在两个人轮流取石子,取石子的时候可以从第一堆有石子的堆中,取走任意正整数颗石子,第一个无法取石子的人输,问两人足够聪明,谁会胜利。

思路

假若只有一堆石子,那么肯定是先手赢。

  1. 如果在这一堆石子前面放一堆数量大于 1 的石子,假若有 x 个石子,那么先手第一次拿 x - 1 块石子,后手被逼拿下最后一个石子,那么先手就可以拿最后一堆。
  2. 如果在这一对石子前面放一堆数量为 1 的石子,那么先手被逼拿完这一堆,后手可以拿最后一堆。

假设初始只有最后一堆石子,我们一堆一堆的往前加。初始 ans = 1,表示现在是先手赢。

往前加,如果当前加了一个 1 ,如果本来是先手赢,现在先手被逼拿了这一堆石子,后手才是之前堆的先手,那么变成后手赢,ans = 0。如果本来是后手赢,那么现在先手赢,ans = 1.

也就是如果出现 1,答案就会翻转。

如果当前堆前面加的是 x (x > 1),假如之前 ans = 1,(先手赢,后手输)那么先手拿 x - 1 个,先手还是之前的先手,还是先手赢 ans = 1。假如之前 ans = 0(后手赢,先手输),那么先手直接拿完 x 个,作之前堆的后手,现在就是先手赢,ans = 1。

如果出现 > 1 的数字,肯定是先手赢

按照上述步骤模拟即可。

代码

/*
 * @Autor: valk
 * @Date: 2020-07-17 16:50:40
 * @LastEditTime: 2020-08-17 09:55:57
 * @Description: 如果邪恶 是 华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
 */

#include <bits/stdc++.h>
#define fuck system("pause")
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;

int arr[N];
int main(){
    int _;
    scanf("%d", &_);
    while(_--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&arr[i]);
        }
        int now=1;
        for(int i=n-1;i;i--){
            if(arr[i]==1){
                now^=1;
            }else{
                now=1;
            }
        }
        if(now==1){
            printf("First
");
        }
        else{
            printf("Second
");
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/valk3/p/13518939.html