9.1-9.6 学习记录

9.1

完善了部分训练策略。
能力提升综合题单 Part 1.1 - 1.2，比较有价值的题目：

• P1980 计数问题：按位考虑数位贡献。
• P1014 Cantor 表：对角线分组，副对角线和相同，奇偶讨论。
• P1047 校门外的树：区修想差分。

9.2

能力全面提升综合题单 Part 1.3 - 1.4

• P1012 拼数：拼数比较法求最大整数。 $A+B > B+A$，这构成严格偏序。
• P2010 回文日期：枚举部分，构造另一部分，判断合法性。
• P1028 数的计算：序列计数问题，使用结尾元素来代表一个序列。常见有：长度、开头元素、结尾元素。
• P4994 终于结束的起点：Fibonacci 数列模 $M$ 意义下的周期性，可以用 $\pi(M)$ 描述，$\pi(M) \le 6M$。

思维训练：

AT_arc111_c

题意：构造题，求最小交换次数和方案，使得每个人拿到对应的行李。若超重，则无法交换。

失败的思考路径：

1. 构造题，考虑无解的情况。猜测结论，满足充分性但不会证明必要性，遂作罢。
2. 数据范围提示排序，排了之后也不会。

正确的思考路径：

1. 通过交换实现排列归位，是置换环的经典应用。直接图论建模。
2. 考虑下界。如果没有约束，最少也需要交换 $n -$ 环数 次交换。
3. 考虑通过构造达到下界。每一个环内，找到体重最大的那个点 $i$，使其与它的前继交换，这样会使得前继归位。非法的情况当且仅当最大体重无法接受交换前，前继的背包重，但这样就无法交换了，因此，只要交换成功，就不会出现非法。
4. 非法情况只存在于无法交换的情况中，即非自环的环上，存在 $b_i \ge a_i$。

9.3

能力全面提升综合题单 Part 2.2 - 2.4

• P1309 瑞士轮：全局排序的一种优化–>归并合并两个有序序列，可拓展至 $k$ 路归并。
• P1902 刺杀大使：最大值最小可以用二分答案做。但这题同时也是瓶颈路，需要想到 MST，不断地添加边（两点边权是 $\max$ 两点点权），直到第 $n$ 行的点都可以和第 $1$ 行的点连通。时间复杂度 $O(n^2 \log n^2)$。
• P1314 聪明的质检员：关注 $f$ 函数则有单调性，且是求数值，考虑二分；关注差值函数则是单峰函数，考虑三分求单峰函数极值。
• P1083 借教室：区修区查可以线段树做。注意到答案函数是单调 $01$ 函数，考虑二分。
• P1429 平面最近点对：分治经典题，按 $x$ 分左右，答案要么左、要么右、要么跨左右。将二维问题固定一维，变成区间问题，神似线段树。

思维训练

AT_arc106_d

题意：对于 $x\in[1,k]$，分别求 $\left(\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L + A_R)^X\right) \bmod 998244353$。

错误的思考：

1. 计数题，这题的大方向肯定是转化计数对象，考虑 $A_i$ 的贡献，或者值域的贡献？($2\times 10^8$)。

2. 这个 $x$ 提示我们需要递推，先确定 $x=1$ 的边界情况。

3. 考虑 $x=1$，此时 $A_i$ 贡献了 $(n-i)+(i-1)=n-1$ 次。

4. 考虑递推。从 $A_i$ 的角度看贡献，首先把二项式拆开。

   $(A_L+A_R)^x = {x \choose 0} A_L^x A_R^0+ {x-1 \choose 1} A_L^{x-1}A_R^1 …$

   由于 $x \le 300$，所以我们可以考虑每一个 $A_L^i$ 的贡献次数。

