本文章由 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$ 满足：

1. $k|x$
2. $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$ 个操作，分别是：

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

数据范围：

• $1\le n\le 3\times 10^5$ ::::: 容易发现，如果没有操作 $2$ 就是李超线段树板子，但是现在有操作 $2$ 了李超线段树就做不了了，同时我们也不想上几乎万能但超级难写的平衡树，怎么办呢？
  注意到这道题比李超线段树板子少了一个强制在线的限制，所以我们考虑离线下来。
  离线下来之后莫队显然时间复杂度不理想，再加一个李超线段树板子维护就是 $\Theta(n\sqrt n\log n)$，不太能跑。
  那么我们考虑对操作编号开一棵线段树，对于每个数对容易维护他们出现的区间，在线段树上跑给 $\Theta(\log n)$ 个点挂上数对，然后在这一个点上开一棵动态开点的李超线段树，对于不同值域维护答案即可。
  对于操作 $3$，我们可以直接找到此时的操作对应的叶子结点，不断往上蹦不断查询即可。
  时间复杂度为 $\Theta(n\log^2n)$，空间复杂度为 $\Theta(n\log n)$。 :::::warning[坑点] 由于此做法空间复杂度为 $\Theta(n\log n)$ 且空间常数较大，所以要关 long long，只在统计答案时开 long long，同时也不要在节点内存 $l$ 和 $r$，节约空间。
  :::::

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

:::::info[闲话] KSCD_ 大神/bx/bx

270pts，感觉打得还不错。
赛后补了 T1,T3。
:::::

A. 缥缈愿：

:::::info[题目基本信息] 考察：数学。
题目简介：
给定 $\{a_n\}$ 和 $k$，求：
$$\max_{l=1}^n\max_{r=l-1}^n\gcd(\gcd_{i=1}^la_i,\gcd_{i=l}^r(a_i+k),\gcd_{i=r+1}^na_i)$$ 数据范围：

• $1\le n\le 6\times 10^5$
• $1\le k\le 10^{18}$
• $\forall i\in[1,n],1\le a_i\le 10^{18}$ ::::: :::::info[考场做法] 乱搞。如果当前前面部分的 $\gcd$ 在 $[1,10^{17}]$ 范围内就进行枚举质因子判断可行性贪心，否则就暴力排除以最前面还未枚举的数开始的区间为被操作区间，记录进答案。 时间复杂度是玄学，拿了 95pts，由于剩余的 5pts 性价比太低就没有继续写。
  ::::: :::::success[正解] 由于前缀后缀 $\gcd$ 只有 $\log V$ 种取值，所以不妨枚举取值对于不同取值贪心 $\Theta(n+\log V)$ 求最大的 $\gcd$，记进答案。
  时间复杂度 $\Theta(n\log^2V+\log^3V)$，空间复杂度为 $\Theta(n)$。
  :::::

B.虚构义：

:::::info[题目基本信息] 考察：ST 表，线段树，猫树，最小生成树，常数优化。
题目简介： $h$ 个点 $n$ 条边的无向带权图，$q$ 次询问，求编号为 $[l,r]$ 的边的最小生成树。
数据范围：

• $1\le n,q\le 5\times 10^5$
• $1\le h\le\color{red}10$ ::::: :::::success[赛时做法（正解）] 注意到只有 $\displaystyle\frac{h(h-1)}{2}=45$ 种端点不同的边，同时端点不同的边显然取边权最小的，所以我们可以用 ST 表维护（由于空间和时间卡，所以我们要用指针动态开 ST 表，既节省空间常数，也节省时间常数），然后每次询问直接 Kruskal/Prim 做即可。
  时间复杂度为 $\Theta(n\log n+qh^2\log h)$，空间复杂度为 $\Theta(n\log n+h^2)$。
  :::::

C. 短恨歌：

:::::info[题目基本信息] 考察：组合数学。
题目简介：
一棵 $n$ 个点的树上有 $k$ 个黑点，求有多少种可能使得到所有黑点的距离和最小的点唯一（对 $998244353$ 取模）。
数据范围：

