A. Glory Addicts
模拟,并不想写题解。
B. Prefix Sum Addicts
算出差分数组 \(d\),然后判断:
- 第一项(差分数组的第一项包括原数组 \(1 \sim n-k+1\) 项)能否合法拼出第二项;
- 第二项及之后是否有序。
第一条的具体判断方法是判断第一项是否小于等于第二项 \(\times (n-k+1)\)。
C. Even Number Addicts
直接记忆化搜索即可。
\(dp[i][j][k]\) 代表先手方当前数字奇偶为 \(i\),奇数还剩 \(j\) 个,偶数还剩 \(k\) 个的胜负。
\[\scriptsize dp[i][j][k] = (dp[i][j-1][k-1] \land dp[i][j][k-2]) \lor (dp[i \operatorname{xor} 1][j-1][k-1] \land dp[i \operatorname{xor} 1][j-2][k])\]
\(j,k\) 较小时处理一下细节即可。
设 \(\{a\}\) 中奇数有 \(x\) 个,偶数有 \(y\) 个,结果即为 \(dp[0][x][y]\)。