AGC020 随便补题, 感觉质量一般但是 F 没补.

A#

给定一个 个格子的棋盘, A 先手执白棋于第 个格子, B 后手执黑棋于第 个格子. 一次移动可以将棋子从第 个格子移动至第 或第 个格子, 但是不能移出棋盘, 也不能移到已有的棋子上. 不能移动者判负, 问先手有无必胜策略?

显然若 则先手必胜, 否则先手必败.

B#

有一个游戏, 一开始有 个人, GM(Game Master) 每次发布如下的指令:

• 组成 个人的组！

然后人们会尽可能多的组成 个人的组, 无法被分配到组里的人淘汰. 轮后, 只剩下两个人作为赢家. 给定 , 求游戏开始时人数最多/最少为多少人.

设当前人数区间为 . 我们考虑现在在前面新增一轮游戏 , 人数区间的变化. 显然变为 .

B.cpp

C#

给定一个 个数的序列 , 求 所有非空子集和的中位数.

.

答案为所有 的子集和中, 大于等于 的最小值. 考虑一个子集和和它补集的和即可证明这个结论. 用 bitset 优化背包即可做到 .

E#

给定一个长度为 的 01 串 . 我们称一个串 可以被压缩成另一个串 , 当且仅当:

• 0 可以压缩成 0, 1 可以压缩成 1.
• 若 A 可以压缩成 A', B 可以压缩成 B', 那么 AB 可以压缩成 A'B'
• 形如 PPPPPPP .... P( 个 P) 的串可以被压缩成 (PxK).

例如: 001001001 可以被压缩成 001001001, 00(1(0x2)x2)1 或者 (001x3).

求 的子集的不同压缩方案数. 一个串 是 的子集, 当且仅当对于 的任意一位 , 的对应位不大于 .

直接状压 DP 即可. 可以证明状态数极少(怎么证明的?).