Codeforces Round #832 (Div. 2) C. Swap Game

ゝ一纸荒年。 2024-04-01 16:53 75阅读 0赞

[Problem - C - Codeforces][]

题意：

给定一个数组，Alice和Bob玩游戏，Alice先手

对于每个玩家：

1.如果a\[1\]==1，判负

2.选择一个除了a\[1\]的数，并将它减1，再与a\[1\]交换

问winner是谁

思路：

博弈题

**对于博弈，我们首先考虑状态的必胜态和必败态**

此题的必败态就是a\[1\]=1，必胜态就是a\[2\]....a\[n\]存在1

**然后再通过类似于dp的思考方式，通过决策想象上一个的状态**

对于必败态：

如果它是由操作1转移过来，那么上一个状态也是必败态，a\[1\]=1

如果由操作2转移过来，那么上一个状态就是必胜态

对于这个必胜态：

如果它是由操作1转移过来，那么上一个状态也是必胜态

如果由操作2转移过来，那么上一个状态就是a\[1\]=2

....

这样不断逆推转移，我们最终归纳发现，该博弈的必胜态就是：最小值不是a\[1\]

即：

如果a\[1\]为最小值，此时为必败态，否则就是必胜态

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10,mnf=0x3f3f3f3f;
    int n,mi=mnf;
    int a[mxn];
    void solve(){
    	mi=mnf;
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i],mi=min(mi,a[i]);
    	if(a[1]==mi) cout<<"Bob"<<'\n';
    	else cout<<"Alice"<<'\n';
    }
    int main(){
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int T;
    	cin>>T;
    	while(T--)solve();
    	return 0;
    }

**总结：**

**对于博弈，我们首先考虑状态的必胜态和必败态**

**然后再通过类似于dp的思考方式，通过决策操作想象上一个的状态**

[Problem - C - Codeforces]: https://codeforces.com/contest/1747/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #832 (Div. 2) C. Swap Game

[Problem - C - Codeforces][] 题意：给定一个数组，Alice和Bob玩游戏，Alice先手对于每个玩家： 1.如果a\[1\]==1，判

ゝ一纸荒年。/ 2024年04月01日 16:53/ 0 赞/ 76 阅读

相关 Codeforces Round #839 (Div. 3) E Permutation Game

[Problem - E - Codeforces][] 题意：给定一个排列，两个人博弈，每次他可以给所有涂蓝的块排序，然后把一个红的染成蓝色。先手想把数列排成升序，后手

喜欢ヅ旅行/ 2024年03月30日 12:37/ 0 赞/ 74 阅读

相关 Codeforces Round #708 (Div. 2) C1 C2

[Problem - C1 - Codeforces][] 题意：让你构造三个数，使它们加起来是n，然后lcm(a1,a2,a3)<=n/2 思路：构造题，要满足两

古城微笑少年丶/ 2024年03月29日 14:25/ 0 赞/ 88 阅读

相关 Codeforces Round #729 (Div. 2) c题

[https://codeforces.com/contest/1542/problem/C][https_codeforces.com_contest_1542_proble

向右看齐/ 2022年10月12日 05:25/ 0 赞/ 201 阅读

相关 Codeforces Round #728 (Div. 2)a-c

https://codeforc.es/contest/1541 cf a b c a 给定一个数n，1 2 3 4 … n

比眉伴天荒/ 2022年10月10日 04:48/ 0 赞/ 40 阅读

相关 Codeforces Round #743 (Div. 2) B. Swaps 思维

题目地址[Codeforces Round \743 (Div. 2) B. Swaps][Codeforces Round _743 _Div. 2_ B. Swaps]

深碍√TFBOYSˉ_/ 2022年09月14日 06:27/ 0 赞/ 190 阅读

相关 Codeforces Round #320 (Div. 1) B. "Or" Game

贪心思路：因为是或的关系，所以只要使得某个数尽可能得大就可以了。于是第一个想法是，选出最大的那个数，使得它乘以k次最大。但是这样会有部分情况是错误的。比如

小鱼儿/ 2022年08月08日 14:46/ 0 赞/ 163 阅读

相关 Codeforces Round 374 div2

题目链接： [ CodeforcesRound374][CodeforcesRound374] 做了这么久cf了，，c题有时候还是做不起，，真的好菜，，，，

Dear 丶/ 2022年07月16日 03:38/ 0 赞/ 199 阅读

相关 Codeforces Round #118 (Div. 2) C. Plant

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". Th

蔚落/ 2022年05月17日 01:13/ 0 赞/ 223 阅读

相关 Codeforces Round #553 (Div. 2)

A：[http://codeforces.com/contest/1151/problem/A][http_codeforces.com_contest_1151_proble

た入场券/ 2021年11月04日 13:36/ 0 赞/ 283 阅读