AgOH

Codeforces Global Round 22 题解

字数统计: 253阅读时长: 1 min
2022/10/04

A. Glory Addicts

模拟,并不想写题解。

B. Prefix Sum Addicts

算出差分数组 \(d\),然后判断:

  1. 第一项(差分数组的第一项包括原数组 \(1 \sim n-k+1\) 项)能否合法拼出第二项;
  2. 第二项及之后是否有序。

第一条的具体判断方法是判断第一项是否小于等于第二项 \(\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]\)

CATALOG
  1. 1. A. Glory Addicts
  2. 2. B. Prefix Sum Addicts
  3. 3. C. Even Number Addicts