VP。

IDDiffDescriptionSolutionPenaltyReview
BHard(1) 对非负序列 bb,重复操作:选择 i,ji, j,若 bi+bjb_i + b_j 为奇数则停止,否则将 bi,bjb_i, b_j 同时变为 (bi+bj)/2(b_i + b_j) / 2。f(b)f(b):停止前操作次数的最小值。
(2) NN 长序列 AA,求 ∑l≤rf(A[l:r])2\sum_{l \le r} f(A[l:r])^2。
(1) 若 ∣b∣≥3\lvert b \rvert \geq 3,答案为 min⁡i{ν2(bi−bi−1)}\min_{i}\lbrace \nu_{2}(b_{i} - b_{i-1}) \rbrace,其中设 ν2(0)=+∞\nu_{2}(0)=+\infty。182+3
NN 长非负序列 AA,重复操作:选择排列 pp,同时更新 Ai←Ai mod max⁡(Api,1)A_i \gets A_i \bmod \max(A_{p_i}, 1),然后任选一个元素删除,将其余元素拼接。最大化 N−1N-1 次操作后剩余的元素。
EEasyNN 长初始全为 00 的序列 aa。重复操作:等概率随机选择未锁定的下标 ii,令 aia_i 增加 11,随后永久锁定任意下标。当序列严格递增时终止。求最优策略下最小期望轮数。没有几何分布。若第一步选中 i=1i=1,则需要 ai≥ia_i \ge i;否则需要 ai≥i−1a_i \ge i - 1。1nn(n+1)2+n−1nn(n−1)2\frac{1}{n} \frac{n(n+1)}{2} + \frac{n-1}{n} \frac{n(n-1)}{2}。15
GExpertNN 长序列 AA,值域 [0,2K)[0, 2^K),均匀随机生成。选手参与 NN 轮游戏,初始得分 x=0x = 0,每轮实时决定是否令 x←x⊕Apix \gets x \oplus A_{p_i}。已知选手策略:认为 AA 均匀分布,选择能最大化期望得分的操作,若期望得分相同则选择异或。求排列 pp 最小化选手期望得分。(1) 由于 AA 均匀分布,那么 x←x⊕Apix \gets x \oplus A_{p_i} 也均匀分布,因此当 x⊕Api≥xx \oplus A_{p_i} \ge x 时选手策略是操作。
(2) 答案大概率为 2K−12^{K-1}。最优时,highbit 不降,每个 highbit 恰有第一个数被操作。
(3) 问题化为:每个 highbit 取一个数,异或和最小。分组 FWT。
*
KEasyNN 长非负序列 AA,构造 ss,满足从 [N][N] 的非空子集中均匀随机取一个 SS,则 PS(∏i∈SAi=s)>1/2\mathbb{P}_{S}(\prod_{i \in S} A_{i}=s) > 1/2。若存在 0,取 s=0s=0;若序列全为 1,取 s=1s=1;否则,反复删去 1(比例考虑空集时,删去 1 不影响 ss 的比例),得到只能是 {a}\lbrace a \rbrace 或 {a,a}\lbrace a, a \rbrace。25
LExpertNN 点图。NN 个三元点对,每个点出现恰好 33 次。删除一个点对,再从剩余每个点对中各删除一个点,得到 N−1N-1 个二元点对,连边后构成一棵树。(1) 考虑有向树,树上每个非根点需要一条入边。需要给每个点 uu 分配一个点对 ii,再指定父节点 vv 形成生成树,特别地,被删去的点对作为根,不需要分配父节点。
(2) 对于前者,以原图点 uu 为左部点,点对下标 ii 为右部点建立二分图。这是 3−3- 正则二分图,有完美匹配。
(3) 对于后者,将可选的父子关系画成有向边,对于点对 ii 匹配节点 uu,父节点可以是 vv 或 ww,连接 v→uv \to u 及 w→uw \to u,得到一个入度等于出度的弱连通有向图,这必然强连通,可以定根并找到外向生成树。
*