• $1\le k\le n\le 10^6$ ::::: :::::info[赛时做法] 暴力加性质，45pts。
  ::::: :::::success[正解] 注意到 $k$ 为奇数时任意放黑点均合法，直接输出 $\displaystyle\binom{n}{k}$。
  否则，直接正难则反，注意到这些点构成一条路径，不妨继续正难则反，求出所有存在大于 $1$ 的路径的最近公共祖先的方案数，然后用所有是符合条件的点方案数的总点数减它，再用总方案数减它即可，代码并不难写。
  时间空间均线性。
  :::::

T4 最后还有 30pts，是一个单侧递归线段树，并不想写，也不会。

KSCD_ 大神/bx/bx

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-14 22:37:01

A. k-th divisor：

:::::info[题目基本信息] 考察：数学，数论（$1400$）。
题目简介：
给定 $n,k$，求 $n$ 的第 $k$ 大因子，若不存在输出 -1。
数据范围：

• $1\le n\le 10^{15}$
• $1\le k\le 10^9$ ::::: 注意到 $n$ 的因数 $p$ 一定满足以下条件之一：

1. $p\le\sqrt n$
2. $\displaystyle\frac{n}{p}\in \mathbb Z_+,\frac{n}{p}\le\sqrt n$

所以我们枚举 $p$ 和 $\displaystyle\frac{n}{p}$，判断因数模拟即可。
时间复杂度为 $\Theta(\sqrt n)$，空间复杂度为 $\Theta(1)$。
:::::warning[坑点] 当 $p=\sqrt n$ 时 $p$ 和 $\displaystyle\frac{n}{p}$ 会算两次，要减去。
:::::

B. USB vs. PS/2：

:::::info[题目基本信息] 考察：贪心，排序，堆排序（$1400$）。
题目简介：
你有 $a+b+c$ 台电脑，$a$ 台只有 USB 端口，$b$ 台只有 PS\/2，$c$ 台两种都有。有 $m$ 个鼠标，他们分别能匹配 USB 或 PS\/2 端口（电脑和鼠标只能一一匹配），代价分别为 $\{val_m\}$，问在能匹配最多的电脑的情况下，这个值和最小代价分别是多少。
数据范围：

• $0\le a,b,c\le 10^5$
• $0\le m\le 3\times 10^5$ ::::: 注意到一个显然的贪心策略：优先匹配只能匹配一种端口的电脑。 :::::success[证明] 如果先将两种端口都可匹配的电脑匹配到 USB 鼠标上，那么后面可能出现的仅能匹配 USB 鼠标的电脑可能就因为缺少 USB 鼠标而无法匹配。
  PS\/2 端口同理。
  ::::: 所以我们优先按这个策略匹配，贪心地匹配 $val_i$ 较小的鼠标，可以使用排序或优先队列实现。
  时间复杂度为 $\Theta(a+b+c+m\log m)$，空间复杂度为 $\Theta(a+b+c+m)$。

C. Two strings：

:::::info[题目基本信息] 考察：二分，双指针。
题目简介：
给定字符串 $s,t$，从 $t$ 中删除一段最短子串，使得 $t$ 是 $s$ 的子序列，给出删除子串后的 $t$，若 $t$ 为空输出 -。
数据范围：

• $1\le |s|,|t|\le 10^5$ ::::: 先考虑完全暴力，枚举删除子串的左右端点，然后通过双指针（好吧好像也不是完全暴力）判断可行性，时间复杂度为 $\Theta(|t|^3)$。
  注意到删除一段子串后肯定剩下一段前缀和一段后缀，所以我们考虑对于每个前缀和后缀分别计算答案。
  设 $f_i$ 为 $t$ 的长度为 $i$ 的前缀作为子序列在 $s$ 中出现的最小右端点，$g_i$ 同上，只不过是反串在反串前缀中匹配，这个显然可以线性维护。
  然后显然最后的答案是在求最小值，且大于等于最小值的都可行，所以我们可以进行二分答案，二分最后的删除长度，然后枚举删除子串的左端点判断即可。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

D. Maximum path：

:::::info[题目基本信息] 考察：贪心，动态规划 DP，DP 优化（$2300$）。
题目简介：
给定一个 $3\times n$ 的矩阵 $a_{i,j}$，这是每个格子的权值，每次你可以移动到你所在位置的四联通格，但不能重复经过同一个格子，问从 $(1,1)$ 到 $(3,n)$ 的所有路径上的格子的权值和最大是多少。
数据范围：

