mx
vanueber
·
·
个人记录
mx1
赛：85 + 24 + 40 + 0
补：100 + 100 + 100 + 24
总结：10^6 不能双 \log，注意题目没写在数据范围里的部分分。
P110120 宇宙（universe）
观察到随着 $k$ 增加，$ans$ 和要维护的下标 $p$ 都是单调递增的，先推一下式子，看一下 $ans$ 应满足什么条件。
$$
\begin{cases}
& ans + 1 > a_p\\
& (x+1)\times p - s_p \le k\times x + s_p
\end{cases}
$$
$$
\begin{cases}
& ans + 1 > a_p\\
& x \le \frac{s_p-p}{p-k}
\end{cases}
$$
先排序，求出前缀和 $s_i$，保证 $p>k$ 后就可以双指针求出 $p,x$。
[code](https://www.mxoj.net/submission/detail?answerId=174490)
## [P110121 跳跃（jump）](https://www.mxoj.net/problem/P110121?trainingNumber=T1141)
- 先做第一关键字。
- 题目的关键性质：询问保证了端点都是白色，代表极长的黑色区间要么不包含，要么完全包含。
- 如果有性质 $C$，这代表可以不踩任何一个黑格子。
- 如果没有，一段长度为 $len$ 的黑色区间，其中有 $\lfloor \frac{len}{k} \rfloor$ 是必须踩的，直接缩成 $len \bmod k$ 的区间。
- 再考虑第二关键字。
- 如果一个点直接跳到了白色，直接不管。
- 否则看一下他在黑色区间的相对位置，如果他跳出去了就不管，否则让他跳回最后的白色的位置。
但这样还是太吃操作了，直接缩黑色区间，只保留 $len \bmod k$，这样直接跑特殊性质 $C$，然后累加一下黑色区间的贡献即可。
[code1](https://www.mxoj.net/submission/detail?answerId=283493)
[code2](https://www.mxoj.net/submission/detail?answerId=297141)
## [P110122 圆环（circle）](https://www.mxoj.net/problem/P110122?trainingNumber=T1141)
[前置题目](https://atcoder.jp/contests/arc073/tasks/arc073_d)
这道题中 $f_{i,j}$ 表示考虑前 $i$ 个要求后，一个在 $x_i$ 另一个在 $j$ 的最小操作数。
$$
f_{i,j} \gets \min f_{i-1,j}+|x_i-x_{i-1}|
\\
f_{i,x_{i-1}} \gets \min f_{i-1,j}+|x_i-j|
$$
把第二个转移拆了：
$$
f_{i,x_{i-1}} = \begin{cases}
\min f_{i-1,j} + x_i - j,j\le x_i\\
\min f_{i-1,j} + j - x_i,j \ge x_i
\end{cases}
$$
发现第一个转移要维护区间加，第二个转移维护 $f_{i-1,j}+x_i$ 和 $f_{i-1,j}-x_i$ 的最小值，直接上线段树即可。
回到本题。
如果只有一个约束，有转移方程：
$$
f_{i,j} \gets f_{i-1,j}+\min(|now-lst|,n-|now|)
\\
f_{i,now} \gets \min f_{i-1,j} + \min(|j-lst|,n- |j-lst|)
$$
相比上面只是多了一项。
然后考虑一个时刻要满足两个条件怎么做。
这个时候末状态是定的，$f$ 数组只有一个有值。
只需钦定一个顺序，第二次转移时在不进行转移一即可。
[code](https://www.mxoj.net/submission/detail?answerId=290961)
# mx2
赛：50 + 100 + 36 + 16
补：100 + 100 + 100 +100
总结：对拍，不要相信大样例。
## [P110124 Mex](https://www.mxoj.net/problem/P110124?trainingNumber=T1151)
$\operatorname{mex}$ 是 $\Theta(n)$ 级别的。
一个数能成为 $\operatorname{mex}$ 说明 $a$ 中 $a_i = \operatorname{mex}$ 的位置对应的 $b_i \not =\operatorname{mex}$，第一问枚举即可。
第二问如果 $a_i \not =\operatorname{mex}\lor b_i \not =\operatorname{mex}$ 说明这个位置随便换。
[code](https://www.mxoj.net/submission/detail?answerId=178808)
## [P110125 独立集](https://www.mxoj.net/problem/P110125?trainingNumber=T1151)
很好的树形 dp。
令 $K = 0\sim n-1$ 分别 dp。
对于每个点 $u$ 选不选设计状态。
$g_u$ 表示不选 $u$ 时子树选择的总方案数。
$f_{u,s}$ 表示 $u$ 选了 $s$ 个邻居的方案数，同时用 $s_{u,k}$ 记一下前缀和。
$g_u$ 相当于子树可以随便选。
$$
g_u = \prod (g_v + s_{v,K})
$$
$f_{u,k}$ 的转移则考虑加入一个元素 $v$。
$$
f'_{u,k} = f_{u,k} \times g_v + f_{u,k-1}\times s_{v,K-1}
$$
时间复杂度 $\Theta(n^3)$。
[code](https://www.mxoj.net/submission/detail?answerId=299520)
## [P110126 删点](https://www.mxoj.net/problem/P110126?trainingNumber=T1151)
神秘性质题。
- 一定不会删的点：$a_1,a_n,\min a_i,\max a_i$。
- 取最左侧的极值到最右侧的极值，选这个矩形，中间的点都会被删掉。
- 然后可能留下的点：一段前缀中 $a_i = a_1$，一段后缀中 $a_i = a_n$。
- 观察到对于每一种可能得删法都可以转化为不相交矩形的删除。
然后 dp，只讨论前缀的情况。
$f_{i,j}$ 表示考虑前 $i$ 个点，是否能留下 $j$ 个。
$$
f_{i,j} = f_{i-1,j-1}
\\
f_{i,j} = f_{k,j}
$$
再使用 `bitset` 优化即可做到 $\Theta(\frac{n^3}{\omega})$。
[code](https://www.mxoj.net/submission/detail?answerId=187572)
# mx3
赛：95 + 0 + 100 + 0
补：100 + 100 + 100 + 0
总结：梦熊大粪评测规则，最后一定要再交一次代码。
## [P110128 委托 (entrust)](https://www.mxoj.net/problem/P110128?trainingNumber=T1155)
贪心，对于一个任务肯定做完之后尽快回到 $0$，排序后二分做最大不相交子区间即可，注意可以落单一个。
[code](https://www.mxoj.net/submission/detail?answerId=191668)
## [P110129 骑车环行 (cycle)](https://www.mxoj.net/problem/P110129?trainingNumber=T1155)
先建出最小生成树，加入一条边后生成一个环，环的代价更新为边权的最大值，答案是最大值的最小值。
树剖线段树维护。
# mx4
赛：100 + 50 + 0 + 0
补：100 + 100 + 100 +100
总结：T3 可以比 T2 简单。
## [P110132 异或子段](https://www.mxoj.net/problem/P110132?trainingNumber=T1158)
神秘诈骗题。
先套路地钦定一个最大值 $x$，然后要考虑的就是跨过 $x$ 且长度为 $x$ 的区间，显然过不了。
剪枝，单调栈预处理左边第一个 $l_i,a_{l_i} \le a_i$，右边第一个 $r_i,a_{r_i}>a_i$，再花 $\Theta(\min(i-l_i,r_i-i))$ 的代价检查答案。
这样复杂度神奇地变成了 $\Theta(n\log n)$。
::::info[证明]
全局最大值先选出来，会暴力统计一个长度为 $n$ 的区间。
像建立笛卡尔树一样得到其余两个子区间的最大值，会产生 $\frac{n}{2}$ 的贡献。
这样总贡献类似归并排序，是 $\Theta(n\log n)$。
::::
[code](https://www.mxoj.net/submission/detail?answerId=198154)
## [P110133 氧气堆](https://www.mxoj.net/problem/P110133?trainingNumber=T1158)
- 观察到值域很小，可以考虑值域上的做法。
- 对每一个值维护一个链表，同时用指针 $p$ 表示当前扫到的最小值。
- 但是这可能会被操作二破坏 $p$ 的最小性。
- 考虑额外维护一个 $min$，由于操作二会弹出最小值，所以 $min \le p$ 最多只有一个。
- 时间复杂度 $\Theta(n+V)$。
坑点：若当前的 $p=x$，影响最晚的是当前插入的 $x$。
[code](https://www.mxoj.net/submission/detail?answerId=214284)
## [P110134 Toptrees 领先](https://www.mxoj.net/problem/P110134?trainingNumber=T1158)
- 没有简单环的无向图是森林。
- 预处理森林里每棵树的信息，一条边合法的条件是：不使用当前树的 $size$，能否凑出一个定值 $k$。
- 一种方法是预处理前缀背包和后缀背包，用 `bitset` 优化，时间复杂度 $\Theta(\frac{nm}{\omega})$，[code](https://www.mxoj.net/submission/detail?answerId=233736&returnUrl=/submission/answer?number=P110134)。
- 新知识：转为计数，$f_i$ 表示凑成 $i$ 的方案数，转移方程 $f_i = f_{i} + f_{i-x}$，发现这个转移方程是可撤销的。
::::info[tips]
`bitset` 相关技巧：可以将 `bitset` 看作一个数组，`<<` 相当于往右平移，`>>` 相当于往左平移。
也可以看成一个数，只是从左到右表示高位到低位。
::::
# mx5
赛：未知
补：100 + 100 + 12 + 0
总结：冲不出正解要打暴力分。
## [P130006 阿蛮](https://www.mxoj.net/problem/P130006?trainingNumber=T1164)
组合意义题。
考虑一个局面 $(x,y)$，当前一共有 $x$ 个人，第一个人及其支持者有 $x-y$ 个，它的贡献为 $\max(0,x-2y)$。
考虑一个局面出现的概率，总方案是 $1\sim x$ 的排列，其中 $1\sim n$ 保持顺序，即 $\binom{x-1}{n-1} \times (x-n)!$。
然后计算 $2$ 后面有 $y-1$ 个人的方案数，首先对 $x-n$ 个人随便排，再从 $n-2$ 个人选 $y-1$ 个固定，即 $\binom{y-1}{n-2}\times(x-n)!$。
于是局面 $(x,y)$ 出现的概率是 $\frac{\binom{y-1}{n-2}}{\binom{x-1}{n-1}}$。
所以答案是
$$
\sum_{x=n+1}^{m} \sum_{y=1}^{x} f_{x,y} \times \max(0,x-2y) = \sum_{x=n+1}^{m} \frac{1}{\binom{x-1}{n-1}} \sum_{y=1}^{\lfloor \frac{x}{2} \rfloor} (x-2y) \times \binom{y-2}{n-1}
$$
固定 $x$，使用前缀和预处理即可。
[code](https://www.mxoj.net/submission/detail?answerId=345794)
## [P130007 菟园](https://www.mxoj.net/problem/P130007?trainingNumber=T1164)
先跑 `kmp`，建立失配树，问题转化为动态加叶子节点，动态询问子树权值，路径加。
分块，可以处理出 $x$ 跳出块第一个跳到谁。
然后权值可以懒标记， $add_i$ 表示跳出去之前的祖先上都需要权值 $+1$。
[code](https://www.mxoj.net/submission/detail?answerId=233720)
# mx6
赛：100 + 0 + 6 + 4
补：100 + 100 + 100 + 20
总结：调试最后一定要注释掉。
## [P130011 句法分析](https://www.mxoj.net/problem/P130011?trainingNumber=T1351)
区间 dp 即可，签到。
## [ P130012 树上前 k 大菊花](https://www.mxoj.net/problem/P130012?trainingNumber=T1351)
妙妙题，肯定是多路归并优先队列。
先考虑大菊花怎么做，把邻居降序排序，然后钦定只选 $k$ 个，压入最优方案。
扩展是考虑如何得到次优解，肯定是有一个指针往后移动一格导致。
很智慧的一点：当前选择是往后移当前指针，或固定当前指针，后面的指针都不能超过他。
这样只扩展出 $\Theta(1)$ 个状态。
很多菊花时再用一个堆维护所有堆顶即可。
[code](https://www.mxoj.net/submission/detail?answerId=233114)
## [P130013 相关聚类](https://www.mxoj.net/problem/P130013?trainingNumber=T1351)
观察 $1$：如果是一棵树，从 $k = n\sim 1$ 考虑，初始时贡献为 $+$ 的数量，$k$ 减小 $1$，如果有 $+$ 代价就减少 $1$，否则代价增加 $1$。
观察 $2$：基环树不同点在于合并了 $len-1$ 个点后就相当于连通了，代价会强制被剩下的边改变。如果环上都是 $+$ 则没有影响，有多个 $-$ 也没有影响，因为这个时候 $+$ 已经选完了。所以只有 $\operatorname{cnt}(-) = 1$ 需要特殊考虑。
当 $\operatorname{cnt}(-) = 1$ 时的合并顺序：树上的 $+$，环上的 $+$，树上的 $-$。
当 $\operatorname{cnt}(-) \not= 1$ 的时合并顺序：环上的 $+$，树上的 $+$，树上的 $-$，环上的 $-$。
[code](https://www.mxoj.net/submission/detail?answerId=321083)
# mx7
赛：100 + 0 + 20 + 0
补：100 + 100 + 20 + 0
总结：构造题太难了。
## [P130019 地球往事](https://www.mxoj.net/problem/P130019?trainingNumber=T1411)
$a_i \gets a_i - i,b_i \gets b_i - i$ 然后按照 $a$ 递增，$b$ 递减的顺序排序，相当于不严格的逆序对之间会连边，求最后连通块的数量。
[原题](https://codeforces.com/problemset/problem/1638/C)，相同的套路，`set` 维护每一个连通块最大的 $b$，加入一个新的就合并。
每个点只会被加入一次删除一次，时间复杂度 $\Theta(n\log n)$。
可以用单调栈把最后的过程变成 $\Theta(n)$。
## [P130020 纪元](https://www.mxoj.net/problem/P130020?trainingNumber=T1411)
- 一个字符串对前一个字符串有约束。
- 具体地，设 $s_i$ 字符集为 $\Sigma$，对于其中任意一个字符，都要求
# mx8
VP：反正做出一道题。
补：100 + 100 + 5 + 0
总结：dp 太难了。
## [P130015 项链 (necklace)](https://www.mxoj.net/problem/P130015?trainingNumber=T1419)
### sol1
二分答案，分成 $<k$ 的和 $\ge k$ 的，$<k$ 的一定要选，两个 $<k$ 之间最多夹一个 $\ge k$，线性检查即可。
### sol2
两两成对的插入堆中，堆头是瓶颈，一定是要被调整的，调整的一对一定会删去较大的，直接拿链表模拟即可。
[code](https://www.mxoj.net/submission/detail?answerId=244737)
## [P130016 计树 (tree)](https://www.mxoj.net/problem/P130016?trainingNumber=T1419)
神秘的插空 dp。
由于题目的限制，钦定一个 $1\sim n$ 的加点顺序。
$f_{i,j,k}$ 表示考虑前 $i$ 个数，形成了 $j$ 棵树，且留有 $k$ 个空位的方案数。
1. 当前节点儿子个数可以取 $0$。
$$
f_{i,j+1,k} \gets f_{i-1,j,k}\\
f_{i,j,k-1} \gets f_{i-1,j,k} \times k
$$
代表为该节点开一棵树，或者把该节点放在一个空位。
2. 当前节点儿子个数可以取 $1$。
$$
f_{i,j+1,k+1} \gets 2\times f_{i-1,j,k}
\\
f_{i,j,k} \gets 2\times f_{i-1,j,k} \times k
$$
这个转移是一样的，只不过要钦定它接的是左儿子还是右儿子。
3. 当前节点儿子个数可以取 $1$。
$$
f_{i,j+1,k+2} \gets f_{i-1,j,k}
\\
f_{i,j,k+1} \gets k\times f_{i-1,j,k}
\\
f_{i,j,k+1} \gets 2\times f_{i-1,j,k}\times j
\\
f_{i,j,k} \gets k \times 2 \times (j-1) \times f_{i-1,j,k}
$$
分别代表：新开一棵树产生两个空位，直接接在一个空位，新开一棵树并接一棵树上去，接在一个空位并在该节点上接一棵树。
[code](https://www.mxoj.net/submission/detail?answerId=310570)
# mx9
赛：100 + 0 + 0 + 0
补：100 + 0 + 0 +0
总结：在补。
# mx10
没打。
补：0 + 100 + 0 + 0
总结：在补。
min-max 容斥。
$$
\max(S) = \sum \min(T)
$$
# mx11
赛：0 + 0 + 0 + 0
补：100 + 0 + 0 +0
总结：文件读写要写对。
# mx12
赛：60 + 40 + 60 + 10
补：100 + 40 + 100 + 10
总结：对拍，根号分治太强了。
## [P130032 距离](https://www.mxoj.net/problem/P130032?trainingNumber=T1639)
floyd 本质是 dp，可以求出 $i,j$ 之间编号不超过 $k$ 的最短路。
考虑分块，$f_{t,i,j}$ 表示不使用编号为 $[l_t,r_t]$ 之间的点，$i,j$ 的最短路。这一部分处理时间是 $\Theta(\frac{n^4}{B})$。
然后对每个 $p$ 求出全源最短路数组。
对于一个 $p$ 在 $t$ 块内，只需要加入 $[l_t,r_t]$ 的其他元素即可，时间复杂度 $\Theta(Bn^3)$。
取 $B=\sqrt n$ 得到最优复杂度 $\Theta(n^{3.5})$。
[code](https://www.mxoj.net/submission/detail?answerId=374376)
# mx13
赛：50 + 20 + 30 + 0
补：100 + 100 + 30 + 0
总结：$\le \not = =$，需要仔细分析性质。
# mx14
赛：100 + 10 + 0 + 25
补：100 + 10 + 0 + 25
总结：在补。
# mx15
赛：40 + 0 + 25 + 0
补：100 + 0 + 25 + 10
总结：在补。
## [P130051 玲珑宝塔](https://www.mxoj.net/problem/P130051?trainingNumber=T1668)
先二分答案，检查可以贪心，开 $mid$ 个位置。每次肯定顺着填下去。
[code](https://www.mxoj.net/problem/P130051?trainingNumber=T1668)
# mx16
赛：100 + 70 + 45 + 0
补：100 + 100 + 45 + 0
总结：在补。
## [P130067 删数游戏](https://www.mxoj.net/problem/P130067?trainingNumber=T1746)
由于单调递增，从最后的数开始删一定是对的。
赛时发现问题转化为求 $a_i \equiv 0\pmod i$ 位置的最大值，同时动态删点，直接打了分块维护。
实际上找到最后满足的位置后直接把之后的加进来就行。
[code](https://www.mxoj.net/submission/detail?answerId=338815)
## [P130068 货币改革](https://www.mxoj.net/problem/P130068?trainingNumber=T1746)
同于最短路，考虑使用 $c_2\sim c_i$ 凑出 $m=c_1$ 的每个剩余系最小价值，那么 $dis_i - m$ 都是不能被表示的。
然后就是加边最短路，但这题有特殊性质，每次只用考虑新加的边即可。
因为松弛过后假设这个点变为 $x_2c_2 + x_3c_3 + \dots+x_{i-1}c_{i-1} + c_i$，那么此时不需要 $c_{2\sim i-1}$ 的边进行松弛，因为最终都可以表示为 $x_ic_i$ 的形式，可以直接由这个点更新。
使用类似归并的方法用双端队列实现迪杰。
[code](https://www.mxoj.net/submission/detail?answerId=345428)
# mx17
赛：100 + 36 + 30 + 10
补：100 + 100 + 30 + 0
总结：在补。
# mx18
赛：100 + 20 + 50 + 20
补：100 + 100 + 100 + 20
总结：在补。
## [P130078 染色（paint）](https://www.mxoj.net/problem/P130078?trainingNumber=T1791)
一个颜色的刷子肯定用来刷 $[l_i,r_i]$，$l_i,r_i$ 代表了该颜色的左右边界。
从 $1$ 开始往后刷 `solve(l,r)` 代表将 $[l,r]$ 染色，递归处理即可。
[code](https://www.mxoj.net/submission/detail?answerId=362230)
## [P130079 交换（swap）](https://www.mxoj.net/problem/P130079?trainingNumber=T1791)
最难做的情况是最小值在右儿子处取到，可以记忆化搜索。
$f_{u,val}$ 表示以 $u$ 为根的子树将 $u$ 改成 $val$，这个值最终变到哪里。
直接记忆化搜索，一个点的取值只能是其祖先或者祖先的兄弟。
# mx19
赛：100 + 0 + 10 + 4
补：100 + 0 + 10 + 4
总结：在补。
# mx20
赛：80 + 30 + 0 + 0
补：100 + 100 + 100 + 0
总结：`vector` 使用要注意效率问题，数组要算空间。
# mx21
赛：100 + 70 + 44 + 10
补：100 + 100 + 100 + 10
总结：数论分块忘记了，本场未挂分。
## [P130109 新站长 (webmaster)](https://www.mxoj.net/problem/P130109?trainingNumber=T1861)
先把所有 `B` 变成 `A`，然后从后往前考虑，能变回来就变，直接贪心。
[code](https://www.mxoj.net/submission/detail?answerId=378282)
## [P130110 小粉兔不想挂科 (failure)](https://www.mxoj.net/problem/P130110?trainingNumber=T1861)
数论分块复习。
---
对于 $i=1\sim n$，$\lfloor \frac{n}{i} \rfloor$ 的值只有 $\Theta(\sqrt n)$ 个。
如果 $i \le \sqrt n$，由于 $i$ 只有 $\Theta(\sqrt n)$ 个，$\lfloor \frac{n}{i} \rfloor$ 的值只有 $\Theta(\sqrt n)$ 个.
如果 $i > \sqrt n$，$\lfloor \frac{n}{i} \rfloor \le \sqrt n$，只有 $\Theta(\sqrt n)$ 个。
所以 $\lfloor \frac{n}{i} \rfloor$ 的值只有 $\Theta(\sqrt n)$ 个。
---
满足 $\lfloor \frac{n}{i} \rfloor = k$ 的 $i$ 的取值范围为 $[\lfloor \frac{n}{k+1} \rfloor +1,\lfloor \frac{n}{k}\rfloor]$。
由不等式 $k \le \frac{n}{i} < k+1$ 推得。
---
回到原题，依次求 $c_i$。
$$
c_i = \sum_{j=1}^{i} a_{\lfloor \frac{i}{j} \rfloor \times b_{i \bmod j}}
$$
数论分块，计算 $\lfloor \frac{i}{j} \rfloor = k$ 的一段。
此时 $a_{\lfloor \frac{i}{j} \rfloor}$ 固定，要算 $b$ 在这一段的和。由于 $i \bmod j = i - \lfloor \frac{i}{j} \rfloor \times j$，所以下标是一个 $i$ 结尾的一段等差数列，公差为 $k$。
由于 $i \bmod j < j = \lfloor \frac{i}{k} \rfloor$，所以只需要预处理以 $i$ 结尾的公差 $k$ 前缀等差数列，而且对于一个 $i$ 最多需要 $\frac{n}{i}$ 个。
调和级数，时间复杂度 $\Theta(n\log n + n\sqrt n)$。
[code](https://www.mxoj.net/submission/detail?answerId=382281)
## [P130111 管理组招新 (recruitment)](https://www.mxoj.net/problem/P130111?trainingNumber=T1861)
神秘带派。
$f_{i,j,k}$ 表示考虑前 $i$ 个人，配好了 $j$ 组，还有 $k$ 组只有组员的答案。
先排序，经验从小到大，而且组员要先被考虑。
直接转移即可。
由于 $k \le \frac{n}{2}$，所以 $k = \Theta(\sqrt n)$，$\Theta(n\log n+ nk^2)$ 可以过。
[code](https://www.mxoj.net/submission/detail?answerId=382137)
# mx22