2020-2021:teams:manespace:codeforces_round_652_div2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_652_div2 [2020/06/27 22:03] iuiou |
2020-2021:teams:manespace:codeforces_round_652_div2 [2020/06/27 23:16] (当前版本) iuiou |
||
|---|---|---|---|
| 行 90: | 行 90: | ||
| 题意：博弈问题，$a$和$b$玩游戏，共进行$n$轮游戏，每轮游戏的先手为上场比赛的输者，比赛内容如下，两个数$a$和$b$，满足$a<b$，每次可以将$a$变成$a+1$或者是$2a$，第一个超过的$b$的玩家输。第一轮现手为主人公，问主人公是否有策略使自己n轮下来必输或者必赢。 | 题意：博弈问题，$a$和$b$玩游戏，共进行$n$轮游戏，每轮游戏的先手为上场比赛的输者，比赛内容如下，两个数$a$和$b$，满足$a<b$，每次可以将$a$变成$a+1$或者是$2a$，第一个超过的$b$的玩家输。第一轮现手为主人公，问主人公是否有策略使自己n轮下来必输或者必赢。 | ||
| - | 题解：<del>恶心的博弈论</del>， | + | 题解：<del>恶心的博弈论</del>，记每轮的数为$s$和$e$ |
| - | 可以先分别计算必胜或者必输的可能，假设第i论必胜可能为win[i], | + | 可以先分别计算必胜或者必输的可能，假设第i论必胜可能为win[i],必输的可能为lose[i]；首先考虑win |
| + | |||
| + | * 如果e为奇数，则先手没有胜利的可能，因为对方总可以保证轮到现手时为奇数，而先手会最先将其变成抄过e的偶数。(归纳法也可以证) | ||
| + | * 如果e为偶数； | ||
| + | * 如果有$\frac{e}{2}<s$，则若s为奇数,先手必胜(只能一个一个的加) | ||
| + | * 如果有$\frac{e}{2}≥s>\frac{e}{4}$,则先手必胜，(先手乘2转化为上一种情况) | ||
| + | * 如果有$s<\frac{e}{4}$，则问题直接转化为$win(s,\frac{e}{4})$ | ||
| + | 再考虑必输的可能性 | ||
| + | * 既然想快点输那么肯定拼命乘2，如果一开始有$\frac{e}{2}<s$,则先手可以必输，否则，问题转化为谁先让局面达到$\frac{e}{2}<s$这种情况，则对方可以必输，即$win(s,\frac{e}{2})$ | ||
| + | 考虑完一局中必胜与必输，注意这含义是可以凭借自己的意愿在先手时必胜或必输。如果在上一句满足必胜必输都可以，则比赛完全掌控在 | ||
| + | 先手的手里，之后先手可以随意获胜或输掉来获得最终的结果。如果上一句既没有办法获胜有没有办法一定输，那么比赛掌握在对方手里，对方可以操控比赛，上一句可以必胜且没办法输，则对方先手，结果要取反，上一句不能保证赢但是必输，则自己先手。这样最后可以得到答案。(双方都会尽量让自己掌握比赛的主导权) | ||
| + | |||
| + | <hidden> | ||
| + | <code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int maxn=1e5+13; | ||
| + | typedef long long ll; | ||
| + | int win[maxn];//记录每一局是否肯定赢 | ||
| + | int lose[maxn];//记录每一局是否肯定输 | ||
| + | ll s[maxn],e[maxn]; | ||
| + | bool getwin(ll s,ll e)//能否根据自己的意愿让先手赢 | ||
| + | { | ||
| + | if(e&1) | ||
| + | { | ||
| + | if(s%2==0) | ||
| + | { | ||
| + | return 1; | ||
| + | } | ||
| + | else return 0; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | if(2*s>e) | ||
| + | { | ||
| + | if(s&1) return 1; | ||
| + | else return 0; | ||
| + | } | ||
| + | else if(4*s>e) return 1; | ||
| + | else return getwin(s,e/4); | ||
| + | } | ||
| + | } | ||
| + | bool getlose(ll s,ll e)//能否根据自己的意愿让先手输 | ||
| + | { | ||
| + | if(2*s>e) return 1; | ||
| + | else return getwin(s,e/2); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | lose[0]=1; | ||
| + | for(int i=1;i<=t;i++) scanf("%lld%lld",&s[i],&e[i]); | ||
| + | for(int i=1;i<=t;i++) | ||
| + | { | ||
| + | if(lose[i-1]&&win[i-1]) | ||
| + | { | ||
| + | return printf("1 1"),0; | ||
| + | } | ||
| + | else if(!lose[i-1]&&!win[i-1]) | ||
| + | { | ||
| + | return printf("0 0"),0; | ||
| + | } | ||
| + | else if(lose[i-1]) | ||
| + | { | ||
| + | win[i]=getwin(s[i],e[i]); | ||
| + | lose[i]=getlose(s[i],e[i]); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | win[i]=!getwin(s[i],e[i]); | ||
| + | lose[i]=!getlose(s[i],e[i]); | ||
| + | } | ||
| + | } | ||
| + | printf("%d %d",win[t],lose[t]); | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/manespace/codeforces_round_652_div2.1593266617.txt.gz · 最后更改: 2020/06/27 22:03 由 iuiou