• $1\le n\le 10^5$
• $\forall i\in\{1,2,3\},j\in[1,n],|a_{i,j}|\le 10^9$ ::::: 注意到如果我们仍然像往常一样朴素设状态 $f_{i,j}$ 为走到 $(i,j)$ 格的路径权值和的最大值并且朴素转移的话，DP 就会出现后效性，我们注意到本题中矩阵是 $3\times n$ 的，$3$ 这个数或许会带来一些性质，我们不妨考虑优化状态转移方程。
  下面是一些性质：

1. 第 $1$ 行和第 $3$ 行本质是一样的，可以归为一类讨论。 :::::success[证明] 轴对称一下即可，显然成立。
   :::::

2. 当我们处于旁边两行时，我们不能往回走。 :::::success[证明] 注意到从旁边走回去后就回不来了，所以我们不能往回走。
   证毕。 :::::

3. 我们最多会连续往后走一格。 :::::success[证明]

   • 当连续往回走的步数为偶数格时：
     上面是唯一一种情况。
     容易发现它可以被如此替代：
   • 当连续往回走的步数为奇数格时： 容易发现它可以被如此替代：

   证毕。
   :::::

根据性质 2,3 可知，我们 DP 要讨论的情况数实际并不多，这时 DP 就没有后效性了。
时空复杂度均为 $\Theta(n)$。

E. Radio stations：

:::::info[题目基本信息] 考察：线段树，树状数组，cdq 分治。
题目简介：
给定 $n,k$ 以及 $\{x_n\},\{r_n\},\{f_n\}$，求满足下列条件的 $(i,j)$ 的个数：

• $1\le i<j\le n$
• $|x_i-x_j|\le\min(r_i,r_j)$
• $|f_i-f_j|\le k$

数据范围：

• $1\le n\le 10^5$
• $0\le k\le \color{red}10$
• $\forall i\in[1,n],1\le x_i,r_i\le 10^9$
• $\forall i\in[1,n],1\le f_i\le 10^4$ ::::: 注意到 $|x_i-x_j|\le\min(r_i,r_j)$ 条件中有 $\min$ 不好处理，所以我们可以将这些点按 $r_i$ 降序排序，这样就可以消掉 $\min$。
  然后注意到 $k\le 10$，所以我们可以对于每个 $f_i$ 分别处理贡献。
  那么现在我们需要支持单点修改区间查询和，由于值域为 $10^9$ 所以我们要上动态开点线段树。
  然后就做完了，数据结构好啊。
  时间复杂度为 $\Theta(nk\log V)$，空间复杂度为 $\Theta(n\log V)$。

F. Tree nesting：

:::::info[题目基本信息] 考察：图论，逆元，树形 DP，状压 DP（$2800$）。
题目简介：
给定两棵树 $S,T$，求 $S$ 有多少个连通子图与 $T$ 同构。
数据范围：

