有些题还没写，不一定保证正确。

ARC148

ARC148C

考虑到求最值，有一个很显然的 dp 做法：考虑结点 (i) 的子树初始时被翻转次数的奇偶性，然后再根据最终要全部和点集相同或不同分讨弄 4 个 dp，转移随便胡一下，然后上虚树就行。

上面那个太难写了，这里有一个比正解更优的做法。不妨令点集中的点为黑色，其余点为白色，则问题转化成将整棵树染成白色。考虑深度最小的黑色点，显然只有操作根到该点路径上的任意一点时才能将其染成白色，贪心地，操作该点最优。考虑循环模拟上述过程。

实际上我们发现取出深度最小的黑色结点时，可以默认该点的所有子结点均为白色。那么对于每个子结点，都需要再进行一次操作以将其变回白色。判掉父子结点均为黑色的情况即为最小操作数。时间复杂度 (O(n))

EDqwq锐评：撅来撅去，父子相撅

ARC147

ARC147C

发现这个式子当所有 (x_i) 趋近于某一个值时答案比较优，于是可以发现这是一个近似单谷函数，用二分 + 随机化/特判过掉就行。

令 (max_{i = 1}^n L_i = M)，(min_{i = 1}^n R_i = m)。

• (M leq m)

  显然 (forall 1 leq i leq n, L_i leq M) 且 (R_i geq m)，于是令 (forall 1 leq i leq n, x_i = m)，答案为 (0)

• (M < m)

  因为 (L_i leq R_i)，所以 (M, m) 必然位于两个不同的下标。假设 (M = L_p, m = R_q)，那么有结论：(forall 1 leq i leq n, x_p leq x_i leq x_q)

  证明：如果存在若干位置，使得 (x_i < x_p) 或 (x_i > x_q)，则因为有 (x_q leq m < M leq x_p)，且 (forall 1 leq i leq n, L_i leq M) 且 (R_i geq m)，只需要令 (x_i < x_q) 的位置为 (x_q)，(x_i > x_p) 的位置为 (x_p) 即可，与题设矛盾。

  于是令 (C = sumlimits_{i eq p, q}^n sumlimits_{j eq p, q}^n |x_i - x_j|)，则答案为：

  (C + |x_p - x_q| + sumlimits_{i eq l, r} |x_i - x_p| + sumlimits_{i eq l, r} |x_i - x_q|)

  发现这个式子可以递归定义，简单手玩可以发现最后的答案为：

  (sumlimits_{i = 0}^{n - 1} |L_i - R_i| imes (n - 2i - 1))

  其中 (L_i) 按降序排列，(R_i) 按升序排列。

  时间复杂度 (O(n log n))

ARC147D

大诈骗，差评。

考虑 设而不求。令 (a_i) 表示 (S_i) 和 (S_{i + 1}) 的公共元素，则长度为 (n - 1) 的 (a) 序列一共有 (m^{n - 1}) 种。

我们发现当 (a) 确定且 (S_1) 确定时，(S_2, ..., S_n) 也随之确定。(S_1) 共有 (2^m) 种。

考虑再设 (A_i) 表示当 (S_1) 包含 (i) 时 (S_1, ..., S_n) 中包含 (i) 的集合总数，同理 (B_i) 为不包含时。考虑选与不选每个数，发现答案为 (prodlimits_{i = 1}^n (A_i + B_i))，而 (forall 1 leq i leq n, A_i + B_i = n)。所以原式为 (n^m)

所以最终答案为 (n^m cdot m^{n - 1})，复杂度 (O(log m + log n))

ARC147E

你会考虑到一些显然的贪心策略，但这些显然都是错的。

题目的要求是最终 (forall 1 leq i leq n, B_i leq A_i)。这个条件和 (forall 1 leq i leq 10^9, sumlimits_{j = 1}^n [b_j leq i] - sumlimits_{j = 1}^n [a_j leq i] geq 0) 是等价的（(a_i, b_i leq 10^9)）。

