CF2002H

令 nn 为网格的规模。我们需要寻找一条从 (1,1)(1,1) 到 (n,n)(n,n) 的路径，路径长度恒为 2n−22n-2。

由于路径总边数为 2n−22n-2，答案的上界显然为 2n−22n-2。注意到网格图有拓扑对称性，考虑 meet-in-mid。

定义副对角线所在的位置集合为 S={(r,c)∣r+c−1=n}S = \{(r, c) \mid r + c - 1 = n\}。因为是网格图，所以任何合法路径必然恰好经过 SS 中的某一个节点。

对于 SS 中的任意节点 (r,c)(r, c)，令 Fr,c\mathcal{F}_{r,c} 表示从 (1,1)(1,1) 到 (r,c)(r,c) 的所有前向路径构成的边权状压位集合，Br,c\mathcal{B}_{r,c} 表示从 (n,n)(n,n) 逆推至 (r,c)(r,c) 的所有后向路径构成的边权状压位集合。由于步数限制，Fr,c\mathcal{F}_{r,c} 与 Br,c\mathcal{B}_{r,c} 的基数上限为 (2n−2n−1)=48620\binom{2n-2}{n-1} = 48620。

对于固定的交点，在 F\mathcal{F} 和 B\mathcal{B} 中各取一个元素 f,bf, b，判断其并集 f∪bf \cup b 的 MEX 是否能达到某一目标值 KK。

满足 MEX 至少为 KK 的充要条件是并集包含 {0,1,…,K−1}\{0, 1, \dots, K-1\} 对应的所有位。定义全 11 掩码 UK=2K−1U_K = 2^K - 1。条件可以表示为：

f∪b⊇UK f \cup b \supseteq U_K

考虑通过集合求补将其转化为对后向集合的查询：

b⊇UK∖f  ⟺  b⊇(∼f)∩UK b \supseteq U_K \setminus f \iff b \supseteq (\sim f) \cap U_K

令查询掩码 ReqK(f)=(∼f)∩UKReq_K(f) = (\sim f) \cap U_K。

现在考虑一个全新的问题：是否存在 b∈Bb \in \mathcal{B}，使得 bb 是 ReqK(f)Req_K(f) 的超集。

很典的做法是将 B\mathcal{B} 中的所有状态构建为一棵深度为 2n−22n-2 的 01Trie 上面。

我们在 Trie 的每个节点 uu 额外维护一个状态 sub_orusub\_or_u，表示以 uu 为根的子树中所有掩码的按位或。

当我们在 Trie 上递归查询 ReqReq 是否存在超集时，若满足 (sub_oru & Req)≠Req (sub\_or_u \ \& \ Req) \neq Req 说明即使把当前子树内所有的状态取并集，也无法凑齐 ReqReq 中需要的二进制位，这部分是绝对不存在合法解的，直接扔了。剩下的就是维护已知的最大 MEX 答案，记为 ansans，考虑按照 popcount 降序验证。时间复杂度我不会证，但应该是对的。

2024 ICPC Asia East Online (I) E. Random Dungeon

令 NN 为地下城的变化总数。我们需要寻找一个最优停止策略，每次挑战成本恒为 CC。

由于每次是从未出现的集合中等概率随机抽取，感觉正着不好做所以考虑倒着做。

定义 EmE_m 为当剩余卡池里还有 mm 个关卡时，继续参与游戏的最优期望收益。如果在这一步抽到了分数 xx，面临的决策是：收手拿 xx，或者放弃当前分数，花费 CC 继续抽并获得期望 Em−1E_{m-1}。显然，只有当 x≥Em−1x \ge E_{m-1} 时我们才会停止。注意到当卡池中还剩 mm 个关卡时，这 mm 个关卡必定恰好是原数组 AA 中最大的 mm 个。

对于序列，令 AA 按降序排列，即 A1≥A2≥⋯≥ANA_1 \ge A_2 \ge \dots \ge A_N。当 m=1m=1 时，别无选择，必定拿到最大的 A1A_1，故 E1=A1−CE_1 = A_1 - C。

对于一般的 mm，由于剩余的 mm 个数正是前 mm 大的元素，等概率抽取下的转移方程可以表示为：

Em=1m∑i=1mmax⁡(Ai,Em−1)−C E_m = \frac{1}{m} \sum_{i=1}^{m} \max(A_i, E_{m-1}) - C

改成前缀查询的形式：

Ai≥Em−1  ⟺  max⁡(Ai,Em−1)=Ai A_i \ge E_{m-1} \iff \max(A_i, E_{m-1}) = A_i

令查询分界点为 kk，满足 Ak≥Em−1>Ak+1A_k \ge E_{m-1} > A_{k+1}，因为 AA 是单调递减的，所以做完了。

我们在预处理时额外维护一个前缀和数组 prefi=∑j=1iAjpref_i = \sum_{j=1}^i A_j，表示前 ii 大的元素之和。

当我们在递推求 EmE_m 时，由于只能在前 mm 个元素中抽取，有效的界限为 k′=min⁡(k,m)k' = \min(k, m)。说明前 k′k' 个元素直接取自身的值，剩下的 m−k′m - k' 个元素无法超越期望，统统取 Em−1E_{m-1}。这部分直接通过 prefk′+(m−k′)×Em−1pref_{k'} + (m - k') \times E_{m-1} 算，时间复杂度是单 log⁡\log 的。