D. Stoned Game
题意
给出n堆石子
每堆石子有ai个石子
现在两个人轮流取某个非0的石堆中的1个石子
但是不能取上一轮对手取的那堆石子
谁不能再取出石子则输掉比赛
问谁赢
题解
是一个关于奇偶博弈和制高点的博弈
参考题解
若没有“不能取上一轮对手取的那堆石子”这个条件则
就是普通的奇偶博弈
但是加入这个条件后就形成了制高点 先手能强制占领优势局面不变
所以当(sum-max<max)时先手可以一直拿最大堆的石子 必胜
否则通过sum的奇偶性判断 若sum为奇数
先手一直从当前剩下最多且能拿的石子堆中拿 最后先手必胜
否则后手必胜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9;
ll data[Max];
int main() {
Turnoff;
ll n;cin>>n;
for(int i=0;i<n;i++)cin>>data[i];
if(n==1){
cout<<1<<" "<<1<<endl;
for(int i=0;i<n;i++)cout<<0<<" ";
}
else {
cout<<1<<" "<<n-1<<endl;
for(int i=0;i<n-1;i++)cout<<(n-1)*data[i]<<" ";
}
cout<<endl;
cout<<n<<" "<<n<<endl;
cout<<n-data[n-1]<<endl;
cout<<1<<" "<<n<<endl;
for(int i=0;i<n-1;i++)cout<<-n*data[i]<<" ";
cout<<-n<<endl;
}
|