可以从值域的角度去考虑。考虑到值域上第一个不满足上面限制的位置 (k)，显然地 (k - 1) 满足条件，那么意味着 (a_i = k, b_i > k) 的数量比 (a_i = b_i = k) 的数量要大。为满足条件，需要找到一个 (b_i leq k, a_i > k) 的位置交换，否则无法满足条件。如果有多个满足条件的数，显然选 (a_i) 最大的最优。

于是考虑用优先队列维护一下，复杂度 (O(n log n))

ARC145

ARC145C

容易证明当且仅当相邻两个数相乘时原式取得最大值，所以考虑这个序列经过重排可以得到多少个序列。

首先显然地可以同时任意交换 (A_i) 和 (B_i)，方法数为 (n!)

然后可以任意选择一对 (A_i, B_i) 交换，方法数为 (2^n)

然后考虑将得到的 (A_i, B_i) 对应回排列 (P)。

对于一对相差 (1) 的正整数 ((a, b))，称 (a) 为左元素，(b) 为右元素，那么对于排列 (P) 的任意一个前缀，必定有左元素的总数大于等于右元素的总数。把左元素看成左括号，右元素看成右括号，那么合法的排列 (P) 等价于合法的括号序列。

长度为 (2n) 的合法括号序列的数量为卡特兰数，即 (frac{1}{n + 1} cdot {2n choose n})

所以最终的答案为 (2^n cdot n! cdot frac{1}{n + 1} cdot {2n choose n} = 2^n cdot frac{(2n)!}{(n + 1)!})，时间复杂度 (O(n))

ARC145D

神仙三进制构造。

假设存在一些互不相同的正整数，其中每一个数的三进制表示均只包含 (0, 1)，那么由这些数构成的集合一定符合除和为 (M) 外的所有限制条件。

证明：(forall x < y < z, x, y, z in S)，有 (z - y eq y - x) 实际上等价于 (2y eq x + z)。此时因为每个数的三进制表示上都只有 (0, 1)，所以 (x + z) 不可能进位。所以若 (2y = x + z)，那么对于 (y) 的三进制表示上的某一位：
1. 该位为 (0)，(x, z) 的这一位均为 (0)
2. 该位为 (1)，因为 (y) 的三进制表示只包含 (0, 1)，所以 (2y) 的三进制表示只包含 (0, 2)，故矛盾
3. 该位为 (2)，(x, z) 的这一位均为 (1)
所以若 (2y = x + z)，则一定有 (x = y = z)。又因为集合的互异性，所以矛盾，故原命题成立。

为使构造出的集合值域在 (pm 10^7) 内，贪心地考虑选取最小的 (n) 个满足条件的正整数。令这 (n) 个正整数的和为 (S)，此时如果 (n mid m - S)，因为显然给所有数同时增加一个值不影响答案，则只需要给所有数增加 (frac{m - S}{n}) 即可。因此考虑构造这样的一种情况。

我们注意到 (m - S leq n - 1 pmod n)，因此我们可以考虑给整个序列乘以 (3)，然后选择 (m - S mod n) 个数增加 (1) 即可消除余数。检验发现这样做也在值域内，所以直接写。

ARC143

ARC143C

分别考虑在每一堆石子上单独博弈的情况，显然先手的输赢是确定的。对于第一次操作，显然先手的人把所有先手必赢的位置全部取一次最优。此后先手的人只需要跟着后手的人操作同样的石子堆，显然此时先手必赢。

于是当存在先手必赢的石子堆时先手必赢，反之先手必输（初始时无法操作）。每个石子堆可以 (O(1)) 判断，复杂度 (O(n))

ARC143D

发现题目给的形式类似于拆点，可以考虑再拼回去。

具体地，从 (A_i) 向 (B_i) 连边建一张图。由于路径唯一，因此拆点后原图的桥一定对应若干条新图中的桥。将这些桥去掉，问题转化成给无向图中的每一条边定向，使得该图中桥和割点的个数之和最小。这里可以通过 dfs 树构造，树边按照遍历方向定向，返祖边从后代到祖先定向。

具体原理我也不是很懂，但是看上去很对

然后整理答案即可。

ARC143E

这种东西有一个已经草烂的结论：当且仅当白色点个数为奇数时有解

