CF678(EDU13) 题解 \/ 李超线段树学习笔记

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-03 23:02:24

:::::info[闲话] 记 $a,b,c,d,e,f$ 为我分别在 $A,B,C,D,E,F$ 上花的时间，那么 $a+b+c+d+e<f$。
:::::

A. Johny Likes Numbers：

:::::info[题目基本信息] 考察：数学（$\color{#FE576A}800$）。
题目简介：
给你两个正整数 $n,k$，求一个最小正整数 $x$ 满足：

$k|x$
$x>n$

数据范围：

$1\le n,k\le 10^9$ ::::: 容易发现这个 $x$ 的前一个被 $k$ 整除的数 $y$ 就是 $y\le n$ 时的最大值，那么最后答案就是： $$\begin{aligned}x&=y+k\&=\frac{y}{k}\cdot k+k\&=(\frac{y}{k}+1)k\&=(\lfloor\frac{n}{k}\rfloor+1)k\end{aligned}$$ 时空复杂度均为 $\Theta(1)$。

B. The Same Calendar：

:::::info[题目基本信息] 考察：数学（$\color{#FFC116}1600$）。
题目简述：
给你一个年份 $y$，求下一个年份 $y'$，使得这两年的日期在日历上的排布相同。
数据范围：

$1000\le y<100000$ ::::: 容易发现，两年的日期在日历上的排布相同的充要条件是：
两年天数相同。
两年第一天的星期几相同。

第一个条件直接根据平年和闰年的定义判断即可，第二个条件需要进行转化：
设这一年的第一天为星期 $X$（为了方便，我们设星期天为星期 $0$，也就是说此处 $X\in[0,6]$），那么符合条件的下一年也应为星期 $X$，设此时一共过了 $Y$ 天，也就是说：
$$X\equiv X+Y\pmod 7$$ 即：
$$Y\equiv0\pmod7$$ 所以，我们直接从这一年开始，暴力向下枚举即可。
容易发现两年不会隔太远。
:::::success[证明] 容易发现，平年天数 $365\bmod7=1$，闰年天数 $366\bmod7=2$，我们不妨以 $4$ 年为一整体，那么含闰年的整体天数对 $7$ 取模的余数为 $5$，不含的余数为 $4$，且根据闰年定义，$4$ 与 $4$ 之间相隔二十多个整体。
那么如果全是 $5$，循环 $7$ 次即可；如果有一个 $4$，最多循环十几次。所以不可能出现两个 $4$。
证毕。
::::: 时空复杂度均为 $\Theta(1)$。

C. Joty and Chocolate：

:::::info[题目基本信息] 考察：数学，贪心（$\color{#FFC116}1600$）。
题目简介：
有一列长度为 $n$ 的地砖，编号为 $1$ 到 $n$，编号是 $a$ 的倍数的可以涂成红色并获得 $p$ 的价值，编号是 $b$ 的倍数的可以涂成蓝色并获得 $q$ 的价值，一个地砖只能涂成一种颜色，问最大价值是多少。
数据范围：

$1\le n,a,b,p,q\le 10^9$ ::::: 容易发现若一个地砖的编号既是 $a$ 的倍数，又是 $b$ 的倍数，那么它肯定会被涂成价值更大的颜色。
所以我们不妨钦定 $p\ge q$，不然我们直接交换颜色。
此时涂成红色显然更优，所以有 $\displaystyle\lfloor\frac{n}{a}\rfloor$ 的地砖会涂成红色，剩下的地砖中未被涂色的 $\displaystyle\lfloor\frac{n}{b}\rfloor-\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor$ 个地砖会被涂成蓝色，那么最后答案就是： $$\lfloor\frac{n}{a}\rfloor\cdot p+(\lfloor\frac{n}{b}\rfloor-\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor)\cdot q$$ 时空复杂度均为 $\Theta(1)$。

D. Iterated Linear Function：

:::::info[题目基本信息] 考察：矩阵快速幂（$\color{#52C41A}1700$）。
题目简介：
定义函数 $f(x)=Ax+B$，定义函数 $g^{(n)}(x)$ 为：
$$g^{(n)}(x)=\begin{cases}x&n=0\f(g^{(n-1)})&\text{otherwise}\end{cases}$$ 求 $g^{(n)}(x)$ 的值对 $10^9+7$ 取模的结果。
数据范围：

$1\le A,B,x\le 10^9$
$1\le n\le 10^{18}$ ::::: 容易发现，$n$ 的数据范围过大，无法支持 $\Theta(n)$ 的时间复杂度，所以我们考虑优化。
对于这种递推方程式，除了直接化简就是采用矩阵加速，在此题中两种方法均可，下面是矩阵加速的方法，因为它思维量少（……真的吗？）。
我们注意到，在递推式 $g^{(n)}(x)=f(g^{(n-1)}(x))=Ag^{(n-1)}(x)+B$ 中有两个单项式，分别是 $g^{(n-1)}(x)$ 和 $B$，那么我们开矩阵存的就是他们。那么最初始矩阵就为： $$\begin{bmatrix}g^{(n-1)}(x)\\B\end{bmatrix}$$ 现在我们要得到： $$\begin{bmatrix}g^{(n)}(x)\\B\end{bmatrix}$$ 假设要乘的矩阵为 $base$，那么我们得到： $$base\times\begin{bmatrix}g^{(n-1)}(x)\\B\end{bmatrix}=\begin{bmatrix}g^{(n)}(x)\\B\end{bmatrix}$$ 容易得到： $$base=\begin{bmatrix}A&1\&1\end{bmatrix}$$ 根据矩阵乘法的结合律会得到最终答案矩阵 $ans$ 就为： $$ans=\begin{bmatrix}A&1\&1\end{bmatrix}^n\times\begin{bmatrix}x\\B\end{bmatrix}$$ 答案就是 $ans$ 的左上角元素。
时间复杂度为 $\Theta(\log n)$，空间复杂度 $\Theta(1)$。

E. Another Sith Tournament：

:::::info[题目基本信息] 考察：状压 DP（$\color{#52C41A}2200$）。
题目简介：
有 $n$ 个人在进行 $n-1$ 轮比赛，每轮有两个人进行斗争，败者淘汰，胜者在擂台上与下一轮的另一人斗争。已知第 $i$ 个人与第 $j$ 个人斗争时第 $i$ 个人获胜的几率是 $a_{i,j}$，问第 $1$ 个人在可以排布比赛顺序的情况下他获胜的最大概率是多少。
数据范围：

$1\le n\le 18$
$\forall i,j\in[1,n],0\le a_{i,j}\le 1$
$\forall i\in[1,n],a_{i,i}=0$
$\forall i,j\in[1,n],i\ne j,a_{i,j}+a_{j,i}=1$ ::::: :::::info[闲话] 听说这题后来被贪心爆标了。
::::: 注意到 $1\le n\le 18$，那么我们考虑状压 dp。
先设 $f_p$ 为场上存活状态为 $p$ 的概率时第 $1$ 个人获胜的概率。
但是这样设状态会有 bug，所以我们设 $f_{p,i}$ 为场上存活状态为 $p$ 且擂台上是第 $i$ 个人时第 $1$ 个人获胜的概率。 :::::success[对于状态设计的一点说明] 其实设 $f_{p,i}$ 为参与过争斗状态为 $p$ 且擂台上是第 $i$ 个人时第 $1$ 个人获胜的概率也可以，但是参与过争斗的状态、擂台上的人、存活状态知二求一，所以这两种其实等价。
::::: 然后我们发现如果 $p$ 从大往小推时，$1$ 淘汰时不好处理边界，所以我们令 $p$ 从小往大推。
最开始令 $f_{\{1\},1}\leftarrow1$。
然后我们容易得到状态转移方程： $$f_{p,i}=\max_{j\in p,j\ne i}(f_{\complement_p\{j\},i}\cdot a_{i,j}+f_{\complement_p\{i\},j}\cdot a_{j,i})$$ 最后答案就为： $$\max_{i=1}^n(f_{\bigcup_{j=1}^n\{j\},i})$$ 时间复杂度为 $\Theta(2^nn^2)$，空间复杂度为 $\Theta(2^nn)$。

F. Lena and Queries：

:::::info[题目基本信息] 考察：动态开点，李超线段树，计算几何（$\color{#9D3DCF}2500$）。
题目简介：
有 $3$ 种 $n$ 个操作，分别是：

向集合 $S$ 中加入数对 $(x,y)$。
删除集合 $S$ 中在第 $k$ 次操作加入的数对。
给定 $k$，求 $\displaystyle\max_{(x,y)\in S}(kx+y)$。