5. 从 $x=1$ 得到启发，$A_i^{j}$ 的贡献可分为 $L,R$ 两类：

   • $i$ 作为 $L$ 时
     • 原：$\sum_{k \in [i+1,n]} {j \choose x-j} A_i^jA_k^{x-j}$
     • 现：$\sum_{k \in [i+1,n]} {j \choose x+1-j} A_i^jA_k^{x+1-j}$
     • $\Delta = $
   • $i$ 作为 $R$ 时
     • 原：$\sum_{x\in [1,i-1]} {x-j \choose j} A_x^{x-j}A_i^j$
     • 现：$\sum_{x\in [1,i-1]} {x+1-j \choose j} A_{x+1}^{x+1-j}A_i^j$

正确的思路：

1. 推式子题，先推式子。

2. 对于这种无序数对的题目，通常转化为有序数对会好做，于是我们定义：

   $T_x = \sum\limits_{l=1}^n \sum\limits_{r=1}^n (a_l+a_r)^x$.

3. 考虑 $T_x$ 与答案之间的关系。按照下标间的大小关系，可以将 $T_x$ 划分成 $3$ 类：$l<r,l=r,l>r$。其中，$l<r$ 的部分和 $l>r$ 的部分是对称的，且答案是 $l<r$ 的部分。

4. 于是有：$ans_x = \frac{T_x-\sum\limits_{i=1}^n(2a_i)^x}{2}$

5. 分开考虑，$T_x = \sum\limits_{l=1}^n \sum\limits_{r=1}^n\sum\limits_{k=0}^x{x \choose k} a_l^{x-k}a_r^k$

   提前和式：$T_x = \sum\limits_{k=0}^x \sum\limits_{l=1}^n \sum\limits_{r=1}^n {x \choose k} a_l^{x-k}a_r^k$

   提前变量：$T_x = \sum\limits_{k=0}^x {x \choose k}\sum\limits_{l=1}^n \sum\limits_{r=1}^n a_l^{x-k}a_r^k$

   分离变量：$T_x = \sum\limits_{k=0}^x {x \choose k} (\sum\limits_{l=1}^n a_l^{x-k}) (\sum\limits_{r=1}^n a_r^k)$

6. 分开考虑，$\sum\limits_{i=1}^n(2a_i)^x = 2^x \sum\limits_{i=1}^n a_i^x$

7. 预处理 $\sum\limits_{i=1}^n a_i^x$ 就可以了。

9.4

能力全面提升综合题单 Part 2.5

• P4995 跳跳：排序贪心，归纳法+交换论证好题。
• P1199 三国游戏：博弈题，自己玩一下就懂了。
• P2672 推销员：双关键字排序中，按其中一个关键字排序的类型。
  • 题意： 对 $x\in[1,n],\lvert C \rvert = x$ 求 $2 \times \max_{i \in C} S_i + \sum_{i \in C} A_i$ 的最大值。
  • 思考：
    1. 分析点贡献。要么贡献 $A_i$，要么贡献 $2S_i+A_i$。
    2. 双关键字贪心，考虑给其中一个关键字排序。按 $S$ 排序不行，按 $A$ 排序。
    3. 此时最优解分两种情况，取 $\max$ 即可。
       1. 前 $X$ 个全选。
       2. 在 $[X+1,n]$ 找一个 $j$ 替换 $X$。可以证明只需要找一个，因为找两个的话，让不是最大值的那个不换，结果一定不劣。
• P1080 国王游戏：序列上交换相邻两项只影响相邻两项，考虑临项交换法确定排序规则。
• P2123 皇后游戏：邻项交换得到的排序规则不满足严格弱序，先分组，再排序。

9.5

思维训练

AT_arc129_d

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。

你可以任意次数重复以下操作：

• 选择一个整数 $i$（$1 \leq i \leq N$），并分别对 $A_{i-1},A_i,A_{i+1}$ 加上 $-1,2,-1$。这里，$A_0$ 视为 $A_N$，$A_{N+1}$ 视为 $A_1$。

请判断是否可以将 $A$ 的所有元素都变为 $0$，如果可以，请求出所需的最小操作次数。

思路