考虑叶结点。发现白色的叶结点必然在其父结点之前删除，黑色叶结点反之。于是可以确定这对父子结点之间操作的先后顺序。将一个点上的“装置”移除，实际上相当于删除该结点。于是可以将这些叶子结点和其父结点删除，又会产生新的叶结点。此时继续重复上面的流程，得到若干组父子结点的先后顺序。

问题转化成构造一组满足这些顺序约束且字典序最小的操作序列。发现实际上就是建 DAG 然后跑一次拓扑排序。

ARC134

ARC134C

可以考虑把题目限制转化为等价的形式：每次从同一个盒子中取出一对由 1 号球和其他球组成的球，经过若干次操作后，每个盒子内的球数量均不为 (0)，并且只有 1 号球。

于是可以考虑先给每个盒子都放入若干个 (1) 号球，然后把剩下的球按照上面的构造一对对放回去。对于 (i) 号球，显然将其放入 (k) 个箱子的方案数为 (C_{a_i + k - 1}^{k - 1})。最后考虑将剩下的 (a_1 - sumlimits_{i = 2}^n a_i) 个 1 号球放入 (k - 1) 个盒子，方案数为 (C_{a_1 - sumlimits_{i = 2}^n a_i - 1}^{k - 1})

于是最终的答案为 (prod_{i = 2}^n C_{a_i + k - 1}^{k - 1} cdot C_{a_1 - sumlimits_{i = 2}^n a_i - 1}^{k - 1})

用卢卡斯做就行。

ARC134D

神秘贪心。

考虑到肯定是优先把 (a_i) 最小的 (i) 选进来，此时分两种情况：

1. 存在 (1 leq k leq n)，使得 (a_k = a_i) 并且 (a_k geq a_{k + n})，显然此时选且只选 (k) 是最优的。

2. 反之，可以考虑将所有 (a_k = a_i) 的 (k) 选出，使得较大的 (a_{k + n}) 被延后。由于序列可以分成 (a_{p_1}, a_{p_2}, ..., a_{p_n}) 和 (a_{p_1 + n}, ..., a_{p_n + n}) 两部分，所以可以把 (a_k < a_{p_1 + n}) 的 (k) 也选进来。对于 (a_k = a_{p_1 + n}) 的情况，暴力判断加入是否可以使字典序变小。如果可以显然全选最优。

于是做完了，是不是很简单呢？

ARC141

ARC141C

考虑一个合法的字符串 S，设 (L_i) 为左数第 (i) 个左括号的下标，(R_i) 为右括号。你发现实际上 (P = L_1, R_1, ..., L_n, R_n, Q = L_n, R_n, ..., L_1, R_1)，根据 (P, Q) 把 (S) 草出来。然后再重新根据 (S) 把似乎是 (P, Q) 的东西草出来，看一看是不是和给的一样就行。

ARC140

ARC140C

随便手玩可以发现类似于这样的构造 ((X, X - 1, X + 1, X - 2, X + 2, ...))

虽然这样取不到理论上界，但是我们可以获得一些启发。

以 (N) 为奇数为例，(N) 为偶数的情况类似。考虑将 ([1, 2N]) 中除去 (X) 的数分成大小各为 (lfloor frac{N}{2} floor) 的两部分，分别记为 (L_1, L_2, ...) 和 (R_1, R_2, ...)。显然 (X, L_1, R_1, L_2, R_2, ...) 这样构造是最优的，可以取满上限 (N - 1)

但是这个难写，不如贺贺贺贺贺。

ARC140D

对于 (N) 个点 (N) 条边的无向图，考虑它的每一个连通分量。

假设某一个极大连通分量的大小为 (k)，显然有 (k - 1) 条边使得该连通分量连通。剩下一条边必然构成一个环，反之该连通分量会增加一个顶点。于是对于原图的每一个连通分量，其包含且仅包含一个环。

我们发现：原图中连通分量的个数等于环的个数。

然后考虑 (A_i = -1) 的结点对于连通分量个数的影响。分类讨论：

1. 环。显然它不包含 (A_i = -1) 的结点。

