VP。区。
难度:DKM / CI / AEGH / BF / JL
| ID | Diff | Description | Solution | Penalty | Review |
|---|
| | 在线段树上维护区间平均值。叶子 ai=i,查询若涉及两侧,则返回两侧结果的算术平均。求区间 [l,r] 数量,使查询结果等于真实平均值 (l+r)/2。 | | | |
| | | | | |
| C | Hard | N 长序列 a,a1=0,0≤ai+1−ai≤1,M 个约束 ∑i=1Pjai=Vj,求方案数。 | DP。g(l,d,s):长度为 l,ai+l−ai=d,且区间和为 s。f(j,u):满足前 j 个约束,且 aPj=u。枚举上一处 aPj−1=u,当前 aPj=u+d,区间和 s=Vj−Vj−1−ul,用 g(l,d,s) 转移。O(N4+T(N2+MN))。 | * | 数据范围提示复杂度。DP 但原始状态需要 N5 时空,逐个维度考虑能够需要删除。 |
| D | Easy | 每回合系统选择 c∈{1,2,4},A 和 B 同时损失 cB 和 cA 生命。判断是否对于任意 c 的序列,都存在某回合结束时 B 死亡且 A 存活。 | A 的能承受攻击次数 ≥4+ B 的。前若干轮取 c=1,最后一轮取 c=4。 | 38 | 听说坑很多,例如乘法爆 LL。 |
| | N 个点 Pi,Q 次询问点 R,求顶点由 Pi 组成、严格包含 R、顶点数最小的简单多边形。 | 对 P 的凸包三角剖分。 (1) 若 R 在 P 的凸包外或边界上,无解。 (2) 若 R 在某个三角形内,答案为 3。 (3) 若 R 在两三角形边界上: (a) 若凸包至少 5 个点,任另取凸包上某点构成凸五边形,总能从这五个顶点中选出三个,使 R 位于三角形内,答案为 3。(反证。假设对所有顶点 V,VR 与五边形边界都相交在另一个顶点 U,那么这些顶点会两两配对,但 5 个顶点不可能两两配对,矛盾。) (b) 若凸包只有 4 个点。(i) 若 R 不在对角线交点,答案为 3。(ii) 若 R 在对角线交点:若存在 P 在除对角线以外的其它位置,答案为 3。否则答案为 4。 © 若凸包只有 3 个点,答案为 3。 | | |
| | | | | |
| | 构造无向简单图,对任意 i,j (i=j, i,j≥2),删除点 i,j 及其关联边后,剩下 Aij 条边。 | (1) 条件即 Aij=m−di−dj+eij。设 D=i=2∑ndi。注意恒等式:j=2∑neij=di−ei1 (2) 将条件对 j 求和,Ri=j=2,j=i∑nAij=(n−2)m−(n−4)di−D−ei1(∗)。 (3) 对 (∗) 作差,Ri−R2=(n−4)(d2−di)+e12−ei1。先枚举 e12,再逐个枚举 ei1(考虑到 n≥6 时,(n−4)∣(R2−Ri+e12−ei1),ei1=0/1 只有一种成立),由此逐步推导出 ei1⟹d2−di,d1。 (4) 对 (∗) 求和,i=2∑nRi=(n−2)(n−2)m−(n−4)D−(n−2)D−d1,代入握手定理 2m=D+d1⟹m,D⟹di⟹eij。 | | (1) 完全不会需要枚举的构造题。好神秘,感觉介于爆搜和直接构之间,这种构造能体现脑子和程序的共同作用(x)某些构造题的程序只是输出工具就没什么意思了()。 (2) 加加减减消去一些变量。 |
| | | | | |
| | | | | |
| | | | | |
| I | Easy | # 润两次 | | 106 | |
| | | | | |
| K | Medium | N 长序列 L 和不降序列 A,选取序列 b,使 ∣bi−bi−1∣≥Li,最小化 maxi{∣Ai−bi∣}。 | 二分答案 x,则需要 bi∈[Ai−x,Ai+x]。按 i 逐个选取,考虑合法 bi−1 的最小值与最大值,所得 bi 是至多两个区间。O(NlogV)。 | 123 | |
| | | | | |
| M | Hard | 选取整数 ai∈[Li,Ri]。坏下标 i:对所有 1≤j<i 均有 ai>aj。最小化坏下标 i 的数量。 | 设已选定的最后一个坏下标处的值为 M。当 Li≤M 时,选 ai=Li,不产生新的坏下标。当 Li>M 时,必须在位置 i 之前增加一个坏下标,延迟贪心地,选择 j≤i 中 Rj 最大的位置 j,修改 aj=Rj,并更新 M=Rj。O(N)。 | * | |