​Problem - GYM106443D - Codeforces​

Problem - D - Codeforces这是一道博弈DP我们要考虑状态 状态转移我们令dp[x]表示剩下x的时候是必胜还是必负如果从一个状态达到的所有状态都是必胜 那么就是必负 否则必胜x 能到达的状态 每次最多删除x/2个元素 所以可以到达[x-x/2 , x-1]这些状态 我们要判断这个区间是否有必负 可以用dp数组求前缀和代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); vectorintdp(5e52,0),sumdp(5e52,0); for(int i1;i5e5;i){ if(sumdp[i]-sumdp[i/2]!i-i/2)dp[i]1; sumdp[i1]sumdp[i]dp[i]; } int t; cint; while(t--){ int n; cinn; if(dp[n])coutmastermei\n; else coutthe greatest\n; } return 0; }