十一月模拟赛回顾
Rem_CandleFire
·
·
个人记录
前情
2024/11/04
A.反转（原题：Pushpush）
题目大意
给定长为 n 的序列 a 和空序列 b，对于 i=1,2,\dots,n 依次进行如下操作：
求最终序列。1\le n\le 10^6。
分析与做法
找规律直接输出就行。时间复杂度 O(n)。
for(int i=n;i>=1;i-=2) printf("%d ",a[i]);
for(int i=1+(n&1);i<=n;i+=2) printf("%d ",a[i]);
B.物流（原题：？）
题目大意
平面上有 n 个点，第 i 点的坐标是 (x_i,y_i)。两个点 i,j 之间的道路的成本为 |x_i-x_j|^3+|y_i-y_j|^3。有 q 个事件，每个事件给出 u_i,v_i,c_i 表示可以选择在点 u_i,v_i 之间建成本为 c_i 的边。要求第一个事件之前与每个事件之后，求使任意两点都能互通的最小总成本。每一次选择是否建边是不独立的。
**分析与做法**
在第一个事件之前，显然使用 Prim 算法得到最小生成树。随后对于每个事件的 $u_i,v_i,c_i$，先对树搜索得到深度和父亲的信息，暴力跳 $u_i,v_i$ 到其 lca 处，求得最大边。判断是否需要断掉最大边，连给出的这条边。使用链式前向星可以方便地删边。时间复杂度 $O(n(n+q))$。
### C.序列（原题：？）
**题目大意**
给定长为 $n$ 的序列 $a,b$，可以任意交换 $a$ 中的两个元素。最小化 $\sum_{i=1}^n{(a_i-b_i)^2}$ 并求出使得其最小的最小交换次数。保证 $a,b$ 各自没有相同元素。
$1\le n\le 3\times10^5,1\le a_i,b_i\le 10^9$。
**分析与做法**
事实上需要最大化 $\sum_{i=1}^n{a_ib_i}$。有排序不等式：对于 $a_i<a_j,b_i<b_j$，则 $a_ib_i+a_jb_j\ge a_ib_j+a_jb_i$，作差因式分解易证。推广得，当 $a,b$ 皆有序时，上式最大。接下来认为 $a,b$ 已离散化。已 $b_i$ 为基准交换 $a$ 中的元素，那么记录一下每个位置应该到哪里，随后扫一遍需要换就直接换。时间复杂度 $O(n\log n)$。交换的过程可以想象环来理解。
### D.魔法阵（原题：？）
**题目大意**
魔法阵是一个任意大小的方阵，满足：
- 设位置 $(i,j)$ 有 $a_{i,j}$ 个魔法石，则 $a_{i,j}\ge m$。
- 设魔法阵大小为 $k$，那么任意从魔法阵选出 $k$ 个格子，满足任意两个格子不同行也不同列，那么选出的格子魔法石数量和都相等。
- 每条对角线魔法石的和不超过 $n$。
现在有无限多魔法石，求满足条件的魔法阵有多少种。$T$ 组测试数据。
$1\le T\le 50,1\le n,m\le 10^5$。
**分析与做法**
注意到第二个条件，如果有序列 $x_i,y_i$，那么 $a_{i,j}=x_i+y_j$ 符合条件（因为任意选出来的和都是 $\sum x_i+y_i$）。然而从序列到魔法阵的映射并不是双射，经典操作是：钦定 $\min(x_i)=0$，那么这样就可以构成双射了。而对于条件一，不妨直接让所有 $y_i$ 都减去 $m$。那么问题转化为将 $n-km$ 个石子填入 $2k$ 个位置中，并保证前 $k$ 个位置至少有一个是 $0$。根据组合数学推一下式子可得答案为 $\binom{n-km+2k}{2k}-\binom{n-km+k}{2k}$。
枚举魔法阵大小 $k$ 然后求一下组合数即可。时间复杂度 $O(\sum\lfloor\frac{n}{m}\rfloor)$。
## 2024/11/11
### A.卡牌（原题：？）
**题目大意**
给定长为 $2n$ 的序列 $a$，一开始 $a_i=i$。每次操作将 $\{a_1,a_2,\dots,a_{2n-1},a_{2n}\}$ 变为 $\{a_1,a_{n+1},\dots,a_n,a_{2n}\}$。询问要进行多少次操作才能将序列变回初始状态。
$1\le n\le 10^{14}$。
**分析与做法**
找规律可以发现，答案就是最小的使得 $2^{x-1}\equiv n\pmod m$ 的 $x$，其中 $m=2n-1$。变形得 $2^x\equiv 2n\equiv 1\pmod m$。那么问题转化为求 $2$ 关于模 $m$ 的阶 $\delta_m(2)$。根据欧拉定理 $a^{\phi(n)}\equiv 1\pmod n$ 且有性质 $\delta_m(a)\mid \phi(m)$，得出做法：先求出 $\phi(m)$，然后枚举其质因数做一个快速幂判断是否成立即可。所有成立的 $x$ 取最小值。时间复杂度 $O(\sqrt{m}+d(p)\log p)$，其中 $p=\phi(m),d(i)$ 表示 $i$ 的约数个数。
### B.异或（原题：[XOR Replace](www.luogu.com.cn/problem/AT_agc016_d)）
**题目大意**
给定长为 $n$ 的序列 $a,b$，每次操作可以将 $a_i$ 替换为整个序列的异或和，问最少几步可以将 $a$ 变为 $b$。$2\le n\le 10^5$。
**分析与做法**
先看一次操作事实上是做什么。假设当前序列异或和为 $a_{n+1}=X$，那么替换了 $a_i$ 之后异或和就变为了 $a_i$，也就是说一次操作是交换 $(a_i,a_{n+1})$，于是套路地，给每个值标号后连边，每条边就是一次交换。如果图不联通，那么答案还要加上联通块的个数（因为需要先把 $a_{n+1}$ 打进去然后内部交换，特殊的，如果 $X$ 在某个联通块里，答案就减 $1$）。无解是判定是否 $a\cup\{X\}\subseteq b$ 。时间复杂度 $O(n\log n)$，因为需要 STL 判断无解和重编号。
### C.树（原题：[Paint Tree](https://www.luogu.com.cn/problem/AT_arc108_f)）
**题目大意**
去原题看。
**分析与做法**
设路径 $(S,T)$ 是树的直径，那么当 $S$ 和 $T$ 同色时答案为 $2^{n-2}d$，下面考虑不同色的情况。
记 $dis_{0/1,u}$ 表示从点 $S/T$ 到点 $u$ 的距离，那么可能的染色权值下界为 $L=\max\{\min(dis_{0,u},dis_{1,u})\}$，上界为 $R=dis_{0,T}$。于是枚举权值 $d\in[L,R]$，那么所有 $dis_{0,i}>d$ 的 $i$ 要与 $T$ 同色，$S$ 同理，满足 $dis_{0,i}\le d,dis_{1,i}\le d$ 的 $i$ 的数量记为 $c_i$。对于枚举的 $d$，到直径两端点距离均小于 $d$ 的点的染色方式无关紧要，所以染色方案数为 $2^{c_d}-2^{c_{d-1}}$。
所以不同色的贡献就是 $\sum_{d=L}^{R}{d\times(2^{c_d}-2^{c_{d-1}})}$。因为 $S,T$ 颜色可以改变，所以以上两种情况都要乘上 $2$。
接下来考虑具体实现，可以在求 $L$ 时得到 $c_i$ 的差分数组，加起来就行，其它可以通过深搜得到。总时间复杂度为 $O(n)$。
### D.路径（原题：[Attraction on Tree](https://www.luogu.com.cn/problem/AT_arc152_f)）
咕咕咕。
## 2024/11/12
### A.魔法师（原题：？）
NOIp 模拟赛 T1 考 A* 还是太超前了。
**题目大意**
$n$ 个怪物，击杀第 $i$ 个怪物会获得法术 $i$ 并替换掉上一个法术。用法术 $i$ 击杀怪物 $j$ 将耗费时间 $w_{i,j}$ 和法力值 $c_{i,j}$。现在给定法力值上限 $m$，求最快击杀所有怪物的顺序，若无解输出 $-1$。若多解，输出字典序最小的顺序。例如 $2,10$ 字典序小于 $10,2$。击杀第一个怪物不需要花费。
$3\le n\le 18,0\le m\le 10^9,0\le w_{i,j}\le 10^6,0\le c_{i,j}\le 10^6,w_{i,i}=c_{i,i}=0$，保证数据随机生成。
**分析与做法**
无法状压 DP，考虑暴搜剪枝。设计得估价函数 $f,g$ 表示在只考虑时间和魔法值其中之一的情况下的最优解，那么搜索到阶段 $S$ 时判断当前消耗加上函数是否在允许范围内（魔法值是否超出上限 $m$，时间是否多于当前最优解），如果否，那么剪枝。估价函数可以通过状压 DP 得到，时间复杂度 $O(\mathrm{not TLE})$。
### B.二叉搜索树（原题：[Jelka](https://www.luogu.com.cn/problem/P11306)）
**题目大意**
给定 $n$ 个点，以 $1$ 为根的二叉树，有点权。$q$ 次修改，每次修改一个点权，询问在每次修改之后求出有多少个点 $u$ 满足以 $u$ 为根的子树是二叉搜索树。
$1\le n,q\le 2\times10^5$。
**分析与做法**
显然只需要考虑每次修改的点 $x$ 对答案的影响，那么首先得到不修改时有多少个点满足条件，这是简单的。考虑二叉搜索树的性质，发现若一棵树是二叉搜索树，那么其中序遍历应当不降。于是中序遍历树得到点 $u$ 为根的子树的区间 $[L_u,R_u]$。用树状数组维护中序遍历序列 $a$，把所有 $a_i> a_{i+1}$ 的位置 $i$ 加入树状数组。那么查询某点 $u$ 是否合法，只需要看 $[L_u,R_u]$ 的值是否等于 $0$。而且点权只会影响该点到根的路径，合法的点一定连续，于是树上倍增即可。
具体的对于每次修改 $x,v$，撤销 $x$ 的影响，修改树状数组，加入新的点权的影响。时间复杂度 $O(n\log^2n)$。
### C.枚举（原题：？）
咕咕咕。
### D.同构（原题：？）
咕咕咕。
## 2024/11/13
非常好的 NOIp 模拟赛，非常好的搬运十三连测，非常好的三紫一黑。
### A.按位或（原题：[A or ... or B Problem](https://www.luogu.com.cn/problem/AT_agc015_d)）
**题目大意**
在区间 $[L,R]$ 中选择任意多个数进行按位或，求可能的结果的数量。$1\le L\le R\le 2^{60}$。
**分析与做法**
非常好的构造，使我的大脑旋转。
因为按位或操作不会使数变小，于是考虑如何构造出大于 $R$ 的结果。首先将 $L,R$ 二进制表示的相同前缀去掉，此时 $R$ 最高位为 $1$，$L$ 对应位置为 $0$。接下来可以从是否保留 $L$ 的最高位进行讨论。
如果保留，那么有如下构造：
```
R=100010101101
L=001000010100
D=111111111111
X=100000000000
```
如上，$D$ 是可以构造出的最大值，$X|A$ 是可以构造出的最小值，在区间 $[X|A,D]$ 中的数都是可以被构造的。
如果不保留，那么有如下构造：
```
R=100010101101
L=001000010100
Y=100010000000
F=100011111111
```
如上，$F$ 是可以构造出的最大值，$R$ 是可以构造出的最小值，在区间 $[R,F]$ 中的数都是可以被构造的。
特殊的，$[L,R]$ 本身也是可以被构造的。所以答案就是三个区间交集内的数的数量。实现是简单的，时间复杂度 $O(\log V)$。
### B.序列（原题：[划艇](https://www.luogu.com.cn/problem/P3643)/[Good Contest](https://www.luogu.com.cn/problem/CF1295F)）
略。
### C.括号匹配（原题：[Bracket Walk](https://www.luogu.com.cn/problem/AT_arc173_d)）
**题目大意**
太长了，去原题看。
**分析与做法**
注意到图是强联通的有向图，所以肯定和环有关。首先套路地将 `(` 记为 $1$，`)` 记为 $-1$，那么一条合法路径的边权和应当为 $0$。另外，如果一个不合法括号串中左右括号数量相等，那么一定可以改变路径起点使其合法。如果图中同时出现正环和负环，那么存在路径，若正/负环单独存在，则不存在合法路径。证明容易感性理解。使用 Bellmen Ford 算法找环，时间复杂度 $O(nm)$。
### D.苹果（原题：[Black Radius](https://www.luogu.com.cn/problem/AT_agc008_f)）
咕咕咕。
## 2024/11/14
### A.Alice 的数（原题：？）
**题目大意**
给定区间 $[L,R]$，对每一个 $i\in[L,R]\cap\mathbb{Z}$ ，距离其最近的完全平方数记为 $j^2$，若 $j$ 是奇数，则答案加 $i$，否则答案减 $i$。求最终答案，对 $10^9+7$ 取模。
$1\le L\le R\le 10^{18}$。
**分析与做法**
$[L,R]$ 的答案等于区间 $[1,R]$ 减去 $[1,L-1]$，而以 $1$ 为端点是简单的，于是就做完了。接下来看看一个智障的考场做法。
考虑一个完全平方数 $i^2$ 对答案的影响，区间 $[i^2-i+1,i^2+i]$ 距离 $i$ 比距离 $i-1$ 和 $i+1$ 都要近，于是其贡献就是这一段的和，等差数列求得为 $2i^3+i$。那么对于 $L,R$，先把两端处不完整的区间处理掉，剩下的就是 $x\sim y$ 这一段完整的区间，即 $[x^2-x+1,y^2+y]\subseteq[L,R]$。该段答案为 $\sum_{i=x}^y{(-1)^{i+1}(2i^3+i)}$。
注意先判掉 $\lfloor\sqrt{R}\rfloor-\lfloor\sqrt{L}\rfloor\le1$ 的情况，接下来就可以愉快地推式子了，钦定 $x$ 为奇数，否则先处理掉。
$$
\begin{aligned}
\sum_{i=x}^y{(-1)^{i+1}(2i^3+i)} &= \sum_{i=x}^y{(2i^3+i)}-\Delta\\
&=2\sum_{i=x}^yi^3+\frac{(y-x+1)(x+y)}{2}-\Delta\\
&=2(\sum_{i=1}^yi^3-\sum_{i=1}^{x-1}i^3)+\frac{(y-x+1)(x+y)}{2}-\Delta\\
&=2[(\sum_{i=1}^yi)^2-(\sum_{i=1}^{x-1}i)^2]+\frac{(y-x+1)(x+y)}{2}-\Delta\\
&=2[(\frac{y^2+y}{2})^2-(\frac{x^2-x}{2})^2]+\frac{(y-x+1)(x+y)}{2}-\Delta
\end{aligned}
$$
令 $n=\lfloor\frac{x+1}{2}\rfloor,m=\lfloor\frac{y}{2}\rfloor$。
$$
\begin{aligned}
\Delta &= 2\sum_{i=n}^{m}{2(2i)^3+(2i)}\\
&= 32\sum_{i=n}^m{i^3}+4\sum_{i=n}^m{i}\\
&= 32[(\frac{m^2+m}{2})^2-(\frac{n^2-n}{2})^2]+2(m-n+1)(n+m)
\end{aligned}
$$
判掉特殊情况和处理两端都是简单的，中间将两部分式子合并即可。注意取模和 `__int128` 的使用。时间复杂度 $O(1)$，常数极大。
### B.bob 的图（原题：？）
**题目大意**
给定 $n$ 个点，$m$ 条边的有向图，边有边权。从 $1$ 到 $u$ 可能有 $n_u$ 条最短路径（边权和最短），第 $i$ 条路径的边数为 $d_{u,i}$。求 $\sum_{i=1}^n{\sum_{j=1}^{n_i}{\sum_{k=j+1}^{n_i}}}{d_{i,j}\times d_{i,k}}$。对 $10^9+7$ 取模。
$1\le n\le 10^5,1\le m\le 2\times 10^5$。
**分析与做法**
诈骗题，答案为 $\frac{1}{2}\sum_{i=1}^n{\bigg((\sum_{j=1}^{n_i}d_{i,j})^2-(\sum_{k=1}^{n_i}{d_{i,k}^2})}\bigg)$。
记 $f_u,g_u,h_u$ 表示到点 $u$ 的边数零次方之和，一次方之和，二次方之和。那么在求最短路过程中，对于可以用于更新的边 $(u,v)$，有 $f_v\leftarrow f_u+f_v,g_v\leftarrow g_v+g_u+f_u,h_v\leftarrow h_v+h_u+2g_u+f_u$。那么答案为 $\frac{1}{2}\sum_{i=1}^n{g_i^2-h_i}$。时间复杂度 $O(n\log n)$。注意用 Dijkstra 求最短路时要使用辅助数组免得进入两次队列导致重复计算。
### C.维护数列（原题：？）
**题目大意**
给定长为 $n$ 的序列 $a$，有 $m$ 次操作，操作共四种：
- 查询 $[l,r]$ 区间的和。
- 查询 $[l,r]$ 区间的平方和。
- 对区间 $[l,r]$ 的每个数除以 $p(p\not=0)$，注意将 $a_i\leftarrow [\frac{a_i}{p}]$，中括号是高斯取整函数。
- 修改 $a_i$ 为 $v$。
$1\le n,m\le 10^5,-10^9\le a_i,v,p\le 10^9$。
**分析与做法**
显然是套路题，注意当一个区间全是 $0$ 和全是 $-1$ 时是否返回的判断。线段树要维护的是区间和，区间平方和，区间最小值，区间最大值。时间复杂度 $O(n\log n)$。
### D.大头问题（原题：？）
咕咕咕。
## 2024/11/15
### A.对数（原题：？）
**题目大意**
给出正整数 $n$，询问有多少整数对 $(x,y)$ 满足 $x,y\in[0,n],x\bigoplus y=x\mid y$，其中 $\bigoplus$ 表示按位异或，$\mid$ 表示按位或。$n$ 以二进制方式给出。
$1\le n \le 2^{1000000}$。
**分析与做法**
设 $x,y$ 二进制表示的第 $i$ 位为 $x_i,y_i$。那么可以进行数位 DP，即 $f_{p,0/1,0/1}$ 表示第 $p$ 位时 $x,y$ 是否顶格 $n$。然后对 $n_i$ 分类讨论即可，每次转移共 $8$ 种情况，使用记忆化搜索实现。时间复杂度 $O(\log n)$。
### B.连通图（原题：[Inverted](https://codeforces.com/gym/104787/problem/M)]）
咕咕咕。
### C.函数（原题：[Knocker](https://codeforces.com/gym/105384/problem/K)）
咕咕咕。
### D.划分（原题：？）
咕咕咕。
## 2024/11/16
### A.硬币游戏（原题：？）
**题目大意**
有排成一列的 $n$ 枚硬币，每次操作可以交换相邻两个，询问最少多少次操作才能使同一面朝上的硬币都排在一起。$1\le n\le 2\times10^5$。
**分析与做法**
显然最终状态只有两种，直接求到达该状态需要的操作次数即可。时间复杂度 $O(n)$。
### B.世界赛（原题：？）
普通模拟，水题，略。
### C.道路翻修（原题：？）
**题目大意**
一个 $n$ 个点 $m$ 条边的图，一个生成树的权值是其中最大边权。共 $m$ 次事件，第 $i$ 次事件使得第 $i$ 条边不能使用。求该图最小权值生成树的权值平均值（若断掉某条边图不连通则不考虑）。
$1\le n\le 10^5,1\le m\le 2\times 10^5$。
**分析与做法**
首先建出最小生成树，此时权值为 $s$。断边不在树上的情况有 $m-n+1$ 种，现在考虑断边在树上的情况。对于该树之外的某条边 $(u,v,w)$，则树路径 $D(u,v)$ 中的所有边都可以用 $w$ 进行更新。设 $u,v$ 的 LCA 为 $rt$，则该边的影响就是路径 $D(rt,u),D(rt,v)$。设 $f_u$ 表示断掉 $u$ 和其父亲这条边可以用于替换的最小边权。类似树上差分，在 $u,v$ 处加入可以用于更新的 $w$，在 $rt$ 处减去（加了几遍就减几遍），自下而上求 $f$。保存和删除可以使用 `multiset` ，使用启发式合并维护，那么 $f_u$ 就是可重集中的第一个元素。对所有 $f_i$ 与 $s$ 取较大值加入答案，方案数加一。当可重集为空时说明此边不可断，略过即可。
时间复杂度 $O(m\log^2m)$。当然可以树剖加个数据结构维护，但码量太大了。还可以换个 $f$ 的定义然后并查集维护一下做到单 $\log$，但我不会。
### D.聚会（原题：？）
**题目大意**
二维平面上有 $n$ 个点，第 $i$ 个点坐标 $(x_i,y_i)$。路径只能沿着网格或对角线走，一条边长度分别为 $1$ 和 $\sqrt{2}$。定义两点 $x,y$ 的距离 $d(x,y)$ 为最短路径的长度。$q$ 次询问，每次询问 $[l,r]$ 的人两两距离的最大值。
$1\le n\le 10^5,1\le q\le 3\times 10^5$。
**分析与做法**
咕咕咕。
## 2024/11/18
### A.足球（原题：？）
**题目大意**
计算 $\sum_{i=l}^{r}{\lfloor \frac{2^i}{3}} \rfloor $。$1\le l\le r\le 10^{18}$，答案对 $10^9+7$ 取模。
**分析与做法**
答案为 $[1,r]$ 的值减去 $[1,l-1]$ 的值。考虑 $2^i \bmod 3$，发现是 $2,1,2,1,\dots$，于是直接套公式算出 $\sum 2^i$ 再减去余数，就可以不用下取整，直接乘上 $3$ 的逆元。时间复杂度 $O(\log r)$。
### B.整数（原题：？）
**题目大意**
给定长为 $m$ 的排列 $b$，有 $n$ 个数 $a_1,a_2,\dots,a_n$，每次操作是遍历 $n$ 个数，将 $a_i$ 改为 $b_{a_i}$。现在 $a_i$ 都是在 $1\sim m$ 之间等概率随机的整数，求期望多少次操作才能将所有 $a_i$ 变回原样。对 $10^9+7$ 取模。
$1\le n\le 10^5,1\le m\le 100$。
**分析与做法**
显然这样的变换会形成若干个环，而注意到长度不同的环最多只有 $13$ 个，在长度相同的环中的点并无本质区别。我们二进制枚举哪些环被选中出现在最终的 $a$ 序列中，操作次数就是被选中的环长的 LCM。考虑当前选中了 $k$ 个环，环长分别为 $c_1,c_2,\dots,c_k$，环长为 $c_i$ 的环的个数为 $d_i$，要求这样选的方案数。$f_S$ 表示选的集合为 $S$ 的可选择位置有多少个，有转移 $f_S=f_{S\setminus T}+c_T\times d_T$，$T$ 表示 $S$ 的最低位。那么假设当前枚举的全集为 $U$，子集为 $S$，方案数就是 $Z_S(f_U-f_S)^n$，其中 $Z_S$ 表示集合 $S$ 的正负号，用于容斥，一开始 $Z_0=1$。这部分内容可以对照十二重计数法中的类型一、三理解。最后方案数要乘上 $U$ 的 LCM，最后的答案要除以 $m^n$，因为算的是期望。时间复杂度 $O(3^q\log n)$，其中 $q$ 是长度不同的环的个数，$\log n$ 是快速幂。
### C.异或（原题：？）
咕咕咕。
### D.力神（原题：？）
咕咕咕。
## 2024/11/19
乱搞场。
### A.交换（原题：？）
**题目大意**
给定正整数 $n,k$，$n$ 可能有前导零。可以交换 $n$ 中相邻数码任意次，设交换了 $x$ 次得到了数 $m$，求最大的使 $m-xk$ 最大的 $m$。
$1\le n\le 10^{100000},1\le k\le 10^{16}$。
**分析与做法**
注意到 $k$ 很小，所以 $n$ 的最低 $19$ 位左右才需要考虑 $k$ 的限制，前若干位只需要贪心从大到小放就行。接下来考虑剩下 $19$ 位数的情况。可以状压，但是贪心更好。对于当前位 $i$，枚举将哪一个数码交换最好。设 $v_i=10^i$，那么将数码 $j$ 从位置 $k$（即 $a_k=j$）交换到位置 $i$ 会使 $m-xk$ 增加 $\Delta_j=jv_i+sv_k-sv_{k+1}-jv_k-m(i-k)$，这里的位置 $i$ 是指作为十进制数该位为 $10^i$。那么取 $\max_{j=9}^{n_i+1}{\Delta_j}$ 的 $j$ 交换是最优的。这部分的时间复杂度是 $O(|n|^2)$。总的时间复杂度是 $O(|n|)$。
### B.好的字符串（原题：？）
**题目大意**
给定 $n$ 个长度为 $m$ 的 01 字符串 $s_1,s_2,\dots,s_n$。一个长度为 $nm$ 字符串 $S$ 是好的，当且仅当 $S[1:m],S[m+1:2m],\dots,S[(n-1)m+1:nm]$ 这 $n$ 个子串两两不同，且每个子串均为给定子串的其中一个。现有编码机，按下对应数字均有 $p$ 的概率得到该数，$1-p$ 的概率得到另一个。求恰能打出一个好的字符串的概率。
$1\le n,m\le 1000,0\le p\le 1$。
**分析与做法**
对 $n$ 个串建出 Trie 树。那么对于一个点 $u$，其可以选择走左儿子 $0$，也可以走右儿子 $1$，把它的所有决策视为一个字符串 $T_u$。设点 $u$ 的左/右儿子被 $c_{u,0/1}$ 个字符串经过，那么一个好的字符串的 $T_u$ 应当恰好包含 $c_{u,0}$ 个 $0$ 和 $c_{u,1}$ 个 $1$。设 $f_{i,j}$ 表示打出 $i$ 个 $0$，$j$ 个 $1$ 的概率，则有 $f_{i,j}=\max(pf_{i-1,j}+(1-p)f_{i,j-1},pf_{i,j-1}+(1-p)f_{i-1,j})$。最终答案就是 $\prod f_{c_{u,0},c_{u,1}}$。时间复杂度 $O(nm)$。特殊的，当 $i\ge j$ 时前者大于等于后者，反之同理，原因若 $i+j$ 恒定，则 $i,j$ 越接近时 $f_{i,j}$ 越大。
### C.网格（原题：？）
**题目大意**
给定 $n\times m$ 网格图，其中 `.` 表示空地，`#` 表示障碍。选出恰好两个不同的障碍使其变为空地并使 $(1,1)$ 和 $(n,m)$ 联通。求方案数。
$1\le n,m\le 1000$。
**分析与做法**
设障碍共有 $k$ 个，若不需要打通障碍就能联通，答案为 $\frac{k(k-1)}{2}$。否则设恰好打通一个障碍就能联通的情况有 $t$ 种，则答案首先有 $t(k-t)+\frac{t(t-1)}{2}$。这两种情况是简单的，只需要从 $(1,1)$ 和 $(n,m)$ 各做一次宽搜打上标记即可（如果一个障碍同时有两种标记，则 $t$ 加一）。
考虑恰好要删除两个的情况。分成两个障碍相邻，和联通块 $A\rightarrow C\rightarrow B$ 两种情况。通过并查集联通块容斥一下就行。时间复杂度 $O(nm)$。以下是乱搞：
考虑在宽搜时没有被打标记的空地，从空地可以搜索到打上两种标记的障碍分别为 $x,y$ ，那么其所在联通块作为中间联通块 $C$ 的贡献就是 $xy$。再遍历用打上的标记特判一下两个障碍物相邻的情况。最终答案就是上述情况加在一起。这样可能会算重，但是数据范围较小时可以直接暴力枚举两个障碍物打通判断是否可行，较大时数据随机能造出形如以下结构的可能性较低，综上所述能够拿到大部分分数。在模拟赛中，该方法可以满分。
```
..##..
.#..#.
..##..
```
### D.电力设备（原题：？）
咕咕咕。
## 2024/11/20
### A.小 C 玩扑克（原题：？）
**题目大意**
有 $n$ 张扑克牌，部分正面朝上，部分反面朝上。翻转第 $i$ 张牌需要花费 $t_i$，且一同将 $[i,r_i]$ 内的牌翻转，求使所有牌正面朝上的最小花费。
$1\le n\le 10^6$。
**分析与做法**
从左到右考虑，若第 $i$ 张牌需要被翻转，那么翻转这张牌肯定是最优的（前面已经全部正面朝上，后面不涉及 $i$），所以直接做就行。时间复杂度 $O(n)$。
### B.小 C 写代码（原题：？）
**题目大意**
给定 $n$ 行长度为 $m$ 的 $01$ 字符串，要求按顺序编写。
- 直接编写：编写一行代码，花费 $c$。
- 复制与修改：选择已写好的某行代码复制，花费 $1$。修改一个位置花费 $1$。
求编写所有代码的最小花费。
$1\le n\le 10^6,1\le m\le 20,1\le c\le 1000$，字符串随机生成。
**分析与做法**
考虑一个字符串 $s_i$（实际上是一个二进制数）如何对后续的编写进行贡献。以它为起点进行宽搜，每次转移就枚举二进制位取反，维护最短距离 $d$（一开始 $d_{s_i}=1$，因为复制要花费 $1$）。那么若编写一个字符串，答案就加上 $\min(d_{s_i},c)$，随后宽搜。注意到状态只有 $2^m$，一次转移花费 $m$，每个状态至多被更新 $m$ 次，所以时间复杂度 $O(n+2^mm^2)$，因为数据随机，所以过得还算轻松。
### C.小 C 求对称（原题：？）
**题目大意**
求有多少种正整数对 $(x,y)$，使得 $x+y=n$，且 $x,y$ 看作字符串时均为回文串。
$1\le n\le 10^{18}$。
**分析与做法**
枚举进位。咕咕咕。
### D.小 C 爱徒步（原题：？）
**题目大意**
时刻 $1$ 位置为 $x$，随后每一个时刻 $x\rightarrow (x+f(x))\bmod m$，求时刻 $n$ 的位置。
$1\le x < m,1\le n,m\le 10^{18}$。
**分析与做法**
咕咕咕。
## 2024/11/21
### A.硬币（原题：？）
**题目大意**
给定 $n$ 种面值不同的硬币，第 $i$ 种硬币面值为 $a_i$，且 $\forall 1\le i<j\le n,a_i\mid a_j$。不同面值的硬币只有颜色不同。可以询问一个 $X$，会返回用最少的硬币凑出 $X$ 的结果，求确定每种面值对应的颜色的最少询问次数。
$1\le n\le 60$。
**分析与做法**
显然答案很小，所以直接枚举能否在 $m$ 次查询内解决问题。$a_n$ 是容易被区分的，所以考虑 $b_i=\frac{a_{i+1}}{a_i}$。每次询问相当于给要区分的面值 $i$ 分配 $[0,b_i)$ 之间的数，如果 $i,j$ 在某次询问中被分配的不一样则可以区分。考虑将 $b_i$ 排序。对于 $b_i\le x$，若 $i\ge x^m$，则不能在 $m$ 次询问中完成。这样的构造并不是一次询问就区分出部分面值，而是将相同权值的面值划分一下，类似递归处理，时间复杂度 $O(n^2)$。二分 $m$ 可以做到 $O(n\log^2 n)$（快速幂）。
### B.狼群（原题：？）
**题目大意**
网格上有 $n$ 只狼，第 $i$ 只坐标 $(x_i,y_i)$，每一步可以移动到相邻四节点之一。求 $m$ 步所有狼均移动到同一个节点的移动路径方案数，对 $10^9+7$ 取模。两种方案不同当且仅当某一步某只狼的移动方向不同。
$1\le n\le 50,1\le m,|x_i|,|y_i|\le 10^5$。
**分析与做法**
套路地，考虑将两个维度分开处理，所以旋转坐标系使 $(x,y)\rightarrow (x-y,x+y)$，那么每一步就变成了 $(x\pm1,y\pm 1)$，于是移动就可以分开考虑了。现在对于终点 $(X,Y)$，从 $(0,0)$ 开始移动，那么假设有 $i$ 步是 $+1$，$m-i$ 步 $-1$，那么有 $i-(m-i)=X$，化简得 $i=\frac{X+m}{2}$，所以方案数为 $\binom{m}{\frac{X+m}{2}}$，$y$ 轴同理。那么答案就是 $\binom{m}{\frac{X+m}{2}}\binom{m}{\frac{Y+m}{2}}$。推广一下，从 $(x_i,y_i)$ 走到 $(X,Y)$ 的方案数就是 $\binom{m}{\frac{X-x_i+m}{2}}\binom{m}{\frac{Y-y_i+m}{2}}$。于是最终答案为：
$$
\sum_{X}\sum_{Y}\prod_{i=1}^{n}{\binom{m}{\frac{X-x_i+m}{2}}\binom{m}{\frac{Y-y_i+m}{2}}}
$$
维度分开处理，将其中一个乘式提前：
$$
\Bigg( \sum_{X}\prod_{i=1}^n{\binom{m}{\frac{X-x_i+m}{2}}} \Bigg)\Bigg( \sum_{Y} \prod_{i=1}^n{\binom{m}{\frac{Y-y_i+m}{2}}}\Bigg)
$$
那么这题就做完了，注意 $X,Y$ 的枚举范围和无解的判定。时间复杂度 $O(nk)$，其中 $k$ 为枚举坐标范围的大小，一般 $k\le 2\times10^5$。
### C.比赛（原题：[TENIS](https://www.luogu.com.cn/problem/P11340)）
### D.半完全幂（原题：？）
**题目大意**
求有多少个 $n\in[L,R]$，且 $n$ 形如 $ab^c,a\ge 1,b>1,c>1,a<b$。
$1\le L,R\le 8\times10^{16}$。
## 2024/11/22
### A.异或函数（原题：？）
**题目大意**
对于给定参数 $a,b$，定义 $f(x)=(x\bigoplus a)-b$。给定 $n$ 个变量 $x_i$ 和 $q$ 组询问，对于每组询问给定 $a,b$，求一个 $i$ 满足 $i\in [1,n),f(x_i)f(x_{i+1})\le 0$，若无解输出 $-1$。
$1\le n,q\le 10^5,0\le x_i,a_i,b_i\le 10^9$。时限充裕。
**分析与做法**
对于 $f(x_i)f(x_{i+1})\le 0$，若存在 $f(x_i)=0$，则 $x_i=a\bigoplus b$。若存在 $l,r$ 使得 $f(l)f(r)\le 0$，则存在 $i\in[l,r)$ 满足条件。贪心地，找到 $x_i\bigoplus a$ 最大的和最小的位置记为 $l,r$，如果 $f(l)f(r)>0$ 则无解，否则可以在 $[l,r]$ 上二分，判断 $f(l)f(mid),f(mid)f(r)$ 是否小于等于 $0$ 并更新。以上，找是否存在 $x_i=a\bigoplus b$ 以及最大最小的 $x\bigoplus a$ 均可以使用 Trie 树解决。时间复杂度 $O(q(\log n+\log V))$，其中 $\log n$ 是二分，$\log V$ 是 Trie 树的深度。
### B.联通块（原题：？）
**题目大意**
给定 $n$ 个点的树和定值 $k$，有点权 $a_i$。选出尽可能多的无交集联通块，使得每个联通块点权和均为 $k$。求最多可以选择多少个。
$1\le n,k\le 10^6,0\le a_i\le 2$。
**分析与做法**
考虑一个点权和为 $m$ 的联通块，它总是可以删除一些点得到点权和为 $m-2$ 的联通块（易证）。那么我们只关心一棵子树内不同奇偶性得到的最大权值，且如果选择 $a_u$，那么其子树只能贡献一次（子树内不涉及 $u$ 的贡献已经算入了，涉及 $u$ 的最多只能贡献 $1$），这为我们贪心奠定基础。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树点权和为偶数/奇数时得到的最大点权和，易得转移：$f_{u,0}=\max_{v}\{f_{v,0}+f_{u,0},f_{u,1}+f_{v,1}\}$，$f_{u,1}$ 同理。当 $f_{u,k\;\bmod\;2}\ge k$ 时答案加一，同时将其复制为负无穷。注意初始数组因当为负无穷。时间复杂度 $O(n)$。
### C.商店（原题：？）
咕咕咕。
### D.编辑距离（原题：？）
咕咕咕。
## 2024/11/23
### A.加减乘除（原题：？）
**题目大意**
给定长为 $n$ 的整数序列 $a$，有 $Q$ 次操作，每次操作形如：
- 对于所有 $a_i\ge x$，$a_i\leftarrow t(a_i+s)$。
- 对于所有 $a_i\le x$，$a_i\leftarrow \mathrm{trunc}(\frac{a_i-s}{t})$，其中 $\mathrm{trunc}(x)$ 表示取 $x$ 的整数部分。
求操作 $Q$ 次后，有多少 $i\in[1,n]$ 满足 $a_i\in[L,R]$。
$1\le n,Q\le 2\times10^5,-2^{63}<L\le R<2^{63},0\le |a_i|\le 10^9$，运算中的所有数的绝对值不会超过 $2^{63}$。
**题目大意**
注意到将 $a$ 排序后，无论怎么操作其相对大小关系是不变的。考虑分别对 $L,R$ 二分一个 $P_L,P_R$，那么最终答案就是 $P_R-P_L+1$。特殊的，需要特判不存在满足条件的元素的情况。具体 check，离线所有操作，考虑二分的 $m$，对 $a_m$ 进行所有操作，判断其结果是否在 $[L,R]$ 内即可。时间复杂度 $O(Q\log n)$。
### B.图书管理（原题：？）
题面相当繁琐，阅读难度高，分析难度低，所以给形式化题意。
**题目大意**
给定 $n$ 的一个排列 $p$，求：
$$
\sum_{1\le l,r \le n,(r-l+1)\bmod 2=1}{f_{l,r}\times l\times r}
$$
其中 $f_{l,r}$ 表示 $i\in[l,r]$，$p_i$ 的中位数。
$1\le n\le 10^4$。
**分析与做法**
考虑拆贡献，假设 $p_i$ 是中位数，那么套路地，将大于 $p_i$ 的视为 $1$，小于 $p_i$ 的视为 $-1$ 做一遍前缀和（正负分开），那么对于合法区间 $[l,r]$，需要满足 $C_r-C_{l-1}=0$。那么开个桶加一下前缀和的下标，枚举 $r\ge i$，答案为 $B_{C_r}\times r\times p_i$。时间复杂度 $O(n^2)$，因为常数极小所以得以通过。
### C.？
### D.？
## 2024/11/26
### A.多项式（原题：[Polynomial division](https://www.luogu.com.cn/problem/AT_abc245_d)）
**题目大意**
对于多项式 $F(x)=\sum_{i=0}^{N-1}{a_ix^i},G(x)=\sum_{i=0}^{M-1}{b_ix^i},H(x)=F(x)\times G(x)=\sum_{i=0}^{K-1}{c_ix^i}$。给定了 $G(x),H(x)$，求 $F(x)$，以系数方式输出。
$1\le M,K\le 2000,0\le b_i\le 10^3,0\le c_i\le 10^6$，$a_{N-1}\not=0,b_{M-1}\not=0,c_{K-1}\not=0$。
**分析与做法**
显然是模拟整式大除法，时间复杂度 $O(MK)$。
### B.撑杆跳（原题：[Fox And Jumping](www.luogu.com.cn\problem\CF510D)）
**题目大意**
去原题看。
**分析与做法**
转化题意：以最少的代价选出若干个数使得它们的最大公因数为 $1$。这样转化的原因是发现选出来的数可以通过有限次减法运算得到 $1$，这刚好符合辗转相除的过程。因为 $a_i\le 10^9$，感性认识到不同的质数个数是 $n\log V$ 级别的，所以做一个 $01$ 背包即可。特殊的，因为值域较大，且没有顺序要求，所以使用 `unordered_map` 进行背包。时间复杂度 $O(n^2\log V)$ 加上巨大常数。因为可用的质数的数量更少，所以状压可以做到 $O(2^9n^2)$。
### C.记录数列（原题：？）
**题目大意**
对于一个 $1\sim n$ 的排列 $P$，可以映射到长度为 $n$ 的序列 $a$ 上，其中 $a_i$ 表示包含下标 $i$ 的，由连续且单调的元素构成的区间的最大长度。现在给定序列 $a$，求有多少种 $P$ 可以映射到 $a$ 上。对 $998244353$ 取模。
$1\le n\le 2000,1\le a_i\le n$。
**分析与做法**
观察有，对于第一个 $a_i=j$，那么 $[i,i+j-1]$ 就是最大的区间，所以 $a$ 可以被划分为若干个块，记为 $b_1,b_2,\dots,b_m$。那么不合法的排列就只有可能是能够合并两个相邻块的情况。于是考虑容斥，设 $f_{i,j,0/1}$ 表示考虑 $i$ 个块，存在 $j$ 个可合并区间，当前区间是上升/下降的方案数（有点像连续段 DP）。则：
$$
f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j-1,0}\\
f_{i,j,1}=f_{i-1,j,1}+f_{i-1,j,0}+f_{i-1,j-1,1}
$$
那么有 $s_i=f_{n,i,0/1}\times(m-i)!$，考虑组合意义可得。答案为 $\sum_{i=0}^{m}(-1)^is_i$。时间复杂度 $O(n^2)$。
### D.变色龙（原题：？）
**题目大意**
给定一个空字符串和 $Q$ 次操作，每次操作是以下其一：
- 在字符串后插入一个小写字母。
- 给定参数 $k$，查询字符串中有多少个子串和字符串的前 $k$ 个字符相同。
强制在线。$1\le Q\le 10^6$。
**分析与做法**
参考 KMP 算法，每加入一个字符对它求出 $nxt$，然后跳 $nxt$ 计数 $sum$，那么对于查询的 $k$，$sum_k+1$ 就是答案。该做法可以被卡到 $O(Q^2)$，然而随机数据下表现优秀，可以在模拟赛做到 100pts。正解涉及 border 和树链剖分的思想，不会，略了。
## 2024/11/27
### A.迷宫（原题：？）
**题目大意**
给定 $n\times m$ 的平凡地图（空地，障碍物，起点，终点），可以花费 $1$ 移动到相邻空地上，也可以花费 $t$ 移动到曼哈顿距离不超过 $k$ 的任意空地，求起点到终点的最小花费。
$1\le n\le m\le 2000,1\le k\le 8$。
**分析与做法**
显然是宽搜，因为边权有两种，所以结合一下最短路维护优先队列的过程，将两种松弛分开存储，易得两个队列花费递增，所以每次取较小的那个队头继续更新就行了。时间复杂度 $O(nmk^2)$。
### B.玩具（原题：？）
**题目大意**
给定长为 $n$ 的木板，有若干位置破损。一只身长 $a$，$b$ 只脚的虫，每只脚占一个单位长度，可以移动到身下的任意完好位置上，每次花费 $1$。身体每次可以移动一个单位，不受木板状态的限制，每次花费 $1$。任意时刻脚都要在身下，求虫从最左边移动到最右边的最小花费。
$1\le b\le a\le n\le 3\times10^6$。
**分析与做法**
题目大意就这么着吧无所谓了。显然每次将脚先移动到最前面，然后挪动身体最优。木板状态前缀和一下然后双指针（一个记录头部，一个记录最后一只脚的位置）过就行了。时间复杂度 $O(n)$。
### C.权重（原题：？）
**题目大意**
给定 $n$ 个点的树，有点权 $a_i$。任意两点的权值 $D(u,v)$ 为两点简单路径上点权的异或值，每个点 $u$ 随机选择一个点 $v$，其贡献 $w_u=D(u,v)$ 。记 $x=\max\{w_u\}$，求 $x\ge t$ 的概率。
$1\le n\le 3\times10^5,0\le a_i,t< 2^{32}$。
**分析与做法**
假设对于点 $u$，有 $c_u$ 个点使得其贡献小于 $t$，那么最终概率为 $1-\prod_{u}\frac{c_u}{n}$。
记根节点到节点 $u$ 的路径权值为 $d_u$，而 $D(u,v)=d_u\bigoplus d_v \bigoplus d_{lca(u,v)}$，所以在 LCA 处统计答案。启发式建一下 Trie 树然后计数就行了。时间复杂度 $O(n\log n\log V)$。
### D.周长（原题：[すぬけ君の塗り絵 2](https://www.luogu.com.cn/problem/AT_arc063_d)）
**题目大意**
略。
**分析与做法**
不会。
## 2024/11/28
### A.Sum（原题：[跑步](https://www.luogu.com.cn/problem/P6189)/[双倍经验·弱化](https://www.luogu.com.cn/problem/P10955)）
**题目大意**
求将 $n$ 拆分成若干正整数之和的方案数。$1\le n\le 10^5$。
**分析与做法**
假设和为 $i$，那么当 $i\le \sqrt{n}$ 时，发现只有 $\sqrt{n}$ 个数，可以使用完全背包解决（虽然卡卡常开个 O3 就过了，虽然小优化可以做到 $O(n(n+1))$ 但是只有 $\frac{1}{4}$ 常数），记为 $f_i$。当 $i>\sqrt{n}$ 时，考虑另一种转移 $g_{i,j}=g_{i-1,j-1}+g_{i-j,j}$ 发现这样根号分治一下之后两个转移的时空复杂度都是 $O(n\sqrt{n})$，最后枚举一下两种乘起来就行了。
### B.City（原题：[Shortest Path on a Line](https://www.luogu.com.cn/problem/AT_nikkei2019_2_qual_d)）
题意请去原题。
[题解：Shortest Path on a Line](https://www.luogu.com.cn/article/d17cn2gz)
### C.种萝卜（原题：[Flags](https://www.luogu.com.cn/problem/AT_arc069_d)/[Now or later](https://www.luogu.com.cn/problem/UVA1146)）
**题目大意**
去原题看。
**分析与做法**
考虑二分答案 $m$，接下来注意到对于点 $i$，如果选择 $x_i$，那么排序后会有一段区间不能选，显然是一个 2-sat 问题。将 $x_i,y_i$ 拆开之后发现直接对区间暴力建边会超时，于是用线段树优化建边即可。时间复杂度 $O(n\log n\log V)$。
对于线段树优化建边，根向儿子连有向边，叶子结点向真实节点连有向边。比前后缀优化建边易懂。
### D.游戏（原题：？）
**题目大意**
先手 A，后手 B，树上行棋。每一步棋移动的距离都要大于上一步，不可停留，不能移动的人输，第一步移动的距离随意。求对于每一个点为起点，先手是否能获胜。
**分析与做法**
结论题。
- 若起点为直径的中点，那么不能获胜。
- 可以证明其它情况可以获胜，因为第一步可以走到中点上，后手走完之后先手可以走到该点关于直径中点的对称点。
时间复杂度 $O(n)$。