1. 做过类似的 ICPC 题。首先注意到操作不会改变 $sum$，这个用来判无解。
2. 考虑线性 DP，值域很小，$f[i][j]$ 表示前 $i-1$ 项都是 $0$，第 $i$ 项等于 $j$ 的最小操作次数。
3. 简化约束。若没有环约束如何转移？
   1. 枚举上一个数的取值，$dp[i][a[i] +2j] = dp[i-1][j]+j$
4. 考虑处理环形：
   1. 扩环成链：不行
   2. 规定起点位置：不行
5. 尝试摸性质。考虑下界。
6. 对于 $a_i<0$ 的点，至少需要在它身上进行 $\frac{-a_i+1}{2}$ 次操作。
7. 每一轮将 $<0$ 的点提升，至多进行多少轮？肯定是不多的，直接暴力吗，这样是最优的吗？

9.6

VP CF 1117 Div.2

A

题意

定义 句子缩写 为单词首字母大写后相连，求用 $n$ 个单词，能否恰好构成 $m$ 个缩写，顺序不限。

$n,m \le 100$，$\sum$ 字符长度 $\le 5 \times 10^4$

思考

1. 剔除无用元素，只有首字母有用。
2. 切换视角，$\mathit{cnt}[i]$ 表示 $i$ 这个字符开头的单词有多少个，判断能否构成某个缩写，实际上就是判断缩写的每一位出现次数是否小于等于 $\mathit{cnt}[$ 这一位 $]$，之后再将 $\mathit{cnt}[$ 缩写开头 $] \mathrel{+}= 1$。
3. 一个暴力的做法，能拼出的就拼出，重复 $m$ 轮。时间复杂度好像对。
4. 做法假了，因为如果某一位不够，随便找一个以这一位开头的单词，让它形成缩写，就可以让这一位增加。
5. 因此只有某一位不存在的情况，才会使得这个缩写不能被拼出。无解的情况就是缩写用到了一个没出现过的字符（令某一位从 $0 \to 1$ 的唯一方法是找一个以这一位为开头的缩写，但是这样的缩写一定不能被拼出）。
6. 用时 $37$ 分钟（

B

题意

两个人 $A$，$B$ 在博弈，各自有一个非严格递减序列 $a,b$。初始时都站在第 $1$ 项上。

每一轮里，若 $A$ 前面的项 $>$ 当前项，移动一项；$A$ 当前项 $-1$。$B$ 同理。

若 $A$ 到达了最后一项，且这一位的数值 $= 0$，则 $A$ 失败。

$A$ 先手。问谁赢。

思考

1. 博弈题，但是不会产生决策，所以实际上是模拟题。
2. 计算每个人能撑过几个 $-1$ 即可。
3. 用时 $18$ 分钟

C

题意

以 $1$ 为根的有根树有 $n$ 个节点。给定点集 $A$ (大小为 $m$) 和边集 $C$，要求对于任意两个点 $x,y \in A$，都有 $\operatorname{Path}(1,x),\operatorname{Path}(1,y)$ 与边集 $C$ 的交集不同。

求最小边数并输出边集 $C$。

$m \le n \le 10^5$

赛时思路

1. 构造题，先考虑下界。对于任意两个点 $x,y \in A$，令 $p = \operatorname{lca}(x,y)$，则 $\operatorname{Path}(p,x),\operatorname{Path}(p,y)$ 上至少有 $1$ 条边集上的边。这里着急了，直接去构造最优解了，没有真的考虑下界是 $m$。
2. 树上问题，先从点的角度看。
   1. 把 $\operatorname{Path}(1,x)$ 视作序列，则问题转化为：$k$ 个序列，选定一些项，使得序列之间两两不同。$1$ 个项可以区分两类点。一类是在这条边下面的，另一类是外面的。
   2. 想象这个过程，一开始是一团，选了一个项之后，裂成两团，再选，再裂。
   3. 没啥想法了。
3. 再从边的角度看。
   1. 一条边能区分可以区分两类点。一类是在这条边下面的，另一类是外面的。因此至少需要 $\log m$ 次操作。能否达到这个下界呢？样例好像佐证了这点，尝试构造！
4. 事实是无法达到下界，失败了。
5. 用时 $31$ 分钟。

正确思路