• $1\le |S|\le 1000$
• $1\le |T|\le\color{red}{12}$ ::::: 同构概念
  注意到 $|T|\le 12$，考虑状压 dp。
  同时又在树上做，考虑树形 dp。
  注意到题目问的是 $S$ 到 $T$ 的同构子图数，而不是 $S$ 的同构子图到 $T$ 的总同构数，直接 dp 肯定会算重。 :::::success[解决方案] 显然，$S$ 的所有同构子图到 $T$ 的同构数都相同，都是 $T$ 到 $T$ 的同构数。
  所以我们要求 $S$ 到 $T$ 的同构子图数，不妨求出 $S$ 的同构子图到 $T$ 的总同构数，再除以 $T$ 到 $T$ 的同构数。
  ::::: 那么现在我们要求 $S$ 的同构子图到 $T$ 的总同构数和 $T$ 到 $T$ 的同构数，容易发现两者可以用类似的方法做，不妨以求 $S$ 的同构子图到 $T$ 的总同构数为例。
  猜测时间复杂度是 $\Theta(|S||T|2^{|T|})$ 的。
  钦定 $S$ 为有根树，根为 $1$，$T$ 为无根树，不妨设 $f_{u_s,T',u_t}$ 为在 $S$ 上以 $u_s$ 为根的子树的所有连通子图（必包含 $u_s$）同构到 $T$ 上以 $u_t$ 为根的集合为 $T'$ 的连通子图的总同构数。
  为了方便求 $f_{u_s,T',u_t}$，我们不妨预处理出在 $T$ 上对于每个点为根时每个子节点的子树内节点构成的集合，以 $u$ 为根子节点为 $v$ 时 $v$ 子树内的节点集合记为 $g_{u,v}$，记 $S$ 和 $T$ 的 $u$ 的邻边集合为 $gs_u$ 和 $gt_u$。
  显然 $S$ 的一个点可以同构到 $T$ 的一个点，所以初始时要令 $f_{u,\{v\},v}\leftarrow 1$，然后状态转移方程式就为： $$f_{us,T',ut}\leftarrow f_{us,T',ut}+\sum_{vs\in gs_{us}}\sum_{vt\in gt_{ut}}f_{us,\complement_{T'}(T'\cap g_{ut,vt}),ut}\times f_{vs,T'\cap g_{ut,vt},vt}$$ 注意这里是为了方便展示状态转移方程，为了防止后效性，枚举顺序如下：

1. dfs 枚举 $us$。
2. 枚举 $vs\in gs_{us}$。
3. 枚举 $T'$，从大到小枚举。
4. 枚举 $ut$。
5. 枚举 $vt$。

这样最后答案就是 $\displaystyle ans\leftarrow\sum_{i=1}^{|S|}\sum_{j=1}^{|T|}f_{i,\bigcup_{p=1}^{|S|}\{p\},j}$。
然后对两个问题分别做一遍，用快速幂算答案即可。
时空复杂度均为 $\Theta(|S||T|2^{|T|})$。
:::::warning[坑点] 本题相当卡空间，尽量少开 long long。
:::::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-25 13:14:37

[ABC368G] Add and Multiply Queries

题目考察：set（STL），树状数组。
题目简述：
给你两个序列 $\{a_n\},\{b_n\}$，有 $q$ 次操作，每个操作可能是以下三种之一：

1. 将 $a_{pos}$ 改为 $x$。
2. 将 $b_{pos}$ 改为 $x$。
3. 设 $f_i(x)$ 为 $\max(x+a_i,x\times b_i)$，给你区间 $[l,r]$，求 $ans=f_r(f_{r-1}(\dots(f_{l+1}(f_l(0)))))$。

数据范围：

• $1\le n,q\le 10^5$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^9$
• 在 $1,2$ 操作中，$1\le pos\le n$
• 在 $1,2$ 操作中，$1\le x\le 10^9$
• 在 $3$ 操作中，$1\le l\le r\le n$
• 在 $3$ 操作中，$1\le ans\le 10^{18}$

乍一看这道题既不满足前缀和的性质，也不满足 ST 表的性质，非常不可做。

实际上我们发现在 $x\in[l,r]$ 的点中 $b_x>1$ 的最多只有 $60$ 个（因为 $ans\le 10^{18}$）。
那么我们将加的数扔进树状数组里，将大于一的乘的数的下标扔进 set 里，查询的时候暴力去找第一个非 $1$ 的乘的数，用树状数组去求前面的和就可以了。

时间复杂度为 $\Theta(n\log V\log n)$（$V$ 是 $ans$ 的值域）。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-01 19:18:59

有人吐槽我题解太水了，这次我就写多点。

[ABC369G] As far as possible

题目考察：图论，长链剖分。
题目简述：
给你一棵 $n$ 个点的带权的树，$n$ 次询问，第 $i$ 次询问要求找出序列 $\{x_{i+2}\}$，该序列要满足以下条件：

• $\forall j\in[3,i+1],k\in[2,j-1],x_j\ne x_k$。
• $x_1=x_{i+2}=1$。

问对于所有的序列中，$\displaystyle\sum_{j=1}^{i+1}\text{dist}(x_j,x_{j+1})$ 最大是多少。
其中，$\text{dist}(a,b)$ 代表 $a$ 点到 $b$ 点的最短距离。
数据范围：

• $2\le n\le 2\times 10^5$
• $\forall i\in[1,n-1],1\le u_i,v_i\le n$
• $\forall i\in[1,n-1],1\le w_i\le 10^9$

设树中有 $num$ 个叶子结点，答案序列为 $\{ans_n\}$，则对于 $i\in[1,n]$，$ans_i$ 有以下两种情况：

• $i\le num$，则必然全选叶子结点。
  简单证明：若有一个不选叶子结点，则选它的子节点必然更优。
• $i>num$，则 $ans_i=ans_{num}$。
  简单证明：对于任意一个非叶子结点，选他的子树内的叶子节点的返回（或进入）的时候顺路就把他选了。

那么我们贪心的想，对于某个值最大的肯定要先选，那么这个某个值是什么值呢？
肯定不是深度，因为我们去到那个点不一定要回到 $1$ 号点。
深度不行，那相对某个点的深度呢？
这个是可以的，但复杂度过高。（因为你不知道某个点是哪个点）
最终我们定义 $dep_x$ 如下：

• 若 $x$ 点被遍历，则 $dep_x=0$。
• 否则设其父节点为 $fa$，则 $dep_x=dep_{fa}+\text{dist}(x,fa)$。

但是这样定义就无法知道所有点与它的距离了，所以我们尝试反向定义：$dep_x$ 代表他所在的子树内离他最远的点与他的距离，转移方程为：（设 $s_x$ 为 $x$ 点的儿子集合）： $$dep_x=\max_{y\in s_x}(dep_y+\text{dist}(x,y))$$ 这样就知道最大的点与他的距离了，而且由于上述的贪心策略，$dep_x$ 最大的肯定最先走，设 $son_x$ 为抵达 $x$ 点后最先走的点，那么不是他的父节点 $fa$ 的 $son_{fa}$ 的点 $x$ 肯定在他遍历完父节点 $fa$ 的 $son_{fa}$ 后还没遍历他 （废话），则他能贡献 $dep_x+\text{dist}(x,fa)$。

这样这个题就做完了，时间复杂度为 $\Theta(n)$。
代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-02 19:05:29

[ABC373F] Knapsack with Diminishing Values

题目考察：背包。
题目简述：
给你一个背包和 $n$ 个物品，第 $i$ 个物品代价为 $w_i$，价值为 $v_i$，数量为 $1145141919810$，出题人为了让这个题变难设你选择第 $i$ 个物品 $k$ 次，那么他会将你获得的价值变为 $kv_i-k^2$。在代价不大于 $w$ 的基础上，求你获得的最大价值。
数据范围：

• $1\le n,w\le 3000$
• $\forall i\in[1,n],1\le w_i\le w,1\le v_i\le 10^9$

暴力的多重背包时间复杂度为 $\Theta(nw^2)$，显然不可行。
我们发现，每多选一个第 $i$ 个物品（设以前选了 $k$ 个）就会增加 $v_i-1-2k$ 价值，我们将一个物品拆成 $v_i-1,v_i-3,\dots$ 这些新物品（当然了，价值为负的不能取）。由于代价相同的我们优先选价值高的，所以我们将代价（$w_k$）相同的放在一起，并降序排序，并取前 $\displaystyle\lfloor\frac{w}{w_k}\rfloor$ 个（因为只有这些有贡献）进行 dp。
这样时间复杂度是调和级数，为 $\Theta(nw\log w)$。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-06 15:23:30

[ABC374F] Shipping

题目考察：离散化，dp。
题目简述：
给你序列 $\{s_n\}$ 和两个正整数 $x,k$，求序列 $\{p_n\},\{t_n\}$ 满足：

• $\forall i\in[1,n],s_{p_i}\le t_{p_i}$。
• $\forall i\in[1,n),t_{p_i}=t_{p_{i+1}}$ 或 $t_{p_i}+x\le t_{p_{i+1}}$。
• $\forall i\in[1,n-k],t_{p_i}\ne t_{p_i+k}$。

使得 $\displaystyle\sum_{i=1}^nt_i-s_i$ 最小，求这个值。
数据范围：

• $1\le k\le n\le 100$。
• $1\le x\le 10^9$。
• $\forall i\in[1,n),s_i\le s_{i+1}$。
• $\forall i\in[1,n],1\le s_i\le 10^{12}$。

本题的难点是缩小 $t$ 的范围。

首先，$p$ 序列的顺序是不影响答案的。

因为 $\displaystyle\sum_{i=1}^nt_i-s_i=\sum_{i=1}^nt_i-\sum_{i=1}^ns_i$，顺序不影响 $s,t$ 的和。

然后我们发现 $t_i$ 只可能是两种值（$1\le pos\le n$）：

• 可能是某一个 $s_{pos}$。
• 可能是某一个 $t_{pos}+x$。

贪心的想，第一种显然是因为若 $t_i$ 不是某一个 $s_{pos}$ 节点，则一定不如是前面的那一个 $s_{pos}$ 节点。
第二种是特例，$t_i$ 不能是前面的那一个 $s_{pos}$。

那么我们将时间节点变成所有的 $s_i+jx$（$1\le i,j\le n$），有效的时间变成了 $\Theta(n^2)$ 个。

我们这样就可以 dp 了，将有效的时间离散化（设为序列 $a$），设 $f_{i,j}$ 表示在第 $i$ 位上，且上一个 $t_{pos}$ 是 $j$ 的 $t$ 的和的最小值。

$j$ 这一维一定要加，要不然你不知道是哪一个时间节点。

$f_{i,j}$ 的转移方程比较难写，我们考虑应用刷表法（我们将从 $f_{i,j}$ 转移到 $f_{pos_i,pos_j}$）。
$\max(a_j+x,s_{pos_i})$ 是 $t_{pos}$ 应该设的值，应该设 $pos_i-i$ 个。这样的话我们就可用 $f_{pos_i,pos_j}=\min(f_{pos_i,pos_j},f_{i,j}+\max(a_j+x,s_{pos_i})\times(pos_i-i))$ 这个式子来转移了。

时间复杂度因为实现细节可能是 $\Theta(n^3k)$ 或 $\Theta(n^3k\log n^2)$。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-15 17:32:14

[ABC375G] Road Blocked 2

题目考察：dijkstra，哈希。
题目简述： 在一个图 $G$ 中，有 $n$ 个点，$m$ 条边（表示为 $u_i,v_i,w_i$），$m$ 个询问，第 $i$ 次询问去掉第 $i$ 条边后从 $1$ 到 $n$ 是否不连通或最短路的值改变（询问是独立的）。
数据范围：

• $2\le n\le 2\times 10^5$
• $1\le m\le 2\times 10^5$
• $1\le u_i<v_i\le n$
• $1\le w_i\le 10^9$
• $G$ 中无重边，点 $1$ 到点 $n$ 联通。

满足该条件，当且仅当所有的最短路都经过这条边，然后需要满足两个条件：

• 首先最短路要经过这条边。
• 然后经过这条边的最短路数等于总的最短路数。

那么我们继续思考（设 $dis_{u,v}$ 为 $u$ 到 $v$ 的最短路，$cnt_{u,v}$ 为从 $u$ 到 $v$ 的最短路数）：

• 最短路经过第 $i$ 边说明 $dis_{1,u_i}+w_i+dis_{v_i,n}=dis_{1,n}$。
• 经过这条边的最短路数等于总的最短路数说明 $cnt_{1,u_i}\times cnt_{v_i,n}=cnt_{1,n}$。

这两个值是可以分别从 $1$ 和 $n$ 分别跑 dijkstra 用 $\Theta((n+m)\log n)$ 求出来，但是 $cnt_{1,n}$ 的值非常大，所以我们要用哈希。

时间复杂度为 $\Theta((n+m)\log n)$。

代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-22 17:41:43

题目

[ABC376F] Hands on Ring (Hard)

题目考察：dp。
题目简述：
有一个有 $n$ 个节点的环，一开始你的两只手分别在 $1$ 节点和 $2$ 节点，每次你的手可以移动到相邻两个节点（即假设原来在 $x$ 处，那么就能移动到 $(x+n-2)\bmod n+1$ 和 $x\bmod n+1$），前提是另一只手不在将要移动的格子上。
有 $q$ 次操作，每次操作（$h_i,t_i$）要求你将左手或右手（$h_i$）移到某一个格子（$t_i$），问所有操作结束之后最少移动多少次。
数据范围：

• $3\le n\le 3000$。
• $1\le q\le 3000$。
• $\forall i\in[1,n],h_i$ 要么是 L，要么是 R。
• $1\le t_i\le n$。

做法

朴素 dp

显然，我们可以得到一个状态为 $\Theta(n^2q)$ 的 dp，设 $f_{i,j,k}$ 为第 $i$ 次操作中左手放在了 $j$ 节点，右手放在了 $k$ 节点，转移方程为（$\text{dist}(x,y,z)$ 表示在不经过 $z$ 点的情况下，从 $x$ 到 $y$ 的距离）：
$$f_{i,j,k}=\min_{j_0=1}^n(\min_{k_0=1}^n(f_{i-1,j_0,k_0}+\min(\text{dist}(j_0,j,k_0)+\text{dist}(k_0,k,j),\text{dist}(k_0,k,j_0)+\text{dist}(j_0,j,k))))$$ 但是每个状态都需要 $\Theta(n^2)$ 转移，时间复杂度（$\Theta(qn^4)$）不可接受（尽管能用滚动数组滚掉第一位）。

证明

证明先移动一个手再移动另一个手更优。
分类讨论：

1. 如果另一只手挡住了这只手的运动路线，直接将另一只手移到一个位置就行了。
2. 否则另一只手不动就行了。

于是我们想到了后面的优化。

优化 $1$

我们发现，实际上有意义的状态并不多，第 $i$ 次操作你的一只手一定要在 $t_i$ 节点上，这样的话有意义的状态就变成了 $\Theta(n)$ 个，但时间复杂度仍然是 $\Theta(qn^3)$。

优化 $2$

我们又发现，有意义的状态只有 $\Theta(n)$ 个，所以我们不需要 $\Theta(n^2)$ 枚举上一个状态，直接用 map 或直接压维的方式解决，时间复杂度为 $\Theta(qn^2)$（可能带 $\log$）。

优化 $3$

我们又双叒叕发现，每个上一个状态只会出现 $1$ 个第 $2$ 种情况，于是我们换种方式转移（我不会告诉你我忘了叫什么了）。
这样每次操作的有效状态为：$dp_{i,i-1}$ 和 $dp_{i,i+1}$（所有的上一个的有效状态均可转移），其他的 $dp_{i,j}$（一个有效状态只会转移一个）。
时间复杂度为 $\Theta(qn)$。

代码

这呢

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-23 12:59:08

[ABC381E] 11/22 Subsequence

题目考察：二分，前缀和。
题目简述：
定义 11/22 序列为由 $k$ 个 1，$1$ 个 \/ 和 $k$ 个 2 拼接而成的字符串（$k$ 为 非负整数）。$q$ 次询问，每次询问求长度为 $n$ 的字符串 $s$ 的 $l$ 到 $r$ 位的最长的是 11/22 序列的子序列的长度。
数据范围：

• $1\le l\le r\le n\le 10^5$。
• $1\le q\le 10^5$。
• 保证 $s$ 只有 1、2 和 \/ 组成。

贪心的想，对于每一个 \/，他前面的所有 1 （设有 $sum$ 个）和后面的所有 2 （设有 $num$ 个）都可以放在他的前面（后面）形成一个子序列，但 1 和 2 的数量要相等，所以最长长度为 $2\min(sum,num)+1$。
前面 1 的个数和后面 2 的个数均可用前（后）缀和预处理得到（设为 $sum_i$ 和 $num_i$）。
但是我们截取 $[l,r]$ 区间后，$sum_i$ 要减去 $sum_{l-1}$，$num_i$ 要减去 $num_{r+1}$，我们就无法预处理每个 \/ 的最长长度了。

我们发现，最后 $sum$ 和 $num$ 减完后应是这样的：

$sum$ 是单调非递减的，$num$ 是单调非递增的。
所以，当 $sum_i<num_i$ 时，$i$ 左边的 $j$ 一定会满足：

• $sum_j<num_j$。
• $sum_j\le sum_i$。

则最终最长长度一定更短，所以我们应该向右找。
$sum_i>num_i$ 同理。

那么现在我们就想到了二分，按照上述方法模拟即可。

最终总体时间复杂度为 $\Theta(n+q\log n)$。
代码