2020-2021:teams:manespace:codeforces_round_652_div2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_652_div2 [2020/06/27 22:45] iuiou |
2020-2021:teams:manespace:codeforces_round_652_div2 [2020/06/27 23:16] (当前版本) iuiou |
||
|---|---|---|---|
| 行 98: | 行 98: | ||
| * 如果有$\frac{e}{2}≥s>\frac{e}{4}$,则先手必胜，(先手乘2转化为上一种情况) | * 如果有$\frac{e}{2}≥s>\frac{e}{4}$,则先手必胜，(先手乘2转化为上一种情况) | ||
| * 如果有$s<\frac{e}{4}$，则问题直接转化为$win(s,\frac{e}{4})$ | * 如果有$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.1593269100.txt.gz · 最后更改: 2020/06/27 22:45 由 iuiou