2. 基环树，也不包含 (A_i = -1) 的结点。

3. 树，此时有且仅有 (1) 个 (A_i = -1) 的结点在树上。

对于第一种和第二种情况，它们无法连接两个连通分量，考虑把它们先提出来，求出对答案的影响。假设这些连通分量的个数为 (x)，形态为树的连通分量的个数为 (y)，那么这两种情况的总贡献为：(x cdot n^y)

在分析树的情况前先记这些树分别为树 1，...，树 (m)。第 (i) 棵树的大小为 (t_i)

然后考虑 (A_i = -1) 的边连接若干个连通分量后形成了新的连通分量。显然它们构成的环可以被这样表示：树 (p_1) -> 树 (p_2) -> ... -> 树 (p_1)

对于该环中的边，显然它从上一棵树中的唯一一个 (A_i = -1) 的结点连过来，可以连到当前树上的任意一个结点。于是这条边有 (t_i) 种选择。那么对于 (k) 棵树构成的环，它对答案的贡献是：

((k - 1)! cdot prod_{i = 1}^k t_{p_i})

于是最终的答案为

(x cdot n^y + sumlimits_{k = 1}^m (k - 1)! cdot prod_{i = 1}^k t_{p_i})

其中 (p) 是由任意 (k) 棵树的编号构成的序列。

上式可以暴力 (O(n^2)) 求出，也可以写高明的分治 NTT

ARC140E

第 (i + 1) 行第 (j + 1) 列的数为 ((lfloor frac{i}{23} floor cdot lfloor frac{j}{23} floor + i + j) mod 23 + 1)

证明可以看官方题解。

你问我怎么想到的？这不是非常非常显然吗

ARC139

ARC139D

题解

ARC126

ARC126C

观察样例发现当 (K) 足够大时使所有数相等最优，反之由于 (gcd(a_1, ..., a_n) leq min(a_1, ..., a_n))，可以合理猜测 (gcd) 不超过 (3 imes 10^5)。显然取到一个 (gcd) 的代价可以贪心计算（取到下一个 (K) 的倍数）。

不妨设 (cnt_i = sumlimits_{j = 1}^n [a_j leq i], pre_i = sumlimits_{j = 1}^n max(i - a_j, 0))。显然地 (gcd = i) 时的代价为 (sumlimits_{k = 0}^{frac{max(a_j)}{i}} pre_{(k + 1)x} - pre_{kx} - cnt_{kx} cdot x)

并且有 (pre_{i + 1} = pre_i + cnt_i, cnt_{i + 1} = cnt_i + sumlimits_{j = 1}^n [a_j = i + 1])

于是可以 (O(n ln n)) 做。

ARC127D

首先答案可以表示成先把 ([1, K]) 的数聚在一起，然后再排序需要的操作次数。

假设我们选出了 (K) 个元素，那么有结论：将 (K) 个元素聚拢在中间的元素最优。令 (m) 为这 (K) 个位置的中位数。考虑从前往后加入，那么当加入第 (m) 个数时，(m) 恰好是要求子段的中间位置。

观察到 (K leq 16)，于是考虑状压 dp。令 (F_S) 为已经聚拢的数集等于 (S) 时需要的最小代价。枚举最后一次加入的数 (a_i)，发现很难得到转移。

不妨将最终的贡献写出来。令初始选择的 (K) 个元素的下标为 (p_1, ..., p_K)，最终得到的子段的下标为 (q_1, ..., q_K)。显然地，(forall 1 leq i < m)，对答案的贡献之和为 (sumlimits_{i = 1}^{m - 1} |p_i - q_i| = sumlimits_{i = 1}^{m - 1} q_m + i - p_i)。同理 (forall m < i < K)，对答案的贡献之和为 (sumlimits_{i = m + 1}^K p_i - (q_m + i))。

我们发现当 (K) 是偶数时 ((q_m + i)) 可以抵消，而 (K) 是奇数时会在 (m + 1) 处剩下一项。于是我们考虑在转移时只考虑 (p_i) 的影响，然后在加入第 (m) 个数时判断是否需要这一项即可。