VP。区。

难度:DKM / CI / AEGH / BF / JL

IDDiffDescriptionSolutionPenaltyReview
在线段树上维护区间平均值。叶子 ai=ia_{i}=i,查询若涉及两侧,则返回两侧结果的算术平均。求区间 [l,r][l, r] 数量,使查询结果等于真实平均值 (l+r)/2(l + r)/2。
CHardNN 长序列 aa,a1=0a_1 = 0,0≤ai+1−ai≤10 \le a_{i+1} - a_i \le 1,MM 个约束 ∑i=1Pjai=Vj\sum_{i=1}^{P_j}a_i = V_j,求方案数。DP。g(l,d,s)g(l,d,s):长度为 ll,ai+l−ai=da_{i+l}-a_{i}=d,且区间和为 ss。f(j,u)f(j,u):满足前 jj 个约束,且 aPj=ua_{P_j}=u。枚举上一处 aPj−1=ua_{P_{j-1}} = u,当前 aPj=u+da_{P_{j}}=u+d,区间和 s=Vj−Vj−1−uls = V_j-V_{j-1}-u l,用 g(l,d,s)g(l, d, s) 转移。O(N4+T(N2+MN))\mathcal{O}(N^4 + T(N^2+MN))。*数据范围提示复杂度。DP 但原始状态需要 N5N^{5} 时空,逐个维度考虑能够需要删除。
DEasy每回合系统选择 c∈{1,2,4}c \in \{1, 2, 4\},A 和 B 同时损失 cBc B 和 cAc A 生命。判断是否对于任意 cc 的序列,都存在某回合结束时 B 死亡且 A 存活。A 的能承受攻击次数 ≥4+\ge 4 + {} B 的。前若干轮取 c=1c=1,最后一轮取 c=4c=4。38听说坑很多,例如乘法爆 LL。
NN 个点 PiP_{i},QQ 次询问点 RR,求顶点由 PiP_{i} 组成、严格包含 RR、顶点数最小的简单多边形。对 PP 的凸包三角剖分。
(1) 若 RR 在 PP 的凸包外或边界上,无解。
(2) 若 RR 在某个三角形内,答案为 3。
(3) 若 RR 在两三角形边界上:
(a) 若凸包至少 5 个点,任另取凸包上某点构成凸五边形,总能从这五个顶点中选出三个,使 RR 位于三角形内,答案为 3。(反证。假设对所有顶点 VV,VRVR 与五边形边界都相交在另一个顶点 UU,那么这些顶点会两两配对,但 5 个顶点不可能两两配对,矛盾。)
(b) 若凸包只有 4 个点。(i) 若 RR 不在对角线交点,答案为 3。(ii) 若 RR 在对角线交点:若存在 PP 在除对角线以外的其它位置,答案为 3。否则答案为 4。
© 若凸包只有 3 个点,答案为 3。
构造无向简单图,对任意 i,j (i≠j, i,j≥2)i, j \ (i \neq j,\ i, j \ge 2),删除点 i,ji, j 及其关联边后,剩下 AijA_{ij} 条边。(1) 条件即 Aij=m−di−dj+eijA_{ij} = m - d_i - d_j + e_{ij}。设 D=∑i=2ndiD = \displaystyle \sum_{i=2}^{n} d_i。注意恒等式:∑j=2neij=di−ei1\displaystyle \sum_{j=2}^{n} e_{ij} = d_i - e_{i1}
(2) 将条件对 jj 求和,Ri=∑j=2,j≠inAij=(n−2)m−(n−4)di−D−ei1(∗)\displaystyle R_i = \sum_{j=2, j \neq i}^{n} A_{ij} = (n-2)m - (n-4)d_i - D - e_{i1} \quad (*)。
(3) 对 (∗)(*) 作差,Ri−R2=(n−4)(d2−di)+e12−ei1R_i - R_2 = (n-4)(d_2 - d_i) + e_{12} - e_{i1}。先枚举 e12e_{12},再逐个枚举 ei1e_{i 1}(考虑到 n≥6n\geq 6 时,(n−4)∣(R2−Ri+e12−ei1)(n-4) \mid (R_2 - R_i + e_{12} - e_{i1}),ei1=0/1e_{i1}=0/1 只有一种成立),由此逐步推导出 ei1  ⟹  d2−di,d1e_{i1} \implies d_2 - d_i, d_{1}。
(4) 对 (∗)(*) 求和,∑i=2nRi=(n−2)(n−2)m−(n−4)D−(n−2)D−d1\displaystyle \sum_{i=2}^{n} R_{i} = (n-2)(n-2)m - (n-4)D - (n-2)D - d_{1},代入握手定理 2m=D+d1  ⟹  m,D  ⟹  di  ⟹  eij2m = D + d_1 \implies m, D \implies d_i \implies e_{ij}。
(1) 完全不会需要枚举的构造题。好神秘,感觉介于爆搜和直接构之间,这种构造能体现脑子和程序的共同作用(x)某些构造题的程序只是输出工具就没什么意思了()。
(2) 加加减减消去一些变量。
IEasy# 润两次106
KMediumNN 长序列 LL 和不降序列 AA,选取序列 bb,使 ∣bi−bi−1∣≥Li\lvert b_{i}-b_{i-1} \rvert\geq L_{i},最小化 max⁡i{∣Ai−bi∣}\max_{i}\lbrace \lvert A_{i}-b_{i} \rvert \rbrace。二分答案 xx,则需要 bi∈[Ai−x,Ai+x]b_{i}\in[A_{i}-x, A_{i}+x]。按 ii 逐个选取,考虑合法 bi−1b_{i-1} 的最小值与最大值,所得 bib_{i} 是至多两个区间。O(Nlog⁡V)\mathcal{O}(N\log V)。123
MHard选取整数 ai∈[Li,Ri]a_i \in [L_i, R_i]。坏下标 ii:对所有 1≤j<i1 \le j < i 均有 ai>aja_i > a_j。最小化坏下标 ii 的数量。设已选定的最后一个坏下标处的值为 MM。当 Li≤ML_i\le M 时,选 ai=Lia_i=L_i,不产生新的坏下标。当 Li>ML_i>M 时,必须在位置 ii 之前增加一个坏下标,延迟贪心地,选择 j≤ij\le i 中 RjR_j 最大的位置 jj,修改 aj=Rja_j=R_j,并更新 M=RjM=R_j。O(N)O(N)。*