1. 构造题考虑下界。在每个点上方选边显然能成，用掉 $m$ 条边。
2. 发现有一个点可以没有边标记，最优做到 $m-1$。因为一条边只能区分一个连通块内的两类点，相当于每次将连通块个数 $+1$，最终要形成 $m$ 个块，最少就是 $m-1$ 条边。

D

题意

目标矩形的面积是 $S$，边长是正整数。处理 $q$ 次查询，问 $(\le x,\le y)$ 内有多少个可能是目标矩形的点。

$S \le 10^{14}, q \le 3 \times 10^5$

赛时思路

1. 几何理解一下目标矩形的覆盖范围，是对称的，数据范围暗示了与 $\sqrt{S}$ 有关。到这里都是对的。
2. 查询可以离线，数据范围暗示排序。这里就没有发现可以枚举所有矩形，所以想歪了。
   1. 尝试先按 $x$ 排序询问。没啥用啊。
   2. 按 $y$ 排序。对称的，也没用。
3. 多出来的 $\log$ 是在暗示神秘分治吗。
4. 没思路了，用时 $17$ 分钟。

正确思路

1. 直接枚举每个矩形（$W_i \times H_i$），考虑每个矩形的贡献就可以了。
2. 逐步添加约束
   1. 倘若 $x$，$y$ 无限大，每个矩形贡献 $(W_i - W_{i-1}) \times H_i$
   2. 加入 $x$ 约束，找到第一个 $W_i \ge x$，前面的前缀和加上，当前这一个贡献 $(x - W_{i-1}) \times H_i$
   3. 加入 $y$ 约束，找到最后一个 $H_j \ge y$，$[j+1,i-1]$ 范围内前缀和做，$[1,j]$ 范围内贡献 $y$，$i$ 贡献 $(x - W_{i-1}) \times \min(y,H_i)$

VP CF 1118 Div.2

A

题意

长度为 $n$ 的序列，每一次操作可以选择 $2k+1 \ (1 \le k)$ 个递增下标，删除其中第 $k+1$ 个下标。

求最终序列 $\gcd$ 的最大值。

思考

1. $\gcd$ 只会越来越小，所以删除的数越多越好。
2. 本质上我可以删除除了第 $1$ 项和第 $n$ 项之外的所有项，通过 $k=1$。
3. $\gcd(a_1,a_n)$ 就是答案。
4. 用时 $14$ 分钟。

B

题意

长度为 $n$ 的数组 $a$，每次操作选择一些 $\ge x$ 的项，将其裂成 $x$ 和 $a_i-x$ 这两项。

进行 $k$ 次操作，最大化某个相同项的个数。

$n,m,a_i \le 2 \times 10^5$

Eazy version 的赛时思路

1. 值域很小，枚举值 $i$。
   1. 用 $x=i$ 操作，新增个数是大于 $x$ 的项的个数，和等于 $2x$ 的项的个数。
   2. 用 $x=k$ 操作，新增个数是 $a_j - k = i$ 的项的个数，即等于 $i+k$ 的个数。取后缀最大值即可。想到这里就直接去写代码了，不应该这么急，应该发现第二种情况一定劣于第一种，这也是后来 Hard version 没思路的原因。
2. 用时 $18$ 分钟。

Hard version 的赛时思路

1. 延续 Eazy version 的思路，枚举值 $i$
   1. 用 $x=i$ 操作 $q$ 次，大于等于 $x$ 的项贡献 $1$ 个，大于等于 $2x$ 的项贡献 $2$ 个。。。如果 Eazy version 想对了，这里继续想下去说不定可以想到解法
   2. 用 $x=y$ 操作 $q$ 次，等于 $i+y$ 的贡献 $1$，等于 $i+2y$ 的贡献 $1$。。。这个 $y$ 好像又有贡献，不太好弄啊。放弃了。

正确思路

