Codeforces Round #658 (Div. 2) B. Sequential Nim
程序员文章站
2022-03-04 21:27:10
B. Sequential Nim题目链接-B. Sequential Nim题目大意给 nnn 堆石子的数量,两人轮流从最左端的非空堆中取任意数量(>0)(>0)(>0)的石子,无法再取者输,假设两人都会采取最佳策略,判断谁会赢解题思路因为每堆石子只有ai=1a_i=1ai=1和ai>1a_i>1ai>1这两种情况,当ai=1a_i=1ai=1时是没有决策权的,该该堆只能一次取完,而当ai>1a_i>1ai>1时,可以选择一次...
B. Sequential Nim
题目链接-B. Sequential Nim
题目大意
给 堆石子的数量,两人轮流从最左端的非空堆中取任意数量的石子,无法再取者输,假设两人都会采取最佳策略,判断谁会赢
解题思路
- 因为每堆石子只有和这两种情况,当时是没有决策权的,该该堆只能一次取完,而当时,可以选择一次拿完,让对手拿下一堆或者拿走个,让对手只能拿该堆剩下的一个
- 所以我们可以得出,第一次拿到数量大于 的石子堆的人是该场赢家,因为他可以通过取个或全部取完来迫使对方进入自己的节奏,具有该场的总决策权
- 我们需要特判一下每堆石子都只有个的情况,这种情况需要判断的奇偶性来确定是谁先无法再取
- 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=1e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
bool ass=0;
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1&&!ass) cnt++;
else ass=1;
}
if(!ass)
cout<<(n&1?"First":"Second")<<endl;
else
cout<<(cnt&1?"Second":"First")<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/Fiveneves/article/details/107523254
上一篇: 微信小程序开发之十六 —— 云开发入门
下一篇: uni-app入门(一)-微信小程序开发
推荐阅读
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #461 (Div. 2) B. Magic Forest(异或的性质)
-
Codeforces Round #658 (Div. 2)C1. Prefix Flip (Easy Version)(贪心)
-
Codeforces Round #658 (Div. 2) (C1、C2)
-
Codeforces Round #663 (Div. 2) B. Fix You
-
Codeforces Round #658 (Div. 2) B. Sequential Nim
-
B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)
-
Codeforces Round #666 (Div. 2)B. Power Sequence(等比数列)
-
Codeforces Round #664 (Div. 2) B. Boboniu Plays Chess
-
Codeforces Round #658 (Div. 2) D. Unmerge(dp,01背包)