十月模拟赛回顾
Rem_CandleFire
·
·
个人记录
前情
2024/10/5
省流：放假回来啥也不会。
A.最多区间对（原题：？）
题目大意
有 n 个区间，选择尽可能多对区间且每对区间不相交。1\le n\le 10^5。
分析与做法
首先按照左端点排序。那么对于一个区间 [l_i,r_i]，如果之前有未配对的右端点小于 l_i 的区间，那么配对即可。
如果没有可配对区间，考虑反悔。在已配对区间中选取右端点最小的 [l,r_{min}]，如果 r_{min}<r_i 则交换两个区间，让 [l,r_{min}] 有与其它区间匹配的可能。
这样一定是最优的，开两个堆存右端点即可，时间复杂度 O(n\log n)。
B.数字堆叠（原题：？）
题目大意
给出长度为 n 的排列 a，空序列 b，空的大根堆 q。共有 2n 次操作，每次操作有两种选择。
-
- 将序列 a 中最靠前的数加入 q 并在原序列中删除。
最终会得到新排列 b，求可以生成多少种不同的排列 b，取模。
**分析与做法**
突破口在于最小的元素。设 $a_x=1,b_y=1$，则序列 $b$ 的前 $y$ 个元素和序列 $a$ 的前 $x$ 个元素是相同的。而序列 $a$ 中 $[1,x]$ 和 $[x+1,n]$ 是独立的两段。因为当前考虑的段可能不同，所以还要另外加入一个最小值 $v$。
现在假设对于区间 $[l,r]$ 考虑其中大于等于 $v$ 的元素。设这些元素中的最小值为 $m$ 且 $a_p=m$。那么允许从 $[p,r]$ 之间选择一个位置 $k$ 划开，继续考虑 $[l,k]$ 和 $[k+1,r]$，相应的 $v\leftarrow v+1$。
使用递归来完成区间 DP，每一次合并是 $\sum_{k=p}^r{F(l,k,v+1)\times F(k+1,r,v+1)}$。答案是$F(1,n,1)$。注意一下记忆化，时间复杂度 $O(n^4)$。
### C.平衡序列（原题：？）
**题目大意**
一个 $01$ 序列是平衡的当且仅当不存在一个子区间其中 $0,1$ 个数的差的绝对值大于 $k$。给出 $k$，求由 $x$ 个 $0$ 和 $y$ 个 $1$ 构成的平衡序列个数，取模。
$1\le k,x+y\le 5\times 10^7$。
**分析与做法**
反射容斥？
### D.美丽序列（原题：？）
长度为 $n$ 的 $01$ 序列 $x$，称其为美丽序列当且仅当其满足 $m$ 条限制。每条限制形如 $u,v$ 不能同时为 $1$。其中：
- $u=x_i$ 或 $u=\lnot x_i
求有多少个长度为 n 的美丽序列。1\le n \le 60。
分析与做法
神秘题，略。
2024/10/6
A.拱桥设计（原题：？）
题目大意
求有多少组正整数参数 (B,C) 使得方程 x^2-2Bx+C=0 有整数解，其中 C 在 [L,R] 内。共 T 组测试数据。
**分析与做法**
对答案进行前缀和，则区间 $[L,R]$ 的答案就是 $S_R-S_{L-1}$。数学方法可知，有整数解的充要条件是 $(B+n)(B-n)=C$。类似质数筛的形式枚举出每一组乘积 $xy$，如果 $x,y$ 奇偶性相同，令 $S_{xy}$ 加 $1$ 即可。
而后对 $S$ 进行一遍前缀和并特判 $C=1\times C$ 的情况。时间复杂度 $O(n\log n)$。
### B.重排（原题：？）
**题目大意**
对于长度为 $n$ 的排列 $a$，每次操作可以对 $|x-y|=1,a_x\not=x,a_y\not=y$ 的 $a_x,a_y$ 交换。要求在不超过 $m$ 次操作后将 $a$ 变为 $1\sim n$。判断是否可行并构造操作序列。
$n\le 1000$。
**分析与做法**
首先对于任意的 $a_p=p,a_q=q$，$[p,q]$ 这一段内的序列应当是 $[p,q]$ 的一个错排，否则无解。
考虑如何构造，对于任意一段，首先考虑最小值 $a_t$，将其不断向前移动，如果遇到 $a_x=x+1$，那么交换 $a_x,a_{x-1}$，此时如果 $a_{x-1}=x$，那就继续向前找……也就是说找到第一个满足 $a_y\not=y+1$ 的位置，先将 $(a_y,a_{y+1}),(a_{y+1},a_{y+2})\dots(a_{t-2},a_{t-1})$ 交换，然后将 $a_t$ 推到底即可。
如果不存在这样的位置，那么直接推就行了。时间复杂度 $O(n^2)$。
### C.美丽子串（原题：[记忆](https://www.luogu.com.cn/problem/P6864)）
**题目大意**
去原题看。
**分析与做法**
考虑前两种操作对答案的影响，记录一下以最末尾字符为结尾的匹配串数量 $cnt$，总答案为 $ans$。
- 对于操作一，$ans\leftarrow ans+cnt+1,cnt\leftarrow cnt+1$。
- 对于操作二，$ans\leftarrow ans+1,cnt\leftarrow 1$。
那么对于第 $i$ 次操作，最终答案就是由初始情况进行了若干次变换得到的。发现可以用矩阵乘法刻画变换过程。
初始矩阵：$[ans=1,cnt=1,1]$。
操作一的矩阵：
\begin{bmatrix}
1,0,0\
1,1,0\
1,1,1
\end{bmatrix}。
操作二的矩阵：
\begin{bmatrix}
1,0,0\
0,0,0\
1,1,1\
\end{bmatrix} $。
记初始矩阵为 V，操作一矩阵为 F，操作二矩阵 S，单位矩阵为 I。得到答案序列形如 VFFSSFS\dots。那么操作三事实上就是将某个序列中某个矩阵改为单位矩阵，撤销撤销操作就是将对于位置改回来，加个数组维护一下某个操作的生效位置就行了。
线段树维护区间矩阵乘法。时间复杂度 O(A^3n\log n)，在这里矩阵尺寸 A=3。
D.物流调度（原题：？）
题目大意
有 x_{max}+1 个配送点，标号为 0,1\dots,x_{max}。货物在当前配送点 x，可以花费 c(x) 的代价将其运送到 \lfloor \frac{x}{2} \rfloor,\lfloor \frac{x}{3} \rfloor,\dots,\lfloor \frac{x}{w} \rfloor，其中 w 给定。
初始时 c(x)=d_0(x)，其中 d_0(x) 为 x 的因子个数。需要执行 q 次操作。
- 修改：给定 x，将 c(x) 减 1，保证任意时刻 c(x)\ge0。
- 查询：给定 x，询问将货物从 x 送到配送点 0 的最小代价。
## 2024/10/9
### A.游戏升级（原题：？）
**题目大意**
两个初始值 $B_1,B_2$，每 $x$ 时间 $+1$，$B_1$ 共有 $A_1$ 时间，$B_2$ 共有 $A_2$ 时间，求有多少个 $x\in [1,N]$ 使得最后 $B_1=B_2$。
共 $T$ 组数据，$1\le T\le 2000,N,A_1,B_1,A_2,B_2\le 10^8$。
**分析与做法**
题意转化为要求多少个 $x\in[1,N]$ 使 $B_2-B_1+\lfloor \frac{A_2}{x} \rfloor=\lfloor \frac{A_1}{x} \rfloor$。
对 $A_1,A_2$ 整除分块之后双指针扫描一遍即可。
### B.难题（原题：？）
**题目大意**
对于任意的 $(x_0,y_0)$，一次变化后为 $(x_0+y_0,x_0+2y_0)$。现在求有多少种整数对 $(x,y)$ 满足 $x\in[0,N],y\in[0,M]$ 变化任意次之后的 $x$ 取到 $X$。
共 $T$ 组数据，$1\le T\le 10^5,0\le X,N,M\le 10^{18}$。
**分析与做法**
推推式子可以发现，若令斐波那契数列 $F_1=1,F_2=1$，进行 $i$ 次变化后的 $x=F_{2i-1}x_0+F_{2i}y_0$。打表可得 $F_{87}\ge 10^{18}$。于是对于每组测试数据，事实上是解至多 $43$ 个形如 $F_ix+F_{i+1}y=X$ 的不定方程，只需要解出来然后调整即可。
注意到这样的时间复杂度是 $O(43T\log V)$ 的，无法通过。根据经典结论，斐波那契数列相邻两数互质可知，方程 $F_ix+F_{i+1}y=X$ 等价于 $F_ix'+F_{i+1}y'=1$。这和 $X$ 无关。于是只要预处理出 $43$ 个方程的特解 $x_i,y_i$，对于每组数据直接乘上 $X$ 然后调整即可。时间复杂度 $O(43T)$。
注意实现细节：每一次调整之后都要判断是否 $x\in[0,N],y\in[0,M]$ 且需要特判 $X=0$ 的情况。
### C.迷宫逃亡（原题：[水筒](https://www.luogu.com.cn/problem/AT_joisc2014_e)）
**题目大意**
去原题看。
**分析与做法**
结论：图上两点间的路径的最大边权的最小值是该图最小生成树上的两点简单路径的最大边权。（类似货车运输）
结论：对于网格多源 BFS 染色后，任何一条对生成树有用的边都不会经过大于两种颜色。
而两种颜色必然有一个分界点。于是网格图上跑多源 BFS 染色并建边，对图建最小生成树，树上倍增处理边权最大值。对于每个询问 $(x,y)$，类似求 LCA 跳一遍更新最大边权即可。
时间复杂度 $O(nm+(p+q)\log p)$。
### D.点格游戏（原题：[Dots and Boxes](https://www.luogu.com.cn/problem/P7363)）
**题目大意**
去原题看。
**分析与做法**
注意限制：每个格子四周都只有 $0$ 或 $2$ 条未划线的边。这说明图中所有联通块要么是链，要么是环。特殊地，将单独的 $1\times1$ 格子看做链。
先考虑在链上先后手如何处理，显然先手只能连一条边。而后手有如下两个选择：
- combo 掉该链剩余的格子，代价是对于下一个联通块变成先手（环相同）。
- 隔一个格子划线，相当于让出两个格子，但不用转换先后手（环上要放弃四个格子）。
而无论如何为了让后手的分数尽可能少，先手都应该选择当前最小的联通块划线。
考虑 DP，设 $f_{i,j}$ 表示考虑到剩下第 $i$ 大链，第 $j$ 大环的最优策略分数。
若当前考虑链的情况，记此链长为 $c$。则 $f_{i,j}=-\max(c+f_{i-1,j},c-4-f_{i-1,j})$，特殊地，如果 $c\le2$，有 $f_{i,j}=-c-f_{i-1,j}$。
若考虑环的情况，记环长为 $l$，类似的，$f_{i,j}=-\max(l+f_{i,j-1},l-8-f_{i,j-1})$。两种情况取较大值即可。
时间复杂度能过。
## 2024/10/10
### A.消除（原题：[Element Extermination](https://www.luogu.com.cn/problem/CF1375C)）
**题目大意**
对于一个 $1\sim n$ 的排列 $p$，当 $p_i<p_{i+1}$ 时可以删除 $p_i$ 或 $p_{i+1}$。判断是否可以将它删剩一个数。
共 $T$ 组测试数据，$1\le T\le 1000,\sum n\le 10^5$。
**分析与做法**
考虑保护一个数使它留到最后。具体地，维护一个栈 $s$，那么对于当前的 $p_i$，尽可能的用 $p_i$ 消除 $s_{top}$ 直到栈内只有一个数。如果此时 $p_i>s_{top}$，删除 $p_i$，否则入栈。时间复杂度 $O(\sum n)$。
事实上有结论：当 $p_1<p_n$ 时可行，否则不行。时间复杂度 $O(\sum n)$，瓶颈在于输入。
### B.树的划分（原题：[Tree Conundrum](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-2889)）
**题目大意**
一棵 $n$ 个节点的树，求有多少种划分方法将树划成若干大小相同的联通块。
$1\le n\le 10^6$。
**分析与做法**
结论：划分成大小为 $k$ 的联通块是可行的，当且仅当树上以子树大小是 $k$ 的倍数的子树有 $\frac{n}{k}$ 个。
“Oier 不需要证明，只需要构造。”——SL。
也可以从边的角度来理解，设有边 $(u,v)$，那么当且仅当 $u,v$ 各自那边的子树大小均是 $k$ 的倍数时这条边可删去。当可删去的边刚好是 $\frac{n}{k}-1$ 条时可行。
### C.奸商（原题：？）
**题目大意**
有 $n$ 种代币，每种面值为 $a_i$。每次小明会给每个顾客依次发放任意多次任意一种代币（可以不发）。两个发代币的方案不同当且仅当给两个顾客发放代币的次数不同或发放了不同种的代币，求有多少种发放代币的方案使得发放的总面值小于等于 $K$。
$1\le n\le 10^5,K\le 10^9,1\le a_i\le 100$。
**分析与做法**
设 $f_i$ 表示发放了总面值为 $i$ 的代币的方案数。显然有转移 $f_i\leftarrow f_i+f_{i-a_j}$（当 $i\ge a_j$ 时）。
注意到 $a_i\le 100$，所以 $f_i$ 的值最多只和前面的 $100$ 个数有关，且转移方程是非常朴素，并且 $k$ 很大，于是考虑矩阵优化。
套路的，可以预处理出 DP 数组的前 $100$ 项，有初始矩阵 $[f_0,f_1,\dots,f_{99},sum=0]$。记录面值为 $a_i$ 的代币有 $c_{a_i}$ 个，随便写一下转移过程可得转移矩阵 $T$：
$$
\begin{bmatrix}
0,0,0,\dots,0,c_1,1\\
1,0,0,\dots,0,c_2,0\\
0,1,0,\dots,0,c_3,0\\
0,0,1,\dots,0,c_4,0\\
\dots\\
0,0,0,\dots,1,c_{n},0\\
0,0,0,\dots,0,0,1
\end {bmatrix}
$$
以上 $n=100$，矩阵大小为 $101\times 101$，初始矩阵中的 $sum$ 用于前缀和。
随便快速幂转移即可，时间复杂度 $O(v^3\log k)$。
### D.候车（原题：？）
略。
### E.求和（原题：？）
**题目大意**
设 $G(n)=\prod_{i=1}^n(2i-1)$，给定 $n,m,x$，求：
$$\sum_{i=0}^n\sum_{j=0}^m{G(i\;\mathrm{xor}\;j\;\mathrm{xor}\; x)}$$
特别的，$G(0)=0$，输出答案对 $2^{32}$ 取模后的值。
$n,m,x\le 2^{30}$。
## 2024/10/11
### A.贸易（原题：？）
**题目大意**
给定 $n$ 个点 $m$ 条单向边的图，点有点权。以任意点为起点出发，途中选择一个点点权 $u$，再选另一个点点权为 $v$，求 $v-u$ 的最大值。
$1\le n,m\le 2\times 10^5$。
**分析与做法**
一眼缩点之后跑拓扑排序，对于经过的每个 SCC 维护最小值，拓扑过程中更新最大值即可。
### B.格子游戏（原题：？）
**题目大意**
对于一个 $n$ 行的网格图，第 $i$ 行有 $a_i$ 个格子，每行左边对齐且 $a_{i+1}\le a_i$。开始时只有左上角数字为 $1$，每次操作可以选择一个格子其中数减一，其右边与下面的格子中的数加一（如果有的话），求让所有格子为 $0$ 的最小操作次数。取模。
$1\le n,a_i\le 10^5$。
**分析与做法**
显然每一行从左到右归零是最优的，玩几下发现是一个杨辉三角斜线求和。对照图可得结论：对于第 $i$ 行，清零的最小操作次数为 $\binom{a_i+i-1}{a_i-1}$。每一行单独算一遍组合数即可。
时间复杂度 $O(n)$。
### C.传火（原题：[Sparklers](https://www.luogu.com.cn/problem/AT_joisc2017_c)）
**题目大意**
去原题看。
**分析与做法**
一眼二分答案 $v$。
显然让 $[1,k-1],[k+1,n]$ 的花火向中间靠拢是最好的，对于 $[l,r]$ 这一段花火，有 $(r-l)t$ 的时间上限，相向而行的时间花费是 $\frac{x_r-x_l}{2v}$，于是得到限制条件 $\frac{x_r-x_l}{2v}\le (r-l)t$，移项得 $x_l-2vtl\ge x_r-2vtr$。
考虑设 $f_i=x_i-2vti$，则一段区间合法当且仅当 $\forall i<j,f_i\ge f_j$。二分 check 转变为是否能将区间 $[k,k]$ 扩展为 $[1,n]$。首先能单调地找到一个极大的递减区间 $[L,R]$，考虑判断能否从 $[k,k]$ 舒张到 $[L,R]$，同时从 $[1,n]$ 收缩到 $[L,R]$。
当 $f_i\ge f_l$ 且 $\forall j\in[i,l],f_j\ge f_r$ 时区间 $[l,r]$ 可以舒张到 $[i,r]$。其它情况同理。
时间复杂度 $O(n\log V)$。
### D.树权（原题：[Spiders Evil Plan](https://www.luogu.com.cn/problem/CF526G)）
略。
## 2024/10/14
### A.传送门（原题：？）
**题目大意**
在 $n\times m$ 的网格图上，每格有数 $0/1$ 表示墙壁/房间，相邻的房间可以花费 $0$ 的代价到达。若某两点属于不同的房间，那么可以花费两点曼哈顿距离的代价传送。
给出起点 $(x_s,y_s)$，对于所有的点 $(x,y)$ 求出从起点到该点最多传送次数，且最终的代价要小于等于直接传送的代价。
定义直接传送的代价为至多经过一次传送的最小代价。
$1\le n\le 300$。
**分析与做法**
优化建边 + DP，具体实现不会。
### B.集合函数（原题：[Strange Function](https://www.luogu.com.cn/problem/CF1310E)）
**题目大意**
去原题看。
**分析与做法**
观察到 $S\rightarrow f^k(S)$ 的映射是多对一的，即可能有不同的 $S$ 有相同的 $f^k(S)$。于是反过来考虑，只要对于某个 $A=f^k(S)$ 存在满足条件的 $S$，则计入答案。
感性地，我们注意到当 $n$ 一定，$k$ 越大时答案越小。根据特殊性质，考虑对 $k$ 分讨。
$k=1$ 时，设 $A=f(S)$，其中 $A=\{a_1,a_2,\dots,a_m\}$，那么有 $|S|=\sum a_i\le n$。划分数问题，简单完全背包即可。
$k=2$ 时，设 $B=f(A)=f(f(S))$，其中 $B=\{b_1,b_2,\dots,b_w\}$，则有 $|A|=\sum b_i,|S|=\sum a_i\le n$，且去重后对于 $A$ 的某个元素 $a_i$，其出现次数为 $b_i$，对 $|S|$ 的贡献为 $a_ib_i$。从而 $|S|=\sum a_ib_i\le n$。
为了构造合法解，需让 $\sum a_ib_i$ 尽可能小，于是直接令 $a_i=i$，则有 $\sum ib_i\le n$。不妨规定 $b_i\ge b_{i+1}$，那么差分一下可以发现实际上只需要 $\sum_{i=1}^w \frac{i(i+1)}{2}b_i$。于是以 $\frac{i(i+1)}{2}$ 做完全背包即可。
接下来是 $k\ge 3$ 的情况。
根据感性理解，不妨直接搜索数的划分，用个 `vector` 记录一下，另外如果当前这一层无法满足条件就直接 `return`。`check` 的方法就类比上述两种情况讨论的内容即可。[给出一种实现](https://www.luogu.com.cn/paste/5wye3yl3)。
时间复杂度 $k=1,O(n^2)$，$k=2,O(n\sqrt{n}?)$，$k\ge3,O(\mathrm{notTLE})$。
### C.矩阵构造（原题：？）
**题目大意**
构造由小写字母 `r,y,x` 组成的不超过 $40\times40$ 的矩阵使得其中恰好有 $n$ 个连续的字符串 `ryx`。在八个方向上出现 `ryx` 均可。
$1\le n\le 2222$。
**分析与做法**
这个数据范围就很魔性，考虑如何构造矩阵使出现的字符串最多。对一下脑电波可以发现类似如下构造最优（以 $8\times8$ 为例）：
$$
\begin{aligned}
ryxyryxr\\
ryxyryxy\\
ryxyryxx\\
ryxyryxy\\
ryxyryxr\\
ryxyryxy\\
ryxyryxx\\
ryxyryxr\\
\end{aligned}
$$
刚好一个 $40\times 40$ 这样构造出来的矩阵答案为 $2223$。
接下来随机选择一个点修改，该点会影响到以它为中心的 $5\times5$ 单位。随机修改可以减少 $1\sim 6$ 个字符串。每次选择减少最小的进行修改，最多需要做 $2222$ 次（事实上远达不到这个）。每次需要比较不修改以及修改成三种字符的情况，需要 $5\times5$ 的范围。那么时间复杂度 $O(100n)$，判断以某个点开始的字符串八个方向需要 `if`，这里会加点常数，但是不多。综上所述随机选择，贪心修改的时间复杂度是有保证的。（当然这不是官解）。
### D.排列（原题：？）
**题目大意**
对于排列 $\{s_n\}$，定义 $g(k,i)=\min_{j=i}^{i+k-1}{s_j}\ ,\ G(k)=\max_{i=1}^{n-k+1}{g(k,i)}$。现在给出 $G(1),G(2),\dots,G(n)$，求满足要求的排列个数。
$1\le G(i),n\le 50$。
**分析与做法**
咕。
## 2024/10/17
### A.向量（原题：？）
**题目大意**
给定序列 $a$，每次操作可以将 $a$ 的相邻两位相加后对位放回原位置。例如 $\{1,3,7\}$ 操作一次后可以是 $\{4,7\}$ 或 $\{1,1,0\}$。求给定序列的操作次数最大值。
序列长度 $n\le2\times10^5$。
**分析与做法**
考虑模拟，从左往右依次操作即可。时间复杂度 $O(n)$。
### B.顺序（原题：？）
**题目大意**
给定 $n\times m$ 的网格图，距离为 $1$ 的两点有边，问能否找到其某个生成树其中树的直径长度为 $t$。若可以，给出构造。
$n,m\le 1000,0\le t\le nm-1$。
**分析与做法**
咕。
### C.表达式（原题：？）
**题目大意**
给定合法的位运算表达式，其中若干运算符被涂抹成 `#`，若干数字被涂抹成 `?`，求有多少种表达式可以让最终运算结果为 $1$。
表达式中运算符数量 $n\le 10^5$。运算符为按位与、按位或、按位异或，数字为 $0$ 或 $1$。
**分析与做法**
建出表达式树然后简单 DP 即可。时间复杂度 $O(2n)$。
### D.熵值（原题：？）
**题目大意**
二维平面上 $n$ 个点，第 $i$ 个点 $(x_i,y_i)$ 有权值 $w_i$。每次操作可以在两点 $u,v$ 间转移权值，即 $w_u\leftarrow w_u-\Delta w,w_v\leftarrow w_v+\max(0,\Delta w-d)$，其中 $d$ 是 $u,v$ 间的欧几里得距离。
$n\le 16,0\le x_i,y_i,w_i\le 10^9$。
**分析与做法**
显然令两个点最多操作一次是最优的，那么将每次操作看做一条边，则对于一个联通块的最小操作代价就是其最小生成树的边权和。一个联通块的最小的点权的最大值就是其点权和减去转移代价的平均值。
$$val=\frac{\sum_{u\in V}{w_u}-D}{|V|}$$
考虑预处理出每个联通块的代价，枚举联通块然后跑一遍最小生成树的算法即可。
因为不同联通块互不影响，考虑 DP 划分联通块。设 $U$ 是当前考虑的情况，那么 $f_U=\max(f_U,\min(f_S,f_{U\setminus S}))$。答案是 $f_{(1<<n)-1}$。时间复杂度 $O(2^ne\log e+3^n)$ 或 $O(2^nn\log n+3^n)$。前式取决于最小生成树算法，$e$ 表示边数，后式为 DP 枚举子集。
## 2024/10/18
### A.能量（原题：？）
**题目大意**
给定长为 $n$ 的序列 $A$，对于大于 $0$ 的 $A_i$，一年后将变为 $A_i^{'}=\lceil \frac{A_i}{2} \rceil+k$，两年后变为 $A_i^{''}=\lceil \frac{A_i^{'}}{2} \rceil+k$，以此类推。有 $Q$ 个询问，第 $i$ 个询问 $m_i$ 年后序列的和。
$1\le n,Q\le10^5,0\le A_i,m_i,k\le10^9$。
**分析与做法**
显然 $\log V$ 年后 $A_i=0$，对于每个 $A_i$ 暴力衰减 $\log V$ 次记录求和即可。时间复杂度 $O(n\log V)$。
### B.基因（原题：？）
因为题意转化较难，考虑最大限度保留。
**题目大意**
对于一种每天发生突变的基因 $s$，在每次突变中，其子串 $p$ 将被替换成非空串 $q$。经过 $m$ 天观察后，记录了 $2m$ 个字符串 $t$。其中 $t_{2i-1}$ 与 $t_{2i}$ 表示第 $i$ 天里，基因的连续子序列 $t_{2i-1}$ 突变为 $t_{2i}$。
但是，受到了宇宙射线的影响，$t$ 被打乱了。现在给定打乱后的数据 $t_1^{'},t_2^{'},\dots,t_{2m}^{'}$，且最终基因为 $s_1$。求初始基因序列 $s_0$。且 $s_0$ 是一个小写字母。保证所有字符串均由小写字母组成。
$1 \le m \le 10^5,1 \le |s_1|,\sum|t_i|\le 3\times 10^5$。保证有解。
**分析与做法**
（事实上，本题的部分分很强，但是我懒得抄部分分的数据范围）
注意到，每两次突变对于每种字母消耗了偶数次。于是统计 $t_i$ 中的字符数量，减去 $s_1$ 的字符数量（即为剩下来的字符），那么一定会有某个字符 $c$ 还存有奇数次，这就是答案了。时间复杂度 $O(\sum|t_i|+|s_1|)$。
### C.序列（原题：？）
**题目大意**
对于长度为 $n$ 正整数序列 $a$ 给出 $m$ 个限制，形如 $[x_i,y_i]=b_i$ 表示序列中 $A_{x_i},A_{y_i}$ 的最小公倍数为 $b_i$。每个 $b_i$ 以质因数分解的格式给出，即 $b_i=\prod_{i=1}^k p_i^{c_i}$。求可能的序列个数。对 $10^9+7$ 取模。
$6\le n\le 38,1\le k\le 8,0\le c_i\le 10^9,m\le \frac{n(n+1)}{2}$。
**分析与做法**
注意到每个质因子独立，那么对于质数 $p_i$，限制在于 $\max(u_i,v_i)=c_i$。将所有限制 $(x_i,y_i)$ 连边。如果一个点多条 $c_i$ 不同，那么最多只能满足最小的 $c_i$，其他边另一端点就确定了。最后只剩权值相同的联通块。
折半，对于一部分维护高位前缀和，$O(1)$ 查询方案，复杂度为 $O(k(t2^t+2^{n-t}))$，其中 $t$ 是维护高维前缀和的点数。
### D.mex（原题：？）
**题目大意**
给定长为 $n$ 的自然数序列 $a$，对于 $0\sim n$ 的每个 $i$，求 $\sum_{l=1}^n\sum_{r=l}^n[\mathrm{mex}_{i=l}^r a_i=i]$。其中 $\mathrm{mex}_{i=l}^r a_i$ 表示在区间 $[l,r]$ 中没有出现的最小的自然数。
$2\le n\le 2\times 10^6$。
**分析与做法**
问题转化为求 $\mathrm{mex}\ge i$ 的答案，然后作差。
咕咕咕。
## 2024/10/19
### A.最大模和（原题：[Modulo Summation](www.luogu.com.cn/problem/at_abc103_c)）
**题目大意**
给定长为 $n$ 的序列 $a$，最大化 $\sum_{i=1}^n{x\bmod a_i}$，$x$ 是非负整数。
**分析与做法**
答案为 $\sum_{i=1}^n{(a_i-1)}$。根据中国剩余定理易得，一定存在非负整数 $x$ 使得 $\forall i\in[1,n]\cap\mathbb{Z},x\bmod a_i=a_i-1$。时间复杂度 $O(n)$。
### B.报警（原题：[Dueling GPSs S](https://www.luogu.com.cn/problem/P3106)）
**题目大意**
去原题看。
**分析与做法**
建反图从 $n$ 到 $1$ 跑最短路可以得到原图中每条边 $(x,y)$ 的抱怨次数 $w$。建边 $(x,y)=w$ 得到新图 $G$。在 $G$ 上正着跑最短路，答案为 $dis_n$。使用堆优化 Dijkstra，时间复杂度 $O(n\log n)$。
### C.数论求和（原题：[Sum and Replace](https://www.luogu.com.cn/problem/CF920F)）
**题目大意**
去原题看。
**分析与做法**
注意到 $d(1)=1,d(2)=2$。那么一个数 $x$ 只要修改 $\le \log x$ 次就会 $\le 2$，于是区间修改时记录一个最大值判断是否有继续修改的必要即可。类似花神游历各国。时间复杂度 $O(n\log n)$。
### D.游行（原题：？）
**题目大意**
给定 $n$ 个点的图，图的建边方式如下：
```c++
state = seed;
for x = 0 -> n-1:
for y = x+1 -> n-1:
state = (state * 1103515245 + 12345) mod 2^{31}
if state < threshold:
add edge x-y
L=length(toggle)/2
for i = 0 -> L-1:
x = toggle[2*i];
y = toggle[2*i+1]
if have edge x-y:
remove edge x-y
else:
add edge x-y
```
选定一个点，走连续五条连续的边，边不能重复，求方案数。
$1\le n\le 500,0\le seed,threshold<2^{31}-1,0\le L\le 200,0\le toggle_i< n,toggle_{2i}<toggle_{2i+1}$。
**分析与做法**
咕咕咕。
## 2024/10/21
### A.资源分配（原题：？）
**题目大意**
给定长度为 $n$ 的正整数序列 $a$，将 $a_i$ 增加 $1$ 的代价是 $b_i$。最小化使 $a_i$ 两两不同的总代价并输出。
$1\le n\le 10^5$。
**分析与做法**
注意到操作只能使某个数增加而不能减少，那么对于相同的数，必然使代价最小的那几个增加是最优的。于是贪心地维护一个小顶堆表示相同数的代价即可。时间复杂度 $O(n\log n)$。
### B.数字生成树（原题：？）
**题目大意**
定义一棵生成树的权值是其所有边权的按位或的结果。给定一个 $n$ 个点 $m$ 条边的图，有 $q$ 次独立的修改，每次新连一条边 $(x,y)$，权值为 $0$，求每次修改后的图的最小生成树的权值。
$2\le n\le 10^5,1\le m,q\le 10^5,0\le w<2^{30}$。
**分析与做法**
咕咕咕。
### C.图书索引（原题：？）
一个字符串 $S$ 的长度为 $k$ 的前缀记作 $S[1:k]$。初始时给定 $n$ 个字符串，第 $i$ 个字符串记作 $S_i$，初始时其数值 $a_i$ 为 $0$。
有 $Q$ 个操作，每个操作是以下其中一种（假设操作时的字符串数量为 $M$）：
- `1 i K x`，对于每个 $1\le j\le M$，如果 $S_j[1:K]=S_i[1:K]$，那么将 $a_j$ 加上 $x$。
- `2 i K T`，加入新字符串 $S_{M+1}=S_i[1:K]+T$，$a_{M+1}=0$。随后将 $M$ 增加 $1$。
- `3 i`，查询 $a_i$。
输入的字符串长度总和为 $L$。$1\le n,q\le 10^5,1\le L\le 2\times 10^5,1\le i\le M,1\le K\le |S_i|,1\le x\le 10^6$。
**分析与做法**
先将操作离线，那么可以对所有 $M$ 个字符串建字典树。字典树记录结束位置。
考虑操作一，设字符 $S_{i,K}$ 在字典树上的位置为 $u$，那么事实上可以转化为以 $u$ 为根的子树加。深搜一遍字典树重新标号即可（dfn 序或重标字符串序号）。
操作二时需要记录以下当前以来第 $i$ 个字符串被加了多少的权值，之后需要减掉。
操作三就是简单的单点查询。
注意结构体的实现。时间复杂度 $O(L\log L)$ 或 $O(L\log M)$。
### D.卡牌游戏（原题：？）
**题目大意**
给定长为 $n$ 的序列 $A$。可以有两种操作：
- 将 $A_i$ 乘上某个质数。
- 如果 $A_i$ 能被某个质数整除，可以除以这个质数。
共 $q$ 次询问，每次询问给定 $[l,r]$，求使 $\exist i,j\in[l,r],A_i\times A_j=x^2,x\in\mathbb{N}$ 的最小操作次数。
$2\le n\le 2\times 10^5,1\le q\le 10^6,1\le A_i\le 5\times 10^6$。（时限 $4s$）
**分析与做法**
若 $A_i\times A_j=x^2$，那么其质因数分解的结果的指数一定都是偶数，所以对于给定的 $A_i=\prod{p_j^{c_j}}$，改为 $\prod{p_j^{c_j\bmod 2}}$。容易发现 $j\le 7$。那么 $A_i$ 的约数至多只有 $2^7=128$ 个，不妨预处理出来。
注意到指数在模意义下时两个操作本质上是一致的，且显然可以在 $O(128n)$ 的时间复杂度下求出将 $A_i$ 变成某个值 $v$ 的代价。于是可以用线段树来保存这些代价。
具体地，记录一个数组 $P_{v,c}$ 表示能以 $c$ 的代价将 $A_{P_{v,c}}$ 改为 $v$。设当前将 $A_i$ 改为 $v$ 的代价为 $c$，那么枚举一个 $d\in[0,7]$，若 $P_{v,d}$ 存在且比当前的值要更优，更新并在位置 $P_{v,d}$ 覆盖为 $d+c$。线段树内维护最小值。
对于某次询问 $r$，在枚举到 $a_r$ 后查找区间 $[l,r-1]$ 的值（因为代价保存在前一个数）。
时间复杂度 $O(w2^wn\log n)$，其中 $w$ 是最多的因子个数，本题中 $w=7$。跑不满，且时限较大所以能过。
## 2024/10/23
省流：文件读写不给文件名，堪称 English Olympics，最后还是猜出来的。
### A.魔法袋（原题：？）
**题目大意**
开始时有数 $a_1=1$，有两种操作（设操作时的数有 $m$ 个）。
- 发生：增加一个数 $a_{m+1}=1$，将 $m$ 加一。
- 合并：（数的个数大于一时）将任意两个数相加为新数，删除原来两数。
给定长为 $n$ 的操作序列 $s$，$s_i=1$ 表示发生，$s_i=-1$ 表示合并，$s_i=0$ 表示可选择发生或合并。最大化最终序列的平均值。若不能完成操作，输出 $-1$。
$1\le n\le 10^6$。
**分析与做法**
记 $\sum a_i=p$，共有 $q$ 个数。注意到 $p>q$，所以操作一 $\frac{p}{q} > \frac{p+1}{q+1}$ 一定不优。那么优先操作二，不能操作时对以前的 $s_i=0$ 反悔即可。时间复杂度 $O(n)$。
### B.数学作业（原题：？）
**题目大意**
共有 $n$ 个学生 $m$ 个城市，第 $i$ 个学生要选择去 $a_i$ 和 $b_i$ 的其中一个。若有奇数个人去同一个城市，那么就需要仆从随行。最小化需要的仆从数。
$1\le n,m\le 10^5$。
**分析与做法**
第一次一眼结论题。
这种题显然将 $a_i,b_i$ 连边。结论：对于一个联通块，需要的仆从数最多就是其边数模二的值。
证明：用 $0$ 和 $1$ 来表示点的奇偶性，那么反转一个人要去的城市，对于 $a_i$ 和 $b_i$ 的影响要么是减少/增加两个 $1$，要么是 $0,1$ 换位。于是一个包含 $x$ 个 $1$ 的联通块最少剩下 $x\bmod 2$ 个 $1$。而最初 $1$ 的个数就是边数。
构造：用类拓扑排序的方法即可。
实现：并查集维护父亲和边数，时间复杂度 $O(n\alpha(m))$。深搜时间复杂度 $O(m)$。
### C.手牌收益（原题：？）
**题目大意**
通过给定随机代码得到长度为 $n$ 的序列 $a$。求：
$$\sum_{1\le i<j<k\le n}{(a_i\bigoplus a_j)\lor a_k}$$
对 $2^{64}$ 取模。$3\le n\le 4\times 10^6,0\le a_i<2^{64}$。
**分析与做法**
拆位，枚举 $k$，顺便分类统计就行了。时间复杂度 $O(64n)$。
### D.音乐变奏（原题：？）
**题目大意**
给定长为 $n$ 的序列 $a$ 和参数 $k,m,c,d$。可以选择一个长为 $m$ 的区间 $[l,r]$ 加上一个首项为 $c$，公差为 $d$ 的等差序列。求最后序列第 $k$ 大数的最大值。
$1\le k,m\le n\le 2\times 10^5,0\le c,d,a_i\le 10^9$。
**分析与做法**
考虑二分答案 $x$。
对于一个数 $a_i$ 可以找到区间 $[l_i,r_i]$ 表示对于所有的 $i\in [l_i,r_i]$，以 $i$ 为等差数列起点，可以使 $a_i\ge x$。维护一个数组 $f$，$f_i$ 表示以 $i$ 为起点加等差数列可以让多少个 $a_i\ge x$。那么 $[l_i,r_i]$ 相当于区间加 $f$。
将 $f$ 差分后单点修改即可。特殊的，若一开始 $a_i\ge x$，那么 $f_1$ 加一。时间复杂度 $O(n\log V)$。
## 2024/10/24
### A.最小环计数（原题：？）
**题目大意**
给定 $n$ 个点 $m$ 条边的无向图，求本质不同的长度最小的环的个数。环长至少为 $3$。当两个环的边不完全相同时，称这两个环本质不同。
$1\le n\le 3000,0\le m\le 6000$。
**分析与做法**
考虑如何寻找环，枚举每一条边 $(u,v)$，如果将这条边断掉，那么从 $u$ 到 $v$ 的最短路再加上这条断掉的边就是一个环。因为边没有边权（或者说都为 $1$），所以直接宽搜得到最短路径和最短路径的方案数，更新即可。时间复杂度 $O(m(n+m))$，注意最后的答案还要除以最小环的环长。
也可以直接从点的方向考虑，假设从 $x$ 开始宽搜，那么更新最短路和方案数。若第二次到达某个点 $u$，假设是从 $v$ 到达的，那么就找到了一个长为 $d_u+d_v+1$ 的环。环长取 $\min$，同时计数即可。这样的时间复杂度是 $O(n(n+m))$ 的。
### B.枚举（原题：？）
**题目大意**
给定 $N,N_3,P$。有 $N_0=N^2+1,N_1=N_0\bmod a,N_2=N_1+b,N_3=N_2\bmod c$。求有多少整数三元组 $(a,b,c)$ 满足以上式子，且 $0\le a,b,c\le P$。并按字典序递增输出前 $10^5$ 对。
$0\le N_3,N\le P,1\le P\le 10^5$。
**分析与做法**
注意到 $\lfloor \frac{N_2}{c} \rfloor \times c + N_3 = N_2$，于是可以枚举 $c$ 和 $\lfloor \frac{N_2}{c} \rfloor$ 从而将 $N_2$ 和 $c$ 对应起来，这部分可以 $O(P\log P)$ 。接下来考虑字典序的问题，首先枚举 $a$，那么 $N_1$ 就是已知的了。于是对于已知的 $N_1$，可以发现 $N_2\in [N_1,N_1+P]$，我们在对应的时候做一个前缀和就可以知道这个区间内符合要求的 $b$ 的数量了。至于输出，可以前缀和的时候链表指一下，枚举即可。时间复杂度 $O(P\log P)$。
### C.保守主义（原题：？）
**题目大意**
定义由两个字符交替组成的字符串是好的。给定长为 $n$ 的字符串 $S$ 和 $q$ 组询问，每组询问给定 $1\le l\le r\le n$，求在 $S$ 的子串中好的最长子序列的长度以及组成这个好的子序列的两个字符。
$1\le n\le 1.5\times 10^6,1\le q\le 10^5$。
### D.考拉的一天（原题：？）
**题目大意**
太长了，咕了。
## 2024/10/25
### A.星际地图（原题：？）
**题目大意**
给定 $n\times m$ 的网格，每个网格为 $0$ 或 $1$，一个 $k$ 行“星际螺旋结构”定义如下：
- 对于第 $i\le k-1$ 行，有 $2i-1$ 个 $1$。特殊的，第 $k$ 行有 $1$ 个 $1$。
- 所有 $1$ 居中对齐。
求地图中星际螺旋结构的数量。$1\le n\le 500$。
**分析与做法**
对每行前缀和一下，然后直接枚举结构起点就行了。时间复杂度 $O(n^3)$。
### B.查找（原题：？）
**题目大意**
给定长为 $n$ 的序列 $A$ 和长为 $m$ 的序列 $B$ 以及常数 $x$，通过以下代码生成 $L$。
```python
def generate_list(A,B,x):
n=len(A)
m=len(B)
L=[]
for i in range(min(n,m-x)):
for j in range(i+x,m):
L.append(A[i]*B[j])
return L
```
求序列 $L$ 中第 $k$ 小的数。$2\le n,m\le 2\times10^5,1\le x\le m,1\le |A_i|,|B_i|\le 2\times 10^5,1\le k\le |L|$。
**分析与做法**
应当可以想到正负需要分讨。接着考虑二分答案，这样可以直接查找一个 $A_i$ 在 $B$ 中的对应区间。具体地，对于每一次检查，倒着将 $B_j$ 分正负加入数据结构里，并且记录一下加入的数的正负的个数，那么对于每一个 $A_i$ 进行分讨即可。时间复杂度 $O(n\log n\log V)$。
```c++
for(int i=m;i>min(n,m-x)+x;i--)
{
T.Add(b[i],1,(b[i]>0?1:0));
na+=(b[i]<0); po+=(b[i]>0);
}
for(int i=min(n,m-x)+x,j=min(n,m-x);j>=1;i--,j--)
{
na+=(b[i]<0); po+=(b[i]>0);
T.Add(abs(b[i]),1,(b[i]>0?1:0));
if(a[j]>0)
{
if(mid>=0) ret+=na+T.Query(mid/a[j],1);
if(mid<0) ret+=na-T.Query((-mid-1)/a[j],0);
}
else
{
if(mid>=0) ret+=po+T.Query(mid/(-a[j]),0);
if(mid<0) ret+=po-T.Query((-mid-1)/(-a[j]),1);
}
}
```
### C.排列审美（原题：？）
**题目大意**
对于长为 $n$ 的排列 $A$，若 $\forall i\in[1,n]\cap\mathbb{Z},A_{A_i}=i$，那么这个排列是符合审美的。
对于长为 $k$ 的排列 $B$，求有多少符合审美的长度为 $n$ 的排列 $A$ 使得 $B$ 是它的子序列。
$1\le k\le n\le 200$。
**分析与做法**
### D.黑暗地牢（原题：？）
**题目大意**
有排成一列的 $n$ 个敌人，血量为 $h_i$。当 $h_i\le 0$ 时该敌人死亡，后面的人补位，一开始一号最前。有五种操作：
- 消耗 $m_A$，对第一个敌人造成 $d_A$ 伤害。
- 消耗 $m_B$，对第一个敌人造成 $d_B$ 伤害。
- 消耗 $m_C$，对第一个敌人造成 $d_C$ 伤害。
- 消耗 $m_D$，对第一个敌人造成 $d_D$ 伤害。
- 消耗 $m_E$，对前四个敌人各造成 $40000$ 伤害。
求击败所有敌人的最小消耗。
$1\le n\le 20,1\le d_A,d_B,d_C,d_D\le 2\times 10^4,1\le m_A,m_B,m_C,m_D,m_E\le 500,1\le h_i\le 10^6$。
**分析与做法**
又臭又长的 DP，咕了。
## 2024/10/31
### A.究曼哈顿距离（原题：？）
**题目大意**
给定 $n$ 个点，第 $i$ 个点坐标为 $(x_i,y_i)$，求最大的两点 $i,j$ 的曼哈顿距离与欧几里得距离的比值。$2\le n\le 10^6,0\le |x_i|,|y_i|\le 10^9$。
**分析与做法**
我们充分发扬人类智慧，旋转坐标系后按照 $x$ 和 $y$ 都排序，那么答案的两个点不会隔太远，所以每个点都和其后的 $10$ 个点计算答案，这样跑的飞快，$n\le 10^6$ 都能在 $1s$ 内过。
好了上述做法是正确的，证明如下：我们考虑对于两个点，画出其曼哈顿距离和欧几里得距离，那么其比值就是直角三角形与两条直角边的和的比值。根据数学相关知识，夹角趋近于 $45^\circ$ （或 $135^\circ$）时最优。那么旋转坐标系之后点 $(x,y)$ 变为 $(\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}})$，那么问题变为找两个点，使其连线与 $x$ 轴（或 $y$ 轴）夹角最小。按照 $x$ 排序后相邻两点的连线就是唯一可能贴近 $y$ 轴的取值，按照 $y$ 排序后相邻两点连线就是唯一可能贴近 $x$ 轴的取值。时间复杂度 $O(n\log n)$。
### B.连通图（原题：[Halftree](https://www.luogu.com.cn/problem/AT_arc152_d)）
**题目大意**
去原题看。
**分析与做法**
注意到同余最短路中的转圈技巧，$i\rightarrow (i+k)\bmod n$ 会产生 $g=\gcd(n,k)$ 个环，环长是 $\frac{n}{g}$。且显然 $n$ 是偶数的时候无解，那么有解时断环为为链，链长一定为偶数，$g$ 一定奇数。所以问题转化为将 $g$ 条链连接。之后随便搞搞就行了，时间复杂度 $O(n)$。
### C.括号游戏（原题：[Bracket Insertion](https://www.luogu.com.cn/problem/CF1781F)）
**题目大意**
去原题看。
**分析与做法**
做法很厉害，但是不怎么会说。主要思想是提项然后加入辅助数组优化计算，时间复杂度 $O(n^3)$。
### D.世界和平（原题：？）
**题目大意**
给定长为 $n$ 的序列 $a$，有两种操作：
- 消耗 $x$ 使区间 $[1,x]$ 减 $1$。
- 消耗 $x$ 使区间 $[n-x+1,n]$ 减 $1$。
求使 $\forall i\in[1,n]\cap\mathbb{Z},a_i\le0$ 的最小代价。多组测试数据。
$1\le T\le 10,1\le n\le 10^5,1\le a_i\le 10^9$。
**分析与做法**
咕咕咕。
## [后续](https://www.luogu.com.cn/article/0llz1lnd)