1. 枚举值域是正确的，但是要发现，用 $x=i$ 操作一定比 $x=y$ 更优。
2. 考虑比 $i$ 大的数在数轴上形成一段，直观上，每次用 $2^px$ 切最多，$0\le p \le k-1$。（一分为二）
3. 因此 $k$ 的有效取值其实很少，只用枚举 $k \le 20$ 的部分（样例也能看出来）。
4. 考虑每个 $a_j$ 的贡献，当 $a_j \le i\times2^k$ 时，贡献 $\lfloor \frac{a_j}{i} \rfloor$ 块，当 $a_j > i\times 2^k$ 时，贡献 $2^k-1$ 块。
5. $a_j > i\times 2^k$ 很好统计，枚举 $i$ 的倍数处理 $a_j \le i\times2^k$ 的贡献。

贪心专题训练

Destroyer Takahashi

题意

$n$ 个区间 $[l,r]$，$l,r \le 10^9$。你可以通过一次操作清除与 $[x,x+d-1]$ 有交的所有区间。问最小操作次数。

$n \le 2 \times 10^5$

思考

1. 不难发现这是区间选点的 plus 版，区间选区间。
2. 按右端点升序排序，若选择区间的右端点无法覆盖当前区间的左端点，则在当前区间的右端点选一个长度为 $d$ 的区间。
3. 使用调整法证明：
   1. 在一个最优解的选择区间集合里，找到第一个不是以题目区间的右端点作为开头的选择区间。
   2. 若将当前选择区间右移会产生影响，则必然存在一个题目区间被当前区间唯一覆盖，且题目区间的右端点大于选择区间的左端点，此时令选择区间的左端点 $=$ 题目区间的右端点必然不劣。

Same Sum Blocks (Hard)

题意

长度为 $n$ 的序列里选尽可能多的区间，这几个区间不能相交，且区间和相等。

$n \le 1.5 \times 10^3, -10^5 \le a_i \le 10^5$

思考

1. 子段和约束，感觉像是二分答案。
   1. 二分区间和：函数没啥性质
   2. 二分区间数：有单调性，跑个二维 DP？那二分就没用了啊。
2. 考虑 DP。
   1. 定义：$f_{i,j}$ 表示，前 $i$ 项，最多有多少个区间和 $= j$ 的不重叠区间？
   2. 转移：$f_{i,j} = \max(f_{i-1,j},\ f_{k,j} + 1)$，要求 $s_i - s_k = j$ 也就是 $s_k = s_i - j$。
   3. 优化：
      1. 这个 DP 是有单调性的，用 $k$ 最大的那个转移就好了，用 $\text{map}$ 维护。
      2. 对于点 $i$，能够形成的不同区间和至多 $i$ 个。
      3. 用二维 $\text{map}$ 存 DP 避免爆空间。时间复杂度 $O(n^2 \log n)$ 可以通过。
3. 好像理论正确？但这是贪心专题啊（逃

正确思路

1. [疑惑] 神秘转化：将所有区间按照 区间和 分组，每一组内的问题转化为：最大不相交区间
2. 取右端点最小的区间就好了。

Cleaning Shifts S

最小区间覆盖模板题，有两种做法。

• 贪心地选左端点小于等于 $R$ 的区间中，$r$ 最大的区间。$O(n \log n)$。
• [疑惑] 还有一种巧妙地做法是图论建模。将 $l-1$ 与 $r$ 连一条边权为 $1$ 的边，$i$ 与 $i-1$ 连一条边权为 $0$ 的边，跑 $01$ BFS，这样跑出来的 $\mathit{dis}_i$ 的意义就是，“覆盖 $[1,i]$，需要的区间数”。$O(n+T)$。

国旗计划

题意

长度为 $m$ 的圆，顺势针编号。有 $n$ 个区间，问，对于每一个区间，固定选择它后，最少区间覆盖。（注意 $[1,2]$ 和 $[3,4]$ 这两个区间没有覆盖 $[1,4]$）。

思考

1. 环上区间覆盖，做过类似的题目，扩环成链后钦定起点倍增即可。
2. 唯一的问题是这题的 $M$ 特别大，离散化一下就好了。
3. 还有一个细节，就是这题跨越边界的区间也要扩环。