ARC114

3.13开的一场vp。
拉的不行，只做出了前 2 道。

题意: 找最小的一个数和数组 $X$ 中的每个数都不互质。
做法：由于 $X_i$ 很小，只有 $15$ 个质因数，直接枚举所有情况即可，时间复杂度 $O(n2^{15})$。

赛时wa了两发。

第一发以为直接枚举即可，但是发现了15个质因数的和可能很大。

第二发最小值初始值设小了。

题意: 给出数组 $f(n\leq 2 \times 10^5，1\leq f_i \leq n)$ , 选出一些数，满足以下条件：
1. 如果 $i$ 被选，那么 $f_i$ 就得被选。
2. 如果 $a \neq b$, 且 $a, b$ 被选，那么 $f_a \neq f_b$。
求方案数。
做法：第一个条件实际上就是一个依赖关系，会选出一个环可能带一条链，第二个条件表明一个每个点的入度为 1，这样的东西只能是环了。
做法就很显然了，拓扑排序找出所有的环，记个数为 $c$, 答案即是 $2^c - 1$。

赛时wa了一发，原因是数组没开大。

题意: 只给出序列长度 $n (\leq 5000)$, 每个数的范围 $1\sim m(\leq 5000)$。
初始有全零的序列，每次操作可以任选一段区间 chkmax 一个任选的数，
记 $f(S)$ 表示，变成这个序列 $S$ 的最小操作次数，求 $m^n$ 种序列的 $f(S)$ 的和。
做法：考虑新加入一个数 $S_i$ 造成的 $f(S)$ 的变化。
1. 如果前面有数 $S_j = S_i$, 并且 $j + 1 \sim i - 1$ 这段的 $S$ 都 $\geq S_i$, 那么可以在 $j$ 操作的时候顺带把这位chkmax，这样就没有变化了，否则变化 1。
2. 如果没有出现过，那么就会变化 1.
现在只需要考虑如何计算总变化，求补集即可。那么枚举当前的数 $x$，在枚举相同出现的位置：
$$\Delta_{x} = m^{i - 1} - \sum_{j = 0}^{i - 1}(m - x)^{i - j - 1} m^{j - 2}$$
求答案时,
$$\text{ans}_i = \sum _{x=1}^m \text{ans} _{i - 1} + \Delta _{x}$$
赛时一直想怎么dp，就做不出来了。

题意: 给出一些点 $a (|a_i| \leq 10^9, n\leq 5000， n \equiv 0 \pmod 2)$, 和一些区间 $b$。
初始时，数轴上的边都是红色，你可以对点 $a$ 左右移，边被经过一次，代价为 1，就会将颜色翻转，红变蓝或蓝变红。
求最小代价，使得每个区间都是蓝色。
做法：观察到，点$a$ 只往一个方向移动，回头肯定不优。
区间问题不好做，考虑差分变成单点问题，这就发现颜色翻转和异或有关，这样就会变成异或差分。
问题转化为，刚开始对 $n$ 个点和区间两端异或 $1$, 有 $n$ 个剩余的 $1$ 可以随意异或，代价是和起点的距离，要求最后是全0。
考虑无解的情况，当 $n$ 个点比初始 $1$ 的个数少时，那就一定不能使得最后全为 0。
剩下就是匹配问题，当点数相同时，显然贪心距离最小的优先匹配。
但是 $n$ 个点比初始 $1$ 的个数多时，$n$ 个点内部还要自己匹配，相邻两点匹配也是最优的。
于是设 $f_{i, j}$ 表示可以用 $i$ 个 1匹配，剩下 $j$ 个要消去。
转移可以从 $f_{i - 1, j - 1}$ 和 $f_{i - 2, j}$ 来。

题意：给出一个 $W \times H (W, K \leq 10^5)$ 的矩阵，有 $H - 1$ 条可以切开的竖线和 $W - 1$ 条可以切开的横线，
如果切到给定的一个子矩阵 $(w1, h1), (w2, h2)$就停止，否则将选择有给定子矩阵的那一块，求期望切的次数。
做法：由于期望有线性性，考虑拆开每条线的对总期望的贡献。
由于四个方向的线相互独立，可以拆开。
以子矩阵右边的竖线为例，它能贡献一次的情况是
1. 子矩阵没被切到，有 $k = w2 - w1 + h2 - h1$ 条。
2. 竖线到子矩阵的竖线条数，有 $c$ 条。
能贡献一次的概率当且仅当在 $k + c$ 条线中第一次被切到，于是期望次数就是 $\frac{1}{k + c}$。
对每一条线的期望求和就是答案。

题意：给出 $n(\leq 2 \times 10^5)$ 个数的排列 $P$, 要把排列分成 $k$ 个连续段，要使这 $k$ 个段重排后的 $Q$ 的最大字典序最小，并求出这个字典序 $Q$。
做法：注意到，$Q$ 的字典序总是大于等于 $P$。
又注意到，开头的 $P_1$ 一定是某一段的开头。
显然使得段重排的字典序最大，就要按段开头的数字的字典序排序。
就考虑 $P_1$ 和 $k$ 的关系。
1. 如果 $P_1 \leq k$, 那么每段开头一定是 $1 \sim k$, 重排就是最小的字典序了。
2. 如果 $P_1 \geq k$, 这时是挑 $1 \sim k - 1$为开头吗？不一定是最小。
求字典序最小，就来点强的约束条件，求出 $Q$ 与 $P$ 的最长公共前缀。
用二分就可以判定了, 记长度为 $l$。
为了使前前缀的不变，那么就一定要选出一个包含 $P_1$ 的 $1\sim l$ 的下降子序列，子序列长度就是拆分的段数。
又要剩下的数分成段不排到前面，就要满足拆分的段的开头 $< P_l$，为了存在合法的情况，就要使得子序列的长度尽可能长，就越容易找出合法的序列。
记 $1\sim l$的最长下降子序列的长度是 $a$, 那么只要选剩下 $1\sim k - a$ 小的开头重排就是最小的 $Q$。

DP 差分异或拆贡献 AtCoder 贪心计数概率期望字符串

相关