VP on 2025-11-15,只做了三题。

IDDiffDescriptionSolutionPenaltyReview
BMediumNN 只袋鼠,第 ii 只袋鼠的初始坐标 xi=Cix_{i}=C_i(Ci>0C_i > 0)。任意操作:选择四种指令之一,作用于所有袋鼠:xi←xi+Aix_i \leftarrow x_i + A_i,xi←xi−Aix_i \leftarrow x_i - A_i,xi←xi+Bix_i \leftarrow x_i + B_i,xi←xi−Bix_i \leftarrow x_i - B_i:最大化 xi<0x_i < 0 的袋鼠数量。(1) 即给 NN 个不等式 Aix+Biy+Ci<0A_{i} x + B_{i}y + C_{i} < 0,找一组整数 (x,y)(x, y) 使得最多的不等式成立。
(2) 直接做是半平面交,但我们没必要这样做(我也不会这个板子)。重要的观察是 Ci>0C_{i}>0,这意味着所有平面都不包含原点。可以不妨设找出的整数 (x,y)(x, y) 是无穷远点,进一步,最优点一定取平面的边界。(像是拿着手电筒原地转圈,问哪个方向照到的最多。)
(3) 对所有平面边界的射线极角排序,对边界的极角做差分,算出每个地方的答案。
*不要乱用 eps;10910^{9} 的可以安全 atan2。
CEasy求 a,ba, b 满足 a+b=N,a∣N,b∣Na + b = N, a \mid N, b\mid N。小清新签到。奇数无解,偶数取 a=b=N2a = b = \frac{N}{2}。4
FHardNN 点且初始无边的无向图,QQ 次操作:添加边权为 ww 的边;最大化两点间路径按位与。(1) 查询:从高到低逐位贪心。对于每一位,尝试将其加入当前已确定的结果中。维护 dsu(s)\text{dsu}(s):只考虑 w∧s=sw \land s = s 的边构成的子图连通性。检查利用这些边,能否使目标连通。单次 log⁡V\log V。
(2) 维护 dsu(s)\text{dsu}(s) 的方法:VV 个并查集,有用的合并只有 (N−1)V(N - 1) V 次。每次合并之后,log⁡V\log V 删去一位,递归到下一层。总时间 (N−1)Vlog⁡V(N - 1) V \log V。
AC好题。先考虑要做什么查询,再决定用什么数据结构维护及考虑如何修改。
GHardNN 个水桶,容量 ViV_i,每秒漏水 LiL_i。初始时任意合并水桶,容量取最大值,漏水取最小值。QQ 次询问第 TjT_j 秒最大剩余容量。(1) 考虑所有可能子集 S⊂[N]S\subset[N],欲求时间 tt - 剩余总容量 vv 图像的上凸壳,这个凸壳时间越大,斜率越缓。预处理凸壳分界点,多次询问在凸壳上二分。O((N+Q)log⁡N)\mathcal{O}((N+Q)\log N)。
(2) 不需要考虑所有子集,基于贪心,剩下容量最大的 kk 个与漏水最慢的 kk 个。将容量和漏水速率排序后,计算每一段的 ∑v\sum v 和 ∑l\sum l 就能确定合并时间,即一次函数的交点,为 ⌈Δ∑vΔ∑l⌉=⌈ViLi⌉\lceil \frac{\Delta \sum v}{\Delta \sum l} \rceil = \lceil \frac{V_i}{L_i} \rceil。
(3) 合并方案:设容量最大的 kk 个是红色,漏水最慢的 kk 个是蓝色。一个桶可能同时有两种颜色。那么同时标红、标蓝的桶,各自建立一组;仅标红的桶与仅标蓝的桶,两两配对;没有颜色的桶,随意并入已有组。
271+1
IHardNN 天,初始资金 MM。第 ii 天会产生打车费 EiE_i,可以选择两种行动之一:(1) 花费 BiB_i 吃饭,收益 AiA_i,自己不打车,因此 PiP_i 的概率 A 朋友花费打车费 EiE_i,1−Pi1-P_{i} 的概率 B 花费;(2) 花费 DiD_i 吃饭,收益 CiC_i,和朋友打车,如果自第一天起或自你上次承担打车费用以来,两位朋友都曾承担过打车费用,则这次必须承担,否则规则同 (1)。在保证所有可能情况的总花费均不超过 MM 的前提下,最大化收益期望。f(i,j,0/1/2/3)f(i,j,0/1/2/3):从第 ii 天到最后一天,已经花费 jj 元钱,上次以来 AB 都没付 / 仅 A 付 / 仅 B 付 / AB 都付,最大收益期望。O(NM)\mathcal{O}(N M)。AC不能用一个有限的负数表示不可能。参与期望计算时,会把不可行方案逐渐稀释变成可行方案。
KMedium象棋棋盘,马先手,车能否吃掉马。唯一的 Yes:无论马第一步怎么走,车都能在第一步吃掉马。71+2不要写超长 if。

I 的一些分析【期望 DP】

这题的状态分为两部分: 确知的费用 和 随机的状态机。前者的实现是 01 背包 DP,后者是期望 DP。

先说随机的状态机。

首先回忆一下期望 DP 的一般做法:

E(当前)=当前收益+∑kP(转移到状态 k)×E(未来状态 k)\mathbb{E}(\text{当前}) = \text{当前收益} + \sum_{k} \mathbb{P}(\text{转移到状态} \ k) \times \mathbb{E}(\text{未来状态} \ k)

依据题意,状态机是关于过去的(谁付过钱导致现在的状态)。虽然状态是由过去决定的,但我们在第 ii 天计算时,不需要知道过去具体发生了什么,我们只需要知道现在做决策 A 时,我的未来期望就是这么多即可。也就是说,在 DP 第 ii 天时,需要先知道第 i+1i+1 天的答案,因此期望 DP 的状态设的是从第 kk 天到最后一天。

如果第 ii 天出去吃,第 ii 天的状态 3 只能转移到第 i+1i+1 天的状态 0,状态 0/1/2 有一定概率转移到 1/2/3。所以,我们列出的转移方程类似于(先不考虑费用)

f(i,?,0)←p⋅f(i+1,?,1)+q⋅f(i+1,?,2)+wf(i,?,0) \gets p \cdot f(i+1, ?,1) + q \cdot f(i+1, ?,2) + w

那么如何加入确知的费用呢?

再加一个维度,实现我知道要花这么多钱的前提下,做某个决策未来会得到多少期望。这同时也满足了题目要求的最坏情况,因为我们已经为每一次决策预留足够的空间——先决定钱,再决定概率。

1
2
3
4
5
6
7
8
9
10
11
12
// 遍历每一个可能的确知预算状态 i
for (int i = 0; i <= m - b; i++) {
// i + b : 确定的费用转移
// 如果 i + b > m,循环条件限制了我们不会进入这里,保证了最坏情况不超标

// ndp[i + b][0] : 第 k 天花费 i + b 且当前状态为 0 的最大期望
chmax(ndp[i + b][0],
a + // 今天的确定性收益
p * dp[i][1] + // 概率转移:如果 A 付钱,未来(第 k+1 天以后)基于状态 1 的期望
q * dp[i][2] // 概率转移:如果 B 付钱,未来(第 k+1 天以后)基于状态 2 的期望
);
}