省选模拟赛Ⅵ

· · 个人记录

一、2024.2.2

1.线索

模拟题，搜索加剪枝就能过，可惜考试时直接跳了。

2.鱼

0/100

事实证明，还有时间能对拍就对拍，挂了 25 分。当位置 t 可以拓展到 [l_t,r_t]，i(i>t) 可以拓展到 t 位置，不能因为当前 l_i\le r_t，就将 i 位置拓展的权值和赋值成 t 拓展的权值和，因为 r_t 有可能小于当前的 r_i，将位置 i 拓展的区间并上 t 拓展的区间，权值和用前缀和计算更新即可。

二、2024.2.5（WC2024）

1.水镜

把石柱横排在一个平面上，将石柱顶点相连，则需要翻折的是线段向下走的连续段，对对称轴高度 L 有限制的只有波峰和波谷。对于波峰，即 h[i-1]\le h[i]\ge h[i+1]，要么翻折从 i+1 开始的向下的点，要么翻折从 i 开始的点，这一段翻折的第一个点翻折后需要比它前面一个点高，这增加对 L 下界的限制，贪心地选择限制较低的那个点开始翻折。对于波谷，同样有两种翻折方式，这一段翻折的最后一个点翻折后需要比它后面一个点低，这增加对 L 上界的限制。用双指针维护可行区间，同时用两个单调队列维护上界限制最小值和下界限制最大值。

2.线段树

20/100

把维护区间 \lbrack l,r) 的线段树结点看成边 (l,r)，边权 1/0 表示是否已知区间和，则区间 \lbrack l_q,r_q) 的和可知当且仅当存在点 l_q 到 r_q 的边权全为 1 的路径。

三、2024.2.15

1.挑战NPC

15/100

题目来源（本题有加强）；类似题；

我求出对于每个 d，删掉所有长度大于 d 的边，最少需要删多少个点，这样剩下的点是最大团。枚举每条需要删的边选择删哪个端点。结果证明此思路很糟糕。

从小到大加边，按标号从小到大枚举最大团选哪些点（保证加进去后仍是一个团），bitset 优化 + 剪枝，能得 50 分。或者多随机几次加点顺序，能加入就加入——这也是求最大团的经典随机化算法（原题可以这么过）。

最大团的大小等于其补图（原图中的点和所有原图中不存在的非自环边组成的图）最大独立集（任意两点不相邻）的大小。

枚举两个点，将它们的距离定为团的最大边长，那么可以加入团的点只能为图中的黄紫点，且这部分点的非合法边（即补图中的边）必横跨线段 AB。将黄紫点分别看作二分图的左右部点，再求二分图最大独立集就行。时间复杂度 O(n^{4.5}) 。

2.糖果大赛

10/100

博弈题，分类讨论减少未知胜负的集合个数，再暴力状压 DP，见洛谷题解。

3.聚会

10/100

题解

四、2024.2.16

1.树莓立方体

35/100

先说这道题——【NOIP2022】比赛。题意：给两个数组 a,b，多组询问，每次询问 [l,r]，求 \sum_ {l\le p\le q\le r}\max a_{[p,q]}\cdot\max b_{[p,q]} 。

解法：将右指针 r 从左往右移，维护数组 ma,mb，ma_i=\max a_{[i,r]}，指针每右移一位，更新 a,b 数组的单调栈时更新 ma,mb，这只对 ma,mb 区间赋值。同时维护数组 sum，sum_i 为 ma_i\times mb_i 的 历史版本和，也即 sum_i=\sum_{j=i}^{r}\max a_{[i,j]}\cdot \max b_{[i,j]}，那么对 [l,r] 的询问的答案就为 \sum_{i=l}^rsum_i 。指针每右移一位，\forall i\in[1,r],sum_i 需要加上 ma_i\times mb_i 。下讨论 sum 的更新方法。

设 ma_{[la,r]} 被赋值成 a_r，mb_{[lb,r]} 被赋值成 b_r，以 la<lb 为例。

注意到 a_r,b_r 是常量而 ma_i,mb_i 是实时变量，拆分 sum_i=k_{ab}\cdot ma_i\cdot mb_i+k_a\cdot ma_i+k_b\cdot mb_i+k，就能用线段树维护。（注意懒标的合并）

回到本题，只有一行以及 a=1,2 的情况就能用维护历史版本和的方法做。

2.爱上火⻋

25/100

五、2024.2.19

115/300

T1 20 min 想出做法，调了 3.5 h，对拍 0.5 h，恶心细节题，T2 直接没看，T3 打了暴力。

1.电车

为什么不给 O(nm) 的步骤分啊。 称某行为间断行当且仅当它为第一行或最后一行或这一行存在人坐，每相邻的两个间断行为一个区间，设为 [l,r]，则下一个人只会坐在第 l 行、第 r 行、第 \lfloor\frac{l+r}2\rfloor 行或第 \lceil\frac{l+r}2\rceil 行上，set 维护所有区间，选最优区间中这四行的最优位置即可。

2.异色

15/100

对于基环树，设 u 是以 1 为根的 dfs 树上深度最小的环上的点，则答案路径不会同时经过连接 u 的两条环边，分别删去这两条边，转化为树上问题。