CF 比赛题解合集

[TOC]

$\downarrow 2023.09.04$

CF1952, CF1954

1952

A. Ntarsis' Set

有一个集合，初始状态里面有数字 $1$、$2$、$3$、$4$、$5$、......、$10^{1000}$。

现在给你一个长度为 $n$ 数组 $a (1\leq a_i \leq 10^9 )$，要进行 $k$ 次操作，每次操作将当前集合中第 $a_1$ 小、第 $a_2$ 小、......、第 $a_n$ 小的数同时移除。

请问 $k$ 次操作之后，最小的数是多少。

顺难则逆。

考虑如果已知删除后在集合中的位置，可以很简单的找到删除前的位置。

所以已知初始的位置，也可以很简单的找到删除后的位置，$O(n + k)$ 即可。

void work() {
    int n, k; cin >> n >> k;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    lint i = 1, cur = 1, pre = 0;
    while (k--) {
        cur += pre;
        while (i <= n && a[i] <= cur)
            ++cur, ++i, ++pre;
    }

    cout << cur << '\n';
}

B. Imbalanced Arrays

对于一个给定的长度为 $n$ 的数组 $A$，定义一个长度为 $n$ 的数组 $B$ 是不平衡的当且仅当以下全部条件满足：

• $-n \leq B_{i} \leq n$ 且 $B_{i} \ne 0$。即每个数在 $[-n,n]$ 内且不为 $0$。

• $\forall i,j \in [1,n], B_{i} + B_{j} \neq 0$。即数组内不存在一对相反数。

• $\forall i \in [1,n], \sum_{j = 1}^{n} [ \left (B_{i} + B_{j} \right) > 0] = A_{i}$。即对于任意的 $i$，数组中与 $B_{i}$ 和大于 $0$ 的数的个数恰好为 $A_{i}$。注意：这里需要计算本身。也即 $i$ 与 $j$ 可以相等。

请构造长度为 $n$ 的不平衡序列。

两种方法，其一可以参见 hfjh。

考虑递归的构造序列，如果当前存在 $A_i = 0$ 或者 $A_i = n$，那么其对应所填的数必定为 $-n$ 或者 $n$。

由于相反数不可能同时出现，所以两个不能同时存在，否则无解。

递归的构造即可。

代码链接：https://codeforces.com/contest/1852/problem/B

C. Ina of the Mountain

• 给定一个长度为 $n$ 的序列 $a$ 和正整数 $k$。

• 每次可以选择一个区间 $[l,r]$，$\forall i \in [l,r],a_{i} = a_{i} -1$。

• 如果 $a_{i} = 0$，则将 $a_{i}$ 变为 $k$。

求让序列全部为 $k$ 的最小操作次数。

多组测试数据，$1 \leq n \leq 2 \times 10^{5}$。

先不考虑 $\bmod k$ 的情况，则构造差分序列 $d$，答案即为：

$$\sum_{i} [d_i \gt 0]d_i $$

那么考虑每次 $0 \to k$ 的变换，相当于在原序列上加了 $k$，然后求上式。

考虑变成差分序列上加减。也就是有地方 $+k$，有地方 $-k$，使得上式最小。

所以考虑正负平衡一下即可。

代码链接：https://codeforces.com/contest/1852/submission/221761642

能考场切自是极好。

D. Miriany and Matchstick

你有一个 $2\times n$ 的矩阵，第一行给定（字符串 $s$），你需要在第二行的位置填上 $A$ 或 $B$。

你需要构造矩阵的第二行，使得该矩阵相邻的格子不同的个数恰好为 $k$。

考虑很 naive 的 DP $f_{i, 0/1, k}$ 表示填完前 $i$ 个数，恰好为 $k$ 是否可行。

打表可以发现，$k$ 可行的集合至多为两个区间。

证明：每一次转移可以是 $+1$ 或者 $+2$，同时又是前面的两个区间并过来的，所以空缺只会是 $0/1$ 个。

所以可以压成 $f_{i, 0/1}$ 即可 /kel

$$f_{i, 0} = (f_{i - 1, 0} \cup (f_{i - 1, 1} + 1)) + (s_i \ne s_{i - 1}) \\ f_{i, 1} = ((f_{i - 1, 0} + 1) \cup f_{i - 1, 1}) + (s_i \ne s_{i - 1}) $$

所以可以用 bitset 对吧。

最后贪心的构造即可。

E. Rivalries

Ntarsis 有一个长为 $n$ 的数组 $a$。

定义一个子数组 $a_l \cdots a_r$ 的权重为：

• 在整个数组 $a$ 中，只出现在该子数组 $a_l \cdots a_r$中的最大元素 $x$。
• 若不存在这样的 $x$，权重为 $0$。

称数组 $b$ 与 $a$ 数组匹配，当且仅当满足：

• $2$ 者长度相等。
• 数组 $a$ 中的每个子数组的权重都与数组 $b$ 对应的子数组的权重相等。
• $b$ 中的数都为正数。

最大化 $b$ 的权值和。

$1 \le n,t \le 10^5$

考虑几个 hints

• 对于每一个值，只有最左边和最右边的两个之外的区间可以做出贡献。

• 将最左和最右记成二元组，如果存在 $a_i \gt a_j$ 并且 $i$ 完全被 $j$ 覆盖，那么 $j$ 将无法做出任何贡献。

• 为了不改变权重，我们只可能增加上面所说的 $j$ 区间。

• 并且至多会有一个区间会加上某一个数。

1954

A. Dual

有 $t$（$1\le t\le 500$）组数据，对于每组数据给出一个长度为 $n$（$1\le n\le 20$）的序列 $a$（$-20\le a_i\le 20$）。

可以进行 $k$（$0\le k\le 31$）次操作，每次操作任选一组 $i,j$（$1\le i,j\le n$），把 $a_i\leftarrow a_i+a_j$，最后使得整个序列单调不减。

对于每组数据，第一行输出 $k$，之后 $k$ 行输出执行操作的 $i,j$。

超级分讨。

考虑到全部变成正的，或者全部变成负的，然后前缀/后缀和即可，这需要 $19$ 次。

首先找到绝对值最大的那个数。

如果异号的个数 $\le 12$，那么直接加上即可。

反之，则同好的个数 $\le 7$，那么找到最大的正数，做 $5$ 次自加操作，然后加上去即可。

代码链接：Submission #221821611 - Codeforces

B. Earn or Unlock

有一长度为 $n$ 的一副牌，每张牌上都有一个数字，设第 $i$ 张牌上的数字为 $a_i$。初始时，你手里只有第一张牌。对于每一张牌，你有两种选择：

• 如果剩余的牌数量 $< a_i$，则将牌摸完，否则继续往下摸 $a_i$ 张牌。摸牌完成后，这张牌会被丢弃。

• 获得 $a_i$ 的分数，并丢弃这张牌。

求你能获得的最大分数。

对于所有数据，保证 $1 \le n \le 10 ^ 5$，$0 \le a_i \le n$。

考虑如果可以摸完 $k$ 张牌，由于摸一张牌的代价为 $1$，所以得分为：

$$- k + 1 + \sum_{i = 1}^k a_i $$

所以判断哪些地方可以摸到即可。

考虑一个 naive 的 $O(n^2)$ DP。

有：

$$f_i |= f_{i - a_i} \text{~ then ~} f_i = 0 $$

于是可以考虑用 bitset 优化。

所以总的复杂度为 $O(\frac {n^2} w)$。

代码：https://codeforces.com/contest/1854/submission/221792387

C. Expected Destruction

给定大小为 $n$ 的正整数集合 $S$，$S$ 中的每个数在 $1\sim m$ 之间。

每一秒进行如下操作：

1. 从 $S$ 中等概率随机选择一个数 $x$。
2. 将 $x$ 从 $S$ 中删去。
3. 若 $x + 1\leq m$ 且 $x + 1\notin S$，则将 $x + 1$ 加入 $S$。

求 $S$ 变成空集的期望时间，对 $10 ^ 9 + 7$ 取模。

$1\leq n\leq m \leq 500$，$1\leq S_1 < S_2 < \cdots < S_n \leq m$。

1843

Div. 3 果然简单，虽然但是，我还是有 1 道题没有想出来。

A.Sasha and Array Coloring

排序双指针向内即可。

https://codeforces.com/contest/1843/submission/210855587

B.Long Long

好啊，就是这道题没想出来。

Virtual Contest 上完成了一半。

考虑把符号相同（0 与任何数符号相同）的合并。

因为放在一起操作显然最优。

bool sgn_eq(int x, int y) {
    return (x * y) >= 0;
}

然后你就得到了一个 ... + - + - ... 正负交替的序列。

那么，很明显，正数与负数的个数相差不超过一，也就是说花费 1 的代价将负数转化为正数的行为是不可取的（我就死在这上面，如此弱智的东西……），于是记录所有负数的个数即可。

有可能溢出，要精细实现

https://codeforces.com/contest/1843/submission/211085413

也可以直接合并负数序列（忽略 0 的情况）

https://codeforces.com/contest/1843/submission/211082437

C.Sum in Binary Tree

会手写堆的人都会写……

Submission #210856724 - Codeforces

D.Apple Tree

弱智题……记录一下每一个节点有多少个叶子节点。输出相乘的结果即可。

https://codeforces.com/contest/1843/submission/210857337

E.Tracking Segments

其实可以改一下题目，变为：

对于每一条线段，求出其变成 beautiful segment 的时间，如果不会变，则输出 -1，顺便强制在线一波。这样代码难度递增。

我首先想到的是一个在线做法。

只要在这个区间内修改了严格大于一半的点，那么一个区间就变得 美丽。

那么什么最早是什么时候？

定义序列 $t_i$ 表示第 $i$ 个点变成 $1$ 的时间，如果没有修改则 $t_i = \inf$。

对于区间 $[l, r]$，设 $k = \lfloor \frac {l - r + 1} 2 \rfloor + 1$，则对于序列 $t$ 的区间 $[l, r]$ 第 $k$ 小即为所求。

如果为 $\inf$ 则不会变得 美丽。

但是显然这太过于复杂。

考虑离线处理每一个线段，并且二分答案。

明显答案具有单调性，如果在 $t$ 时变得 美丽，则之后一直会很 美丽。

我说的不是我们

我们只加入前 $mid$ 个点，然后用一个前缀和一一判断有没有 美丽 的线段即可。

如果是 美丽 的，则满足在这个区间内有 $\ge k$ 个点变成了 $1$。

https://codeforces.com/contest/1843/submission/211083551

F.Omsk Metro

自己做的时候胡的性质：

对于一个路径 $p$，定义其最大子段和为 $mx_p$，最小子段和为 $mn_p$。

那么可以拼凑出来的区间为 $[mx_p, mn_p]$。

感性证明一下：

这里不妨把一条路径拍扁成一条链，设为 $[l, r]$。

我们考虑加入一个点 $r$ 对于一条路径 $[l, r]$ 的影响。

设 $suf_x$ 为以 $x$ 为右端点，可以凑出来的权值的集合。

考虑递推，有 $suf_x = \{0, w(x)\} \cup （suf_{x - 1} + w(x))$。

于是对于区间 $[l, r]$ 有 $S = \bigcup_{l \le x \le r} suf_x$。

其实不难发现，$suf_x$ 的上下界每一次最多只会变化 $1$，也就是说，如果可以凑出 $x (x \ge 0)$，那么一定可以凑出 $[0, x]$。负数的情况同理。

所以我们考虑求出最大的，和最小的子段和即可 $O(1)$ 判断……

实现上也就是树链剖分加上基本的求区间最大子段和的思路即可。

1834

Virtual Contest 做了 5 道题，非常不错。

A.Unit Array

秒切题，判断个数，然后判断一下奇偶即可。

提交：https://codeforces.com/contest/1834/submission/211190220

B.Maximum Strength

题目描述

每一种材料的力量由一个十进制整数表示。

对于一个武器，由两种材料构成。假如第一种材料的力量为 $X = \overline{x_1x_2 \dots x_n}$，第二种材料的力量为 $Y = \overline{y_1y_2 \dots y_n}$，那么这个武器的力量为 $\sum_{i = 1}^n |x_i - y_i|$，也就是 $|x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|$。

如果两个数字长度不一样，则要将短的数字用前导零补成相同长度。

现在，你拥有无数个力量在 $[L, R]$ 中的材料。你想要选出两个材料做出一个力量最大的武器。请你求出你设计出的武器力量的最大值。

题解

找到第一个不同的地方，其他地方全部填 $|9 - 0|$ 即可。

大数填 0，小数填 9，这样一定满足在区间内。

提交：Submission #211191108 - Codeforces

C.Game with Reversing

题目描述

你有两个长度为 $n$ 的序列 $S, T$。

你将不断重复以下步骤直到两个序列相等：

1. 在 $S$ 或者 $T$ 中任意选择一个数字，然后修改为另一个数字。如果此时序列相等，则结束操作，否则进入操作 $2$。

2. 任意反转一个序列。如果此时序列相等，则结束操作，否则重复操作 1。

注意：操作 $1$ 和操作 2 都计入操作次数中。

你需要输出最小化的操作次数。

解题

正序和逆序分别讨论一下，取 $\min$ 即可。

设 $icnt$ 表示正序不同的个数，$rcnt$ 表示逆序不同的个数。

那么 $ans = \min(2 \times icnt - icnt \% 2, 2 \times rcnt - (rcnt - 1) \% 2)$。

提交：https://codeforces.com/contest/1834/submission/211198802

D.Survey in Class

对于每一个学生的学习集合，答案是 $2 \times \max(|S_1| - |S_1 \cap S_2|)$。

$O(n \log n)$

考虑使用树状数组维护线段，从左向右扫一遍。

$O(n)$

考虑两条线段的关系，三种：

• 左边

• 相交

• 右边

对于每一个 $S_1$，我们需要最小化 $|S_1 \cap S_2|$，所以对于三种情况，我们维护三个线段：

• 右端点最左

• 最短

• 左端点最右

分别判断即可。

提交：Submission #211192375 - Codeforces

E.MEX of LCM

我考场上的做法

考虑只有 $O(n^2)$ 个取值，那么 $mex$ 一定 $\le n^2$。所以我们限制了答案的上界，设为 $U$。

实际上有更紧的上界，根据：CF1834E MEX of LCM 题解 - LCTTTTTTTTTTT - 洛谷博客，$U$ 可以 $= 4256233$。

考虑对于一个固定的右端点，其左端点与其匹配的 $lcm$ 是单调的，并且不同的数量在 $O(\log U)$ 。

考虑每一次变化 $lcm$ 至少 $\times 2$。

所以考虑用一个 set 维护。

同时，再用一个 set 维护所有出现过的 lcm （考虑是 $O(n \log U)$ 个，空间没问题）

所以总复杂度为 $O(n \log V \log U \log \log U)$。

提交：Submission #211194246 - Codeforces

还有的思路

考虑每一个左端点，可以二分找 lcm 的分界，当值大于上界的时候退出。

用桶或者什么东西操作一下即可。

复杂度为 $O(n \log U \log n)$。

然而还有玄学优化，参考：出错了 - 洛谷，在 题解界面 看 @Xy_top 的即可。

$\downarrow 2023.09.06$

1830

B. The BOSS Can Count Pairs

多组数据。

每组数据给你一个 $n$ 和两个序列 $a,b$。

求有多少个数对 $(i,j)$ 满足 $1 \le i < j \le n$ 且 $a_i \times a_j = b_i + b_j$

对于每一个 $i$ 看作用 $a_i \times x - b_i = y$ 这条线来切所有的点。

注意到当 $a_i$ 很大的时候的简单的，我们只需要用一个桶记录一下 $(x, y)$ 的个数即可，然后可以 $O(\frac n {a_i})$ 求出。

此时设一个阈值 $B$，当 $a_i \gt B$ 的时候认为是很大的，所以上面的复杂度可以看作 $O(\frac n B)$。

问题在于当 $a_i$ 很小的时候，注意到其实可以 $O(B)$ 预处理出 $\forall k \in [1, B]$ $k \times a_i - b_i$ 的值。

这样就可以 $O(1)$ 查询了。

两者稍微平衡一下，令 $B = \sqrt {2n}$ 于是可以 $O(n \sqrt {n})$ 解决本题。

代码链接： https://codeforces.com/contest/1830/submission/222008847

C. Hyperregular Bracket Strings

给定一个数 $n$ 和 $k$ 个区间 $\left[l_i,r_i\right]\in [1,n]$。

我们定义，对于一个长度为 $n$ 的，仅由 ( 和 ) 组成的合法括号序列，如果它的每一个区间 $\left[l_i,r_i\right]$ 内的子串都是合法括号序列，那么这个括号序列是好的。

求好的括号序列的数量，答案对 $998244353$ 取模。

相交和包含的情况很 naive，重点在于如何处理。

类比 $2023.09.05$ izumi，采用一个随机化异或的做法。

每一个区间附上一个神秘的权值，差分前缀一次。

如果异或权值相同，意味着需要形成一个合法括号，这预处理卡特兰数即可。

rapper 的讲解见：hfjh

代码链接：https://codeforces.com/contest/1830/submission/222007540

D. Mex Tree

给定一棵 $n$ 个结点的树，点有点权，点权为 0 或 1。你需要给一种指定点权的方案，使得每一条路径的点权 $\operatorname{mex}$ 之和最大。

$n\le 2\times 10^5$，多组数据。

如果考虑跨越多种数的正贡献，发现很难。于是考虑块内的负贡献。

正难则反！！！！！！！！！！！！！！！！！！！！！！！哦

对于每一个连通块，考虑树形背包。

$$\begin{aligned} f_{x, i, 0} &\leftarrow \min(f_{x, i, 0} + f_{j, k, 1}, f_{x, i - k, 0} + f_{j, k, 0} + (i - k) \times k) \\ f_{x, i, 1} &\leftarrow \min(f_{x, i, 1} + f_{j, k, 0}, f_{x, i - k, 1} + f_{j, k, 1} + 2 \times (i - k) \times k ) \end{aligned} $$

关键结论是连通块的大小一定不会很大，否则减少的贡献太多了。

有证明在 $n \le 2e5$ 小不会超过 $258$。

代码：https://codeforces.com/contest/1830/submission/222027041

E. Bully Sort

对于一个非升序的排列 $\{p_i\}$，定义一次操作为按顺序执行以下步骤：

1. 令 $p_i$ 为排列中最大的满足 $p_i\neq i$ 的数。

2. 令 $p_j$ 为排列中最小的满足 $i 的数。

3. 交换 $p_i$ 和 $p_j$

可以证明在排列非升序的前提下总能找到满足条件的 $i$ 和 $j$。

定义一个排列的权值为将其升序排序所需的操作次数，可以证明总能在有限次操作内将其升序排序，注意如果排列本身就是升序的那么其权值为零。

现在给定一个排列和若干次修改操作，求出每次修改后排列的权值，每个修改操作为交换排列中指定的两个数。

注意修改是永久的。

发现排序方式和冒泡排序很像，于是考虑与逆序对之间的关系。

发现每次交换 $(i, j)$ 使得逆序对的个数减少 $2(j - i) - 1$。

发现 $2(j - i)$ 这个东西很好，考虑交换会影响什么改变 $2(j - i)$。

发现 $\sum_{i = 1}^n |p_i - i|$ 符合要求。

发现两者最后都为 $0$。

发现操作次数等于 $\sum_{i = 1}^n |p_i - i|$ 与逆序对个数之差。

于是动态维护逆序对即可。

发现分块很优秀，$O(n \sqrt{n \log n})$，虽然是正常的 $O(n \log^2 n)$ 的树套树的四倍时间……

代码：https://codeforces.com/contest/1830/submission/222012835

1836

A.Destroyer

开个桶记录个数，看满不满足单调不上升即可。

B.Astrophysicists

辛辛苦苦写了这么久的文章就没了？？？？烦死了。

自己做 Virtual Contest 的时候这道题打表打了半天（20min）才搞定……

题目大意

有 $n$ 个人，$k$ 个金币，每个金币价值 $g$ 个银币。

良心公司要把这 $k$ 个金币作为工资分给这 $n$ 个人，但是没有办法平均分配，良心老板想出了分配规则：

• 由你设定每个人分配的银币数 $x_i$。

• 你需要保证 $\sum_{i = 1}^n x_i = k \times g$。

• 老板会把银币数转化为金币发放，所以想出了以下规则：

  • 令 $r = x \mod g$，如果 $r \ge \lceil \frac g2 \rceil$，那么公司会额外花费 $g - r$ 个银币以凑出完整的金币（此时花费了 $x + g - r$ 个银币）。

  • 反之，会吞掉这 $r$ 个银币以凑出完整的金币（此时花费了 $x - r$ 个银币）。

假定最终公司的花费为 $p$ 个银币。你需要最小化 $p$，并输出 $k \times g - p$。

解题思路

如果开始没有思路，那么打表是一个很好的方法。

首先我们可以很轻易的得到一个 $O(nkg)$ 的 DP 算法。

设 $f_{x, i}$ 表示处理到第 $x$ 个人，一共分配了 $i$ 个银币公司省下的最多银币。

有转移方程：

$$f_{x, i} = \max_{0 \le j \le i} f_{x - 1, i - j} + w(j) $$

其中：

$$r = j \mod g $$

$$w(j) = \begin{cases} r - g &, r \ge \lceil \frac g2 \rceil \\ r &, r \lt \lceil \frac g2 \rceil \end{cases} $$

运行后输出 DP 数组，结合 $m = \lceil \frac g2 \rceil - 1$可以很轻易的发现规律：

最终的数组分为两个部分：

• 第一个部分为 $[0, nm]$，下标与数值一一对应。

• 第二部分为 $[-\lfloor \frac g2 \rfloor - m - nm, nm]$ 不断循环。

现在我们来严谨证明一下。

理想状态下，我们自然是给每一个人分发 $m = \lceil \frac g2 \rceil - 1$ 个银币，这样就可以吞掉 $nm$ 个银币。

但是可能存在一下两种情况：

• 其实根本没有 $nm$ 个银币，所以全部都分配到 $\le m$ 个。所以全部可以吞掉。对应上文中第一部分。

• 还剩下了 $r = k \times g - nm$ 个银币。由于我们可以按照一个金币为单位再分配，所以我们只需要关注 $r \mod g$ 的值。

  显然，如果把这些银币分给不同的人是不优的，因为破坏了老板吞掉更多人 $m$ 个银币的美梦。

  所以这些银币应该全部分配给一个人，对于答案做出贡献 $w(m + k \times g- nm) - m$。

  （化简一下）对应上文中第二部分。

提交记录：https://codeforces.com/contest/1836/submission/211134556

C.k-th equality

注意，注意：

Each input file has at most 5 test cases which do not satisfy A,B,C≤3.

所以，$O(10^{\min(A, B)})$ 可以过。

那么考虑顺序枚举 $A$ 位的数 $a$，满足的数 $b$ 应该为一个连续区间，这个可以 $O(1)$ 解决。

所以区间长度与 $k$ 判断一下即可。

提交记录：https://codeforces.com/contest/1836/submission/211137329

1835

B. Lottery

给定一个长度为 $n$ 的序列 $v$，其值域为 $[0,m]$。

现在你需要选择一个 $x \in [0,m]$，使其权值最大。定义一个数 $x$ 的权值为：

$$\sum_{c=0}^{m}[\sum_{i=1}^{n}[\vert v_i - c \vert \leq \vert x - c \vert] < k] $$

请你找到权值最大的数 $x$，若有多个，输出最小的那个。

考虑 $k = 1$ 的特殊情况，发现两个人内部的所有点都造成了 $\frac 12$ 的贡献。所以告诉我们不需要枚举太多的点，在一些点的周围枚举一下即可。

这可以很合理的外推到所有的 $k$ 的情况。

C. Twin Clusters

给定 $2^{k+1}$ 个 $[0,4^k)$ 内的整数，请求出任意两个不交非空区间使得其异或和相等，若无解则输出 -1。

抽屉原理抽象题。-1 是不可能的，这一定有解。

于是考虑生日悖论，随机化一些区间即可（逃。

考虑正解，将 $4^k$ 分成前 $k$ 位和后 $k$ 位。

前缀异或和有 $2^{k + 1} + 1$ 个，而前 $k$ 位最多有 $2^k$ 种取值。所以至少会有 $2^k + 1$ 对前 $k$ 位相等的前缀。

考虑把这些对找出来，其后 $k$ 位却也只有 $2^k$ 种取值，所以至少有两对的后 $k$ 位的异或值相等。所以就完了。

代码：https://codeforces.com/contest/1835/submission/222050899

D. Doctor's Brown Hypothesis

给定一张 $n$ 个点 $m$ 条边的简单有向图和常数 $k$，请求出有多少组 $(x,y)$ 满足 $1\le x\le y\le n$ 且存在一条 $x$ 到 $y$ 和一条 $y$ 到 $x$ 的长为 $k$ 的路径，$k\ge n^3$。

发现 $n^3$，所以发现可以随便走环凑最小公约数。

于是先缩点，在连通块内考虑。

找出生成树，考虑一个非树边，有结论，$d | \mathrm{abs}(dep_y - dep_x - 1)$。

所以可以找出 $d$，而合法当 $k \equiv 0 \pmod d$ 或者 $d \equiv 0 \pmod 2 \text{ and } k \equiv \frac d2 \pmod d$。

用桶记录一下即可。

代码：Submission #222076413 - Codeforces

1827

A. Counting Orders

简单计数。

两个都排序，双指针维护一下 a[i] 在 b[p] 的位置（a[i] <= b[p]）。

那么方案数 $\times (p - i)$。

提交：https://codeforces.com/contest/1827/submission/211387552

C. Palindrome Partition

回文好题。

考虑利用 Manacher 求出每一个偶数的回文串。

参考：算法学习笔记(13): Manacher算法 - jeefy - 博客园

观察可以发现：每一个合法的串都可以被划分为多个最小的合法串，并且划分方法是唯一的。

所以考虑如下：

我们需要维护出每一个点作为右端点，最靠近的左端点。

这等价于求出满足 $i + p[i] \ge x$，求 $\max i$。

• 做法1：利用上面的限制，可以通过 ST 表求解。

  • 参考：算法学习笔记(3): 倍增与ST算法 - jeefy - 博客园，以及题解：https://codeforces.com/blog/entry/116109

• 做法2：由于需要中心最大，所以逆序处理，利用每一个中心更新没有更新过的点。

  由于每一个点只需要更新一次，考虑使用链表或者并查集维护。我用的是并查集。

然后，设上面对于端点 $i$ 求出来的结果为 $g_i$。

得出最终的递推式：

$$f_i = \begin{cases} 0 &,g_i = 0 \\ f_{i - g_i} + 1 &, g_i \ne 0 \end{cases} $$

其中 $f_i$ 表示以 $i$ 结尾的合法的串的个数。

最终的答案为 $\sum f_i$。

提交：Submission #211396680 - Codeforces

D. Two Centroids

性质好题。

重心有如下性质：

• 最大子树大小 $\le \lfloor \frac n2 \rfloor$。

• 新增一个叶子节点，重心最多变化一条边。

• 重心至多有两个。

那么我们考虑每次加入一个点对于原来重心 $c$ 的影响，并设当前最小的子树大小为 $mx$。

• 如果加入的叶子节点在 $c$ 的子树 $t$ 内。更新 $t$ 的大小，并更新 $mx$。如果此时 $mx \ge \lfloor \frac n2 \rfloor + 1$，那么重心向 $t$ 移动。并且此时 $mx$ 更新为 $\lfloor \frac n2 \rfloor$（不考虑，把图画出来就明白了。

• 由于我们不可能动态维护以每一个重心为根，所以还要考虑其祖先的情况（同理）。

然后就是如何找 $t$ 的问题。有两种解决方案：

• 无论如何首先可以通过 dfn 序判断是否在其子树内。

  • 方案1：利用倍增的方法跳祖先。空间复杂度 $O(n \log n)$，单次 $O(\log n)$。

  • 方案2：利用 dfn 区间，对于每一个节点保存其子节点的 dfn，每次二分找到叶子的 dfn 所在的区间即可。（我用的这种方法）空间 $O(n)$，单词 $O(\log n)$。

• 实测第二种要快一点点（也快不了多少，主要是常数够好）

提交：Submission #211401150 - Codeforces

E. Bus Routes

差点没用 dlang 卡过去

思路1

考虑更严的限制（等价）：叶子节点间两两可以在两次内到达。

于是考虑对于每一个叶节点，求出其能到达的最高的祖先 $high(x)$。

也就是求一个 LCA 即可。

那么满足条件的必要条件是每一对 $high(x), high(y)$ 满足祖先/子节点关系。

如果不是，那么至少需要三条路径。

如果满足上述条件，那么所有的 $high$ 满足在一条链上。

那么可以通过 dfn 序判断。

这并不充分。

考虑找到最低那个 $high(x)$，并以 $high(x)$ 作为根。

此时重新求一次 $high$，如果所有的 $high$ 都为 $high(x)$，那么就是 $ok$ 的，否则，如果有 $high(y) \ne high(x)$，那么 $x, y$ 不可达。

不要写倍增求 LCA，利用 ST表 $O(n \log n) \sim O(1)$ 或者 树链剖分 $O(n) \sim O(\log n)$ ，甚至是离线 $O(n)$ 求。倍增太慢了，dlang 卡不过去。

思路2

参考 Alex_Wei 的博客：https://www.luogu.com.cn/blog/_post/575397。

利用 DSU on tree。

思路3

维护虚树并树上差分。非常的高效。

参考：CF1827E Bus Routes - Kubic 的博客 - 洛谷博客

1824

LuoTianyi and the Show

有 $n$ 个人观看一场与 VOCALOID 有关的演出，场地里有一行座位，从左到右标号 $1$ 到 $m$，接下来观众将按顺序以如下三种方式中的一种选择座位：

1. 如果没人坐在座位上，就坐在座位 $m$ 上，否则坐在目前最靠左的人的左边。若座位 $1$ 有人，则离开。
2. 如果没人坐在座位上，就坐在座位 $1$ 上，否则坐在目前最靠右的人的右边。若座位 $m$ 有人，则离开。
3. 如果 $x_i$ 没人则坐在 $x_i$，否则离开。

现在知道每个人选择座位的方式，你可以让人们按照任意顺序入场，求最多找到座位的人数。

安排方式只有三种，1/2/3 分别先，依次向左/向右/向两边扩展即可。

LuoTianyi and the Floating Islands

给定一棵 $n$ 个结点的树，现在有 $k(k\le n)$ 个结点上有人。

一个结点是好的当且仅当这个点到所有人的距离之和最小。

求在这 $n$ 个点中随机取 $k$ 个点时，好的结点的期望个数，对 $10^9+7$ 取模。

发现用点来算很难算，于是考虑用边来算贡献。由于每种情况边会比点数少 $1$，所以期望点数等于期望边数 $+1$，于是考虑边如何做贡献，两边的点数相等即可。

于是就搞定了：https://codeforces.com/contest/1824/submission/222881710

LuoTianyi and XOR-Tree

给定一棵 $n$ 个节点的树，根节点为 $1$ ，每个点有一个点权 $a_i$ ，每次操作可以选择一个点任意修改点权，求最少的操作次数，使得每一条根结点到叶子结点的路径上的异或和都为 $0$ 。

如果要相等，那么只需要子树所有相等，那么改变只需要改变自己即可。

所以找到子树中最多的那个值，保留即可。

并且启发式合并即可……

代码：https://codeforces.com/contest/1824/submission/222885893

注意 if (maxcnt > 1) 的优化，否则会 TLE。

LuoTianyi and the Function

Feyn 给了你一个长度为 $n$ 的整数数组 $a$，下标由 $1$ 开始。

用以下方式定义函数 $g(i,j)$：

• 当 $i\le j$ 时，$g(i,j)$ 是满足 $\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}$ 的最大整数 $x$；
• 否则 $g(i,j)=0$。

$q$ 次询问，每次给定 $l,r,x,y$，请求出 $\sum\limits_{i=l}^r\sum\limits_{j=x}^y g(i,j)$ 的值。

需要个可以区间赋值和历史版本求和线段树……不会额。

$\downarrow 2023.09.11$

1819

A. Constructive Problem

给定整数 $n$ 和一个非负整数序列 $a$。

你需要选择整数 $l,r,k(1\leq l\leq r\leq n;0\leq k)$，然后将 $a_l,a_{l+1},\cdots,a_r$ 的值均变为 $k$。

判断能否通过恰好一次上述操作使操作后的 $\mathrm{mex}(a)$ 增加 $1$。

如果没有 $\mathrm{mex}(a) + 1$ 的存在，并且 $\mathrm{mex}(a) \lt n$，那么一定存在方案。

否则，需要变换所有的 $\mathrm{mex}(a) + 1$，而为了使影响最小，只是恰好包含所有的区间变成 $\mathrm{mex}(a)$，重新求一次 $\mathrm{mex}$ 即可。

代码：https://codeforces.com/contest/1819/submission/222839488

B. The Butcher

有一张 $h\times w$ 的纸片，但你并不知道 $h$ 与 $w$ 的具体数值。现在对这张纸片进行 $n-1$ 次裁剪。每次裁剪后会将其中一半收归（即这一半不会再被裁剪），保证纸片不会被旋转。

告诉你最终裁剪后的 $n$ 张纸片长宽，问初始有多少 $h\times w$ 的纸片可以裁剪成这 $n$ 张纸片，输出所有可行的 $(h,w)$。

发现一张一定是 $h$ 或者 $w$，那么找到 $\max h$ 和 $\max w$ 作为两种可能即可。

由于每次减下 $w, h$ 递减，所以考虑双指针扫一遍即可。

代码：https://codeforces.com/contest/1819/submission/222845297

C. The Fox and the Complete Tree Traversal

给定整数 $n$ 和一棵包含 $n$ 个节点的树。

记 $\text{Dist}(x,y)$ 表示树上节点 $x,y$ 之间最短路径的边数。

你需要判断是否存在一个 $1\sim n$ 的排列 $p$，满足：

• $\text{Dist}(p_i,p_{i+1})\leq 2$ 对任意整数 $i(1\leq i 成立。
• $\text{Dist}(p_1,p_n)\leq2$。

存在则输出 Yes 然后输出任意一个满足要求的 $p$，不存在则输出 No。

有两种方法，一种是我考场想出来的，分讨比较严重：

先考虑状态 $f_{x, 0/1}$ 表示走完其子树后是否可以在其子节点或者本身上。

发现叶子节点对于其可行性没有影响，考虑非叶节点的影响。

不难分类讨论，设当且节点为 $x$：

• 如果没有非叶节点，那么不难发现最后无论在哪里都可以。

  

• 如果只有一个非叶节点 $y$，那么发现 $f_{x, 0}$ 满足当且仅当 $f_{y, 1}$ 满足，同理，$f_{x, 1}$ 满足当 $f_{y, 1}$ 满足。

  

• 如果有两个非叶节点，发现除非这个点是根，或者父节点为根且根没有其他子树，否则绝对无法满足。而如果满足上述条件，那么最开始无论是从 $x$ 出发，还是最终到达 $x$ 本质相同。

  

所以我们可以愉快的 DP 了，但是考虑父节点为根且根没有其他子树的情况不太好判断，所以任意找一个度数 $\ge 2$ 的点作为根，那么自然这个条件就无法满足，如果没有找到……这还是能一颗树？

int rt = 1;
void dfs(int x, int p) {
    dep[x] = dep[p] + 1;

    int son = 0;
    vector<int> nonleaf; 
    for (int y : G[x]) {
        if (y == p) continue;
        ++son;
        dfs(y, x);
        if (!leaf[y]) nonleaf.push_back(y);
    }

    if (son == 0)
        leaf[x] = 1, f[x][1] = 1;
    else if (nonleaf.size() == 0) 
        f[x][0] = f[x][1] = 1;
    else if (nonleaf.size() == 1) {
        int y = nonleaf[0];
        f[x][0] = f[y][1], f[x][1] = f[y][0];
    } else if (x == rt && nonleaf.size() == 2) {
        int y = nonleaf[0], z = nonleaf[1];
        if ((f[y][0] && f[z][1]) || (f[y][1] && f[z][0])) f[x][1] = true;
    }
}

这样，从根开始，依据 DP 转移的过程构造即可。

vector<int> v;
void construct(int x, int t, int p) {
    vector<int> nonleaf;
    for (int y : G[x]) {
        if (y != p && !leaf[y]) nonleaf.push_back(y);
    }

    #define pushLeaf() { for (int u : G[x]) if (u != p && leaf[u]) v.push_back(u); }
    if (nonleaf.size() == 0) {
        if (t == 0) v.push_back(x);
        for (int y : G[x]) {
            if (y != p) v.push_back(y);
        } if (t == 1) v.push_back(x);
    } else if (nonleaf.size() == 1) {
        int y = nonleaf[0];
        if (t == 0) {
            v.push_back(x);
            construct(y, 1, x);
            pushLeaf();
        } else {
            pushLeaf(); 
            construct(y, 0, x);
            v.push_back(x);
        }
    } else if (nonleaf.size() == 2) {
        int y = nonleaf[0], z = nonleaf[1];
        v.push_back(x);
        if (f[y][1] && f[z][0]) {
            construct(y, 1, x);
            pushLeaf();
            construct(z, 0, x);
        } else if (f[y][0] && f[z][1]) {
            construct(z, 1, x);
            pushLeaf();
            construct(y, 0, x);
        } else assert(nonleaf.size() == 2);
    }
}

虽然是说稍微复杂了一点，但是分讨很简单，代码依据分讨就可以直接模拟出来，十分的 naive，这比正解要更 brute force 一点（CF优良传统）。

而对于正解，先找出最长链，那么支链的深度不能超过 $1$，否则一定不合法，$O(n)$ 做即可，只是要扫很多遍而已。

D. Misha and Apples

给定 $n$ 个集合 $S_i$，第 $i$ 个集合的大小为 $k_i$，集合元素为 $1\sim m$ 的正整数。特别地，若 $k_i = 0$，则 $S_i$ 可以是正整数 $1\sim m$ 的任意可空子集，由你确定。

设 可重集 $S$，初始为空。按编号从小到大依次遍历每个集合，往 $S$ 中加入 $S_i$ 所有元素。每次加入当前集合的所有元素后，若 $S$ 包含重复元素，则清空 $S$。注意，一个集合内的元素 同时 被加入 $S$。

你需要确定 $k_i = 0$ 的 $S_i$ 具体包含哪些数，使得最终的 $|S|$ 最大。求出这个最大值。

$1\leq T, \sum n, m\leq 2\times 10 ^ 5$，$0\leq \sum k_i\leq 2\times 10 ^ 5$，$S_i$ 的元素互不相同。

考虑找到可以清空的位置 $can_i$，以及每一个 $i$ 往前最多可以保留到的位置 $late$。

每次找到最后一个冲突的位置 $max\_conflict$ 记为 $mc$，于是如果 $mc \le late$ 那么对于 $late$ 没有影响，而 $can_i$ 可行当且仅当 $(late, i]$ 之间存在一个 $k = 0$。

否则 $can_i$ 一定可行，而 $late$ 需要更新到 $mc$ 之后第一个 $can_i$ 为 $1$ 的点。

于是，就搞定了。

E. Roads in E City

这是一道交互题。

给定一张 $n$ 个点 $m$ 条边的无向连通图，无自环，但可能有重边。

图上有一些特殊边，保证任意两个结点通过特殊边连通，你希望求出所有特殊边。

初始所有边都没有被堵住。你可以进行以下三种操作：

• $-\ x$（$1\leq x\leq m$）：如果第 $x$ 条边没有被堵住，则堵住该边。
• $+\ x$（$1\leq x\leq m$）：取消堵住第 $x$ 条边。操作前第 $x$ 条边必须被堵住。
• $?\ y$（$1\leq y\leq n$）：交互库随机选择某个 $s$ 并返回能否从 $s$ 出发走没有被堵住的特殊边到 $y$。

你最多进行 $100m$ 次操作。

$2\leq n\leq 2000$，$n - 1\leq m\leq 2000$，$1\leq t\leq 1000$，$\sum n, \sum m\leq 2000$。保证图无自环且连通。

利用其随机化，以及联通的性质。

找到一个特殊的生成树，然后考虑非树边即可。

问题在于如何判断树边，断开，然后两边跑 $k$ 次，那么错误率为 $(\frac x n \frac {n - x} n)^k$，在 $k \to 20$ 的时候就趋近于 $0$ 了，可以认为完全正确。

于是就做完了。

$\downarrow 2023.09.18$

1817

A. Almost Increasing Subsequence

给定长度为 $n$ 一个序列 $a$ 以及 $q$ 次询问，每次询问给出 $l$ 和 $r$，找出序列 $a$ 在 $[l,r]$ 内最长的几乎递增子序列。

对于几乎递增的定义：如果一个序列中不存在连续的三个数 $x$，$y$，$z$，使得 $x \ge y \ge \ z$，则这个序列是几乎递增的。

也就是说每一段递减的都至多取两个。转换一下，减去连续的三个的个数，差分一下即可。

代码：https://codeforces.com/problemset/submission/1817/223787996

B. Fish Graph

定义“鱼图”为满足以下条件的无向图：

• 该图包含正好 $1$ 个环，环上有 $1$ 个特殊的结点 $u$，$u$ 除了连在环上的 $2$ 条边外还有正好 $2$ 条边，每一条边连向一个环外的结点（即，若环的大小为 $s$，整个图一共有 $s+2$ 个结点）。

现在给定一个简单无向图，问该图中是否有一个子图为“鱼图”。一个无向图的子图即为原图中删去若干个点和若干条边所形成的图。如果存在，还需要构造出其中任意一个满足要求的子图。

合法的点当且仅当 $D_x \ge 4$ 并且 $SCC_x \ge 3$，于是可以 $O(n)$ 求了。

注意我的写法中，需要回退，防止 $<><>$ 的这种图找不到环。

代码：https://codeforces.com/problemset/submission/1817/223785932

C. Similar Polynomials

给定两个次数为 $d$ 的多项式 $A, B$ 在 $0, 1, 2, \dots, d$ 处的点值对 $10^9+7$ 取模，保证 $B(x) \equiv A(x+s) \pmod {10^9+7}$。求 $s \bmod 10^9+7$。

考虑差分：

$$\begin{aligned} \Delta^{n - 1}f &= a(x + s) + b \\ \Delta^{n - 1}g &= ax + b \\ \Delta^{n}f &= \Delta^{n}g = -a \\ \end{aligned} $$

于是可以求出 $s$ 了。

还有拉格朗日插值求出系数然后求的方法，差不多。

代码：https://codeforces.com/problemset/submission/1817/223798973

D. Toy Machine

有一个长 $n$ 宽 $2$ 的矩形游戏机。保证 $n$ 是奇数。

游戏开始之前，有 $n - 2$ 个玩具放在第一排中间的 $n - 2$ 个位置中（两个角除外）。编号从左到右依次为 $1$ 到 $n - 2$。第二行为空，其最左、最右和中心位置是障碍物。你可以控制玩具机向左、向右、向上、向下，分别用字母 $\texttt L$、$\texttt R$、$\texttt U$ 和 $\texttt D$ 表示。

操控时，所有玩具将同时沿相应方向移动，碰到另一个玩具、墙壁或障碍物停止。您的目标是将第 $k$ 个玩具移动到第一行最左边。给定 $n$ 和 $k$，构造一个最多使用 $1000000$ 次操作的方案。

认为代码展示了一切：https://codeforces.com/problemset/submission/1817/223803543

E. Half-sum

有一个非负整数序列 $\{a_1,a_2,\dots,a_n\}$。

你可以从序列中取任意两个数，并将它们的平均数放回序列。

序列最后会剩两个数，请求出这两个数的差的绝对值的最大值。

因为答案将会是一个小数，所以请输出答案对 $10^9+7$ 取模的结果。

呃，推一点点式子，发现如果从断点 $x$ 到断点 $y$ 的差距为：

$$\sum_{i = x + 1}^{y} (\frac {a_i}{2^i} + \frac {a_i}{2^{n-i+1}}) - \frac {a_x}{2^x} + \frac {a_y}{2^y} + \frac {a_{x + 1}}{2^{n - x}} - \frac {a_{y + 1}}{2^{n - y}} $$

于是可以 $O(y - x + 1)$ 求解，于是发现可以分治求解。

问题在于如何维护这些加加减减的值。

有一个 trick：Trygub Number，适用于此。

于是可以 $O(n \log n)$ 求解了。

注意可能需要较快的读入：Submission #223847308 - Codeforces

然而正解，考虑 $2^i$ 在 $i \ge 30$ 时便很大了，使得 $\frac {a_i}{2^i}$ 趋近于 $0$，于是可以发现断点只会出现在前/后 $\log n$ 个不同的数上，于是常数为 $64$ 的 $O(n)$ 做法新鲜出炉！

1815

Div. 1 确实难，Virtual Contest 上只完成了两道题，想出来了三道题。

A. Ian and Array Sorting

秒切题……考虑将前 $n - 1$ 个数变成一样的一个数 $x$。显然可以完成。

然而考虑此时最后一个数。如果 $\ge x$，那么是 $\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}$，如果 $\lt x$，要分类讨论：

• 如果前面有奇数个，是 $\texttt{\colorbox{#E74C3C}{\textcolor{white}{WA}}}$。

• 反之，则是 $\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}$。

提交：Submission #211291004 - Codeforces

B. Sum Graph

傻逼交互。

好呀好呀，傻逼交互体。想出来了思路，但是就是没有写出来。

考虑 + 点 $n + 1, n + 2$。那么整个图会形成一条链。

static int perm[N]; int l = 1, r = n;
for (int i = 1; i <= n; ++i) {
    perm[i] = (i & 1) ? l++ : r--;
}

于是我们可以在 $n - 1$ 次以内找到链的一端，然后就可以再来 $n - 1$ 次找到可能的排列。

由于我们可能是找到的两端，所以有两种排列方法。

输出即可。

提交：Submission #211296415 - Codeforces

进阶：参考 https://codeforces.com/blog/entry/114847?#comment-1021812 以及 Editorial of Codeforces Round #865 - Codeforces，可以把次数减少到 $n + \lfloor \frac n2 \rfloor + 2$ 次询问。

C. Between

构造好题。

考虑包含可以形成依赖。

于是可以形成一张图。

我们从 1 开始 BFS 对其分层，可以发现，第 $i$ 层最多可以放 $i$ 个（包含依赖多套一个）。

那么考虑如何构造合法方案。

我的方法是每一次，按照 BFS 逆序遍历很多遍，每一次遍历到，如果还有没放的则放一个，否则略过。（好像官方题解就是这样？看不懂）

考虑正确性：按照逆序遍历保证出现次数少的在中间，保证不同层之间的依赖关系；每次放一个保证出现次数相同的交替出现，这样就保证了层内的依赖关系无论如何一定满足（互相依赖也没关系）。

提交：Submission #211298131 - Codeforces

D. XOR Counting

打表好题。

在 $m = 1$ 的时候答案就是 $n$。

在 $m \gt 3$ 的时候小小打表，可以发现答案为 $\lceil \frac n2 \rceil \times (\lfloor \frac n2 \rfloor + 1)$。

证明：在 $m \gt 3$ 的时候，$[x, \frac {n-x}2, \frac {n-x}2, 0, 0, \dots]$ 可以恰好凑出 $x$，所以所有与 $n$ 奇偶性相同的 $x$（此时 $n-x$ 为偶数，$\frac {n-x}2$ 为整数）都可以被凑出。

然后我们发现，加法和异或得到的奇偶性是一样的，并且有 $a \otimes b \le a + b$，意味着我们只能凑 $\le n$ 并且与 $n$ 奇偶性相同的数。

综合两条，我们便可以得出，所有可能凑出的数就是 $\le n$ 且与 $n$ 奇偶性相同的数。

推一下公式就是上面的了。

于是问题就只剩下了 $m = 2$ 的时候。

我们考虑一个 DP，我们记 $f(n)$ 表示所有可能的异或和的和，$g(n)$ 表示可能的个数。然后稍微分类讨论一下：

• 如果 $n$ 是奇数，我们不妨假设 $n = a_1 + a_2$，其中 $a_1$ 为偶数，$a_2$ 为奇数。设 $a_1' = \frac {a_1}2, a_2' = \frac {a_2 - 1}2$。我们可以看出：$a_1' + a_2' = \frac {n-1}2$ 以及 $a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')+1$。此时个数不会变，而和变为原本的两倍再加上个数。也就是 $g(n) = g(\frac {n-1}2)$ 以及 $f(n) = 2f(\frac {n-1}2) + g(\frac {n-1}2)$。

• 如果 $n$ 是偶数，那么我们又要分两类讨论：

  • 设 $n = a_1 + a_2$，其中两者都是偶数，那么类似的，$a_1' + a_2' = \frac n2$，$a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')$。

  • 如果都是奇数，有 $a_1' + a_2' = \frac n2 - 1$ 以及 $a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')$。 

  • 因此，我们可以知道 $f(n) = 2 \times f(\frac n2) + 2 \times f(\frac n2 - 1)$，以及 $g(n) = g(\frac n2) + g(\frac n2 - 1)$。

FAKE: 于是我们可以得出递推复杂度 $T(n) = T(\frac n2) + 1$，得出为 $O(\log n)$。

依据SMB，复杂度似乎不是这样的，但是题解是这么给的，或许是有一些神秘的分析，或者是加了记忆化，所以复杂度是这样的。

其实完全可以用记忆化……快一点吧。

提交：https://codeforces.com/contest/1815/submission/211297560

E. Bosco and Particle

性质好题。

性质：

1. 循环多次 $=$ 循环一次

2. 设 $a_i$ 表示实际上从上面进入这个序列的次数，$b_i$ 表示实际上向下面出去这个序列的次数。我们把第 $i$ 个序列单独提出来，类似的定义 $a_i'$ 和 $b_i'$。可以发现，$\exists k \implies a_i = ka_i', b_i = kb_i'$，也就是有 $\frac {a_i}{b_i} = \frac {a_i'}{b_i'}$

3. 有 $a_i = b_{i-1}$。

4. 令 $f_i = a_{i + 1}$，$f_0 = a_1$，于是有 $f_k = \prod_{i = 1}^k \frac {b_i}{a_i} f_0$。

5. 需要保证 $\forall k$，$ f_k$ 为整数。

于是就可以写出来啦！！！（不是

提交：Submission #211323975 - Codeforces

竟然比 C++ 快，不可思议

1868

A. 2D Traveling

该题共有 $t$ 组数据，对于每一组数据，给定一个共有 $n$ 个节点的图，其中有 $k$ 个关键点（两个关键点之间移动花费为0）。给出 $n$ 个点的坐标 $(x_i,y_i)$ ,求从 $a$ 到 $b$ 两点之间的最小移动花费。

除关键点以外，两点之间的移动花费为曼哈顿距离。

策略要么是 $a$ 直接到 $b$，要么是 $a$ 先到最近的关键点，跳到 $b$ 最近的关键点。

直接做即可，代码：https://codeforces.com/contest/1869/submission/223695140

B1/2. Candy Party

有 $n$ 个人，第 $i$ 个人有 $a_i$ 颗糖，在派对上，每个人 会且仅会做下面的事情恰好一次 ：

• 选一个正整数 $p\ (\ 1 \leq p \leq n\ )$ 和一个非负整数 $x$ ，然后把 $2^x$ 颗糖给第 $p$ 个人。注意任意时刻一个人手上的糖不能变成负数，并且一个人不能把糖给自己。

你需要回答能否在上述操作后让每个人手中的糖果数量相同。

注意本题和 Hard Version 不同的是本题中每个人必须从他人处接受恰好一次糖果，给出恰好一次糖果。

也就是每一个人要么使用 $2^x - 2^y$，要么使用 $2^x$，要么使用 $2^{2x} - 2^x$。分开考虑来 DP 即可。

C. Travel Plan

给定一颗 $n$ 个节点的完全二叉树，每个点有权值 $a_i \in [1,m]$，定义从 $i$ 到 $j$ 的路径的权值 $s_{i,j}$ 为路径上的最大点权。

求所有树（$m^n$ 种点权）的 $\sum_{i=1}^n \sum_{j=i}^n s_{i,j}$ 的和，模 $998244353$。

很显然，我们可以分别求出每种长度路径对答案的贡献，然后再在树上统计各个长度路径的个数，最后把贡献加起来即为答案。

D. Flower-like Pseudotree

给你一个基环树，我们称一个基环树是像花的当且仅当删去基环树中的环后，剩余的所有树高度一致，请你构造一个像花的基环树，满足树中所有点的度数为 $d_i$，

大力分讨即可。

1863

A. Channel

Link

没什么好说的，模拟即可。

代码：https://codeforces.com/problemset/submission/1863/225013381

B. Split Sort

给定一个 $1 \sim n$ 的排列 $q$，你可以多次进行以下操作：

• 新建一个初始为空的序列 $q$；
• 选择一个整数 $x$（$2 \leq x \leq n$）；
• 按照在 $p$ 中出现的顺序将所有小于 $x$ 的数添加到序列 $q$ 末尾。
• 按照在 $p$ 中出现的顺序将所有大于等于 $x$ 的数添加到序列 $q$ 末尾。
• 用序列 $q$ 替代排列 $p$。

你需要找到使 $\forall i \in [1,n]$，$p_{i} = i$ 的最小操作次数。

本题有多组测试数据，$1 \leq T \leq 10^{3}$，$1 \leq n,\sum n \leq 10^{5}$。

记 $i$ 出现的位置为 $p_i$，则答案为 $\sum_{i = 2}^n [p_i < p_{i - 1}]$

代码：Submission #225039544 - Codeforces

C. MEX Repetition

给定值域在 $[0, n]$ 的一个序列，$p_i$ 互不相同，定义一次操作为 $i = 1 \to n, p_i = \mathrm{mex}(P)$，求 $k \le 10^9$ 后的序列是什么样子的。

将初始的 $\mathrm{mex}$ 放在序列开头，则一次操作相当于 $i = 1 \to n, \mathrm{swap}(p_0, p_i)$，结果是加入了 $\mathrm{mex}$ 的序列向右循环了一次。

所以最后就是循环 $k$ 次，去掉第一个数即可。

代码：https://codeforces.com/problemset/submission/1863/225014759

D. Two-Colored Dominoes

有一个 $n \times m$ 的棋盘，上面铺着一些 $1 \times 2$ 的多米诺骨牌（横竖均有可能），骨牌之间没有重叠。

你需要找到一种染色方案满足以下条件：

• 每个多米诺骨牌一端被染白，另一端被染黑。其他没有骨牌的格子不染色。
• 对于棋盘的每一行，被染黑的格子数等于被染白的格子数。
• 对于棋盘的每一列，被染黑的格子数等于被染白的格子数。

请输出任意一种染色方案，如果无解，输出 $-1$。

本题有多组测试数据，$1 \leq T \leq 10^{4}$，$2 \leq n,m \leq 500$，$\sum (n \times m) \leq 2.5 \times 10^{5}$。

发现横竖之间没有影响，所以分开考虑。

考虑只有竖着，那么横向黑白染色，这无法影响道下一行，所以忽略。

纵向类似即可。

代码：https://codeforces.com/problemset/submission/1863/225041894

E. Speedrun

你在玩一个游戏，要完成 $n$ 个任务。其中对于每个任务 $i$，它只能在某一天的第 $h_i$ 时刻完成。游戏每天有 $k$ 个小时，分别编号为 $0,1,...k-1$。

给出 $m$ 对任务间的依赖关系，$(a_i,b_i)$ 表示 $a_i$ 必须比 $b_i$ 先完成。保证依赖关系不形成环。

完成任务不需要时间，也就是说可以在同一天的同一时刻先后完成多个任务。

求完成所有任务所需的最短时间。这里的时间定义为：完成最后一个任务的时刻 与 开始第一个任务的时刻 之差。

多组数据，$T\le 10^5$，$\sum n,m\le 2\times 10^5$，$k\le 10^9$。

最优的情况是延迟了一部分拓扑序第一的点，而且这一部分一定是前缀。

所以扫一次前缀，一一延迟更新当前答案，然后更新总答案。

每一个点至多更新一次，所以这部分 $O(n)$。

代码：https://codeforces.com/problemset/submission/1863/225021336

F. Divide, XOR, and Conquer

有一个长为 $n$ 的数组 $a_1, a_2, \cdots, a_n$。

在每次操作中，你可以把数组分成两段，留下一段，扔掉另一段，要求前者的异或和不小于后者的。重复操作，直到只剩下一个数为止。

对于每个 $i$，问最后剩下来的可不可能是第 $i$ 个数。

有 $t$ 组数据。$1 \le t \le 10\ 000$，$1 \le n \le 10\ 000$，$1 \le a_i \le 2^{60}$，$\sum n \le 10\ 000$。

有一个显然的 $O(n^3)$ 做法。

考虑一个区间 $[l, r]$ 什么时候可以被转移过来，由于异或，从二进制入手。

假定从 $[l, k]$ 转移过来，其区间异或和为 $x$，$[l, r]$ 区间异或和为 $y$。

如果 $x$ 的第 $k$ 位为 $0$，那么显然两边这一位都是相等的。如果为 $1$，那么有一边会大一点，下面的位随意了。

所以可以有条件 $y \& \mathrm{highbit}(x) \ne 0$ 则可以转移。

于是一个一个长度递减做下去即可。

代码：https://codeforces.com/problemset/submission/1863/225050040

G. Swaps

给定长度为 $n$ 的序列 $a$，每次操作可以选定一个 $i$，并 $\operatorname{swap}(a_i,a_{a_i})$。求能通过某种操作顺序得到的不同序列数。

$n\le 10^6$。

简洁的题面，深邃的思想。

首先，一个经典的套路是：

对于序列中涉及到对于 $a_i$​​ 和 $a_{a_i}$​ 进行操作的问题，一般可以考虑建立 $(i,a_i​)$ 的内向基环树或者 $(a_i​,i)$ 的外向基环树转化为图论问题。

-- from weakpyt

一次交换相当于使得一个点自环，儿子连向父亲。

于是转换为对于一个点，儿子可以断一条边，并且至多段一条边的模型。

所以如果只是一棵树的话，答案就是 $\prod (d_x + 1)$。

然而有环，发现环上所有边的断掉的情况不存在。

再发现环上留一条边不断，但是每一个点都断了一条边/或者不变的情况都是一样的，这部分显然是 $\sum (d_x - 1 + 1)$ 的。

所以减去重复的，只保留一个，答案为：

$$\prod_{cycles}(\prod_{x \in cycle} (d_x + 1) - 1 - (-1 + \sum d_x)) \prod_{x \not \in cycle} (d_x + 1) $$

化简一下：

$$\prod_{cycles}(\prod_{x \in cycle} (d_x + 1)- \sum d_x) \prod_{x \not \in cycle} (d_x + 1) $$

这样就好求了。

代码：https://codeforces.com/problemset/submission/1863/225037149

H. Goldberg Machine

给定一棵树，每个节点要么没有儿子，要么有两个儿子，每个叶子节点有一个权值。

多次修改某个叶子节点的权值，维护递推式子：$f_x = 2 \max(f_y, f_z) - (f_y \ne f_z)$。

令 $t_x = f_x - 1$，则递推式子转换为 $t_x = 2 \max(t_y, t_z) + [t_y = y_z]$。

记 $x$ 的深度为 $dep_x$，则可以令叶子 $g_x = 2^{dep_x} f_x$，则递推式子为 $g_x = \max(g_y, g_z) + 2^{dep_x}[g_y = g_z]$。

有一个结论是 $g_x$ 的二进制中 $1$ 的个数是 $\log A + \log n$ 级别的。

考虑暴力合并。

假定 $x, y$ 的 $g$ 相等，则可以在 $z = \mathrm{LCA}(x, y)$ 处贡献 $2^{dep_z}$。

于是可以利用 vector 字典序暴力找相同的，然后合并即可。

最后会得到很多个答案，取最大的即可。

为什么取最大的正确性没问题？考虑如果 $x$ 在和 $y$ 之前与某一个 $u$ 合并了，那么合并的位置一定在 $z$ 下面，也就是贡献 $2^{dep}$ 一定大于 $2^{dep_x}$，使得最终的答案大于错误的答案，所以如此是没有问题的。

由于当日晚上呕吐，身体不适，所以没有写本题。然而代码实际上是好写的，不过多赘述。

1753

成功因为虚拟机炸了，重新写一遍此文。

都是没有保存的错。

A. Make Nonzero Sum

由于 Note that it is not required to minimize the number of segments in the partition.。考虑每一段最小化……

可以发现，每一段都可以划分为长度为 1 或 2 的段。于是考虑影响。

只有长度为 2 的段会改变正负，不妨令 $C_+, C_-$ 分别表示 1 和 -1 的个数，并假定 1 更多。

不难发现，只需要 $\frac {|C_+ - C_-|}2$ 个长度为 2 的即可。

如果不是整数，那么直接判不可以即可。

由于有影响，考虑 DP。

设 $f_i$ 表示考虑前 $i$ 个数，最多能够放多少个长度为 2 的。

于是有

$$f_i = \max \begin{cases} f_{i - 1} \\ f_{i - 2} + 1 &, a_i = 1 \end{cases} $$

考虑在 DP 变化的地方放置长度为 2 的即可。

B. Factorial Divisibility

当时脑子抽了，用了两种合并的方法。

详见：https://codeforces.com/contest/1753/submission/211561532

但是实际上只需要通过 $x! = x \times (x -1)!$ 合成即可（2048……

C. Wish I Knew How to Sort

假定有 $C_0$ 个 $0$，并且在前 $C_0$ 个数中有 $k$ 个 1。

那么考虑此时一个有效的操作，即是在前 $C_0$ 中选择到了一个 $1$，在后面中选择了一个 $0$。

有效的概率为

$$P_k = \cfrac {k^2}{n \choose 2} $$

于是考虑状态转移，设 $f_k$ 表示从前 $C_0$ 个数中有 $k$ 个 $1$ 的状态转移到 $0$ 个 $1$ 的期望步数。

根据 markov 中的期望线性方程求解的方法，有

$$f_k = 1 + (1 - P_k)f_k + P_k f_{k - 1} $$

稍微魔改一下，就变成了：

$$f_k = \frac {1}{P_k} + f_{k - 1} $$

于是小小递推即可。

然而我当时是反着推的，无所谓，一样的：Submission #211560140 - Codeforces

D. The Beach

转换问题：等价于将两个 . 移动到一起的最小代价。

显然可以发现，一个障碍最多移动一次。

借用大佬的图：

于是我们可以考虑如此建图。跑一个最短路即可。

提交：Submission #211566195 - Codeforces

E. N Machines

非常恶心，虽然不是顶级难度。

最优的策略一定是把乘法向后移，把加法向前移。

思考 It's guaranteed that the current value of the resulting product does not exceed 2x10^9. 的意义。

发现，除去 $\times 1$，最多只会有 $\log C$ 个乘法。

于是考虑枚举其子集，为 $2^{\log C}$。所以需要优化。

有一个简单而优雅的剪枝：如果两个数相等，那么一定是选择最前面的。

由于 $12! = 6227020800 \gt 2 \times 10^9$，所以其实最多只会有 $O(2^{12})$ 种状态。

那么在钦定了向后移动的乘法后，我们需要找到前 $rest$ 个移动到前面贡献最大的加法。

考虑二分移动到前面的贡献 $\Delta$，在每一段再二分数量。

考虑如何计算每一个加法的 $\Delta$ ？考虑加法移动前，其贡献为 $x \times suf_x$，移动后的贡献为 $x \times pre_x \times suf_x$。

其中 $suf_x$ 和 $pre_x$ 是指乘法移动后，$x$ 前面的乘法前缀积和后面的乘法后缀积。

于是 $\Delta x = x \times (pre_x - 1) \times suf_x$。

NOTICE：

• 二分 $\Delta$ 时找到最大的 $cnt > rest$ 的那个 $\Delta$，由于多算了 $cnt- rest$ 个，并且这些数的贡献一定是 $\Delta$，所以再减去 $(cnt - rest) \times \Delta$ 即可。

• $\Delta$ 可能很大很大，所以上界大一点（我用的倍增，所以直接是从 $2^{60}$ 开始向下……虽然没必要）

提交：Submission #211609810 - Codeforces

F. Minecraft Series

首先固定一个正方形，考虑贡献：将数分为正数与负数，分别计算 $mex_p$ 与 $mex_n$。

正的为 positive，负的为 negative。

于是贡献为 $mex_p + mex_n - 1$。

由于 $mex$ 的单调性，发现包括合法正方形的正方形一定合法，所以考虑双指针维护所在最小合法正方形的。

注意，是在每一条对角线上来一发双指针，这样才能保证复杂度。

然后，然后就搞定了。

可以优化的是，$mex$ 可以利用分块优化复杂度。

于是你可以得到一个复杂度为：

$$O(nm \cdot \min\{n, m\} + n m \sqrt k) $$

的优雅 brute force……

提交：https://codeforces.com/contest/1753/submission/211685792

然而……不断的 TLE 让我怀疑人生，最后发现……

参考：讨论

1718

A. Burenka and Traditions (hard version)

有 $T$ 组数据，对于每一组数据，你有一个长度为 $n$ 的数组 $a$，每一次操作可以选择一段区间 $[l,r]$，花费 $\left \lceil \dfrac{r-l+1}{2} \right \rceil$ 秒使区间内的数都异或 $x$，问最少需要几秒才能把数组中所有的元素都变成零。

首先不难发现有一个非常简单的上界 $n$，也就是每两个两个的变成 $0$ 即可，或者换成一个一个向后推的过程。

然而如果存在一个区间本身异或和为 $0$，那么发现左端点是没有必要推的，这使得操作次数 $-1$。发现这优化十分显然，于是利用 set 维护最小的段即可。

代码：Easy: https://codeforces.com/problemset/submission/1718/229358204, Hard: https://codeforces.com/problemset/submission/1718/229358185

B. Fibonacci Strings

给你一个数列 $\{c_k\}$，可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作：

• 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。

• 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。

问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？

呃呃，原题不是这样的，但是既然这么翻译了，那么贪心的模拟一下即可。

代码：https://codeforces.com/problemset/submission/1718/229357931

C. Tonya and Burenka-179

给定一个长度为 $n$ 的序列，要求求出一个权值最大的对 $(p, k)$，其中 $0 \le p, k \lt n$。

定义一个对 $(p, k)$ 的权值为 $\sum_{i = 1}^{n} A_{p + k i \bmod n}$。

先考虑最朴素的做法 $O(n^2)$，发现，考虑优化其过程，发现可以类似于分治，例如 $(p, k)$ 可以由 $(p, 2k)$ 和 $(p + k, 2k)$ 合并而来。

但是发现 $(p, k)$ 一定不必 $max((p, 2k), (p + k, 2k))$ 更优，所以此时 $k$ 是不必要的。

于是发现 $k$ 是最优的当且仅当 $\frac nk$ 为质数，这只有 $6$ 个，每一个用一个 set 维护即可，这是 $O(6 n \log n)$ 的。

代码：https://codeforces.com/problemset/submission/1718/229362201

D. Permutation for Burenka

给定一个排列 $p$ 和有 $k$ 个空位的序列 $a$，已经确定了可以 $k - 1$ 个数，每次询问给定一个数，要求是否可以将这 $k$ 个数填入 $a$ 中使得 $\forall i < j, \arg \max p_{[i, j]} = \arg \max a_{[i, j]}$

发现这个限制可以转化为两者的笛卡尔树同构，发现排列的笛卡尔树是确定的，先构出来，然后考虑 $a$。

发现每一个空位都可以填的数是一个区间，而剩下一个数合法也一定是一个区间，于是考虑如何求上下界。

首先将每一个位置的上下界求出来，考虑一个十分经典的贪心来求它，按照区间右端点从大到小排序，尽量选择大的来满足它，那么到第一个不可以填的区间的时候，就意味着剩下的一个数必须大于这个区间的左端点了，于是可以求出下界了。

同理，按照左端点从小到大排序，可以求出其上界。

不过需要注意，如果遇到了两个没有办法满足的区间的时候，无论填什么都不可以了，此时所有询问回答皆为 NO。

代码：https://codeforces.com/problemset/submission/1718/229374552

E. Impressionism

Burenka 有两张图片 $a$ 和 $b$ ，它们的大小可以表示为 $n \times m$ 的像素组合。每幅画的每个像素都有一个颜色——表示为一个从 $0$ 到 $2 \times 10^5$ 的数字，并且在两幅画的每一行或每一列中都没有重复的颜色，除了颜色 $0$ 。

Burenka 想把图片 $a$ 变成图片 $b$。为了实现她的目标，Burenka 可以执行 $2$ 操作之一：交换 $a$ 的任意两行或其任意两列。现在需要你来告诉 Burenka 该如何操作，或者说明其不可能完成。

模拟 $\mathrm{Pity Problem}$，利用二分图一一匹配即可。

F. Burenka, an Array and Queries

每次询问一个区间，求 $\prod a_i$ 与 $1 \sim C$ 中互质的数的个数。

有根号分治，或者乱搞。

但是官方题解所说：The only one hint to this problem is don't try to solve, it's not worth it.

1710

B. Rain

给定一个 $n$ ，这 $n$ 天会降雨，每一个降雨天有一个 $x_i$ 和一个 $p_i$ ，表示以 $x_i$ 为中心，降雨量向左右两边递减，即对于所有的数轴上的点 $x$ ,其降雨量都会增加 $max(0,p_i−∣x_i−x∣)$

现在你可以消除一天的降雨，问消除第 $i$ 天的降雨是否可以使得没有任何地方的降雨大于 $m$。

考虑整个图长什么样子，发现峰值（很多个）一定是某个 $x_i$ 上。

于是求出每一个 $x_i$ 对应的降雨 $h_i$，这可以通过二分和差分很容易的求出（考虑每一次增加的是一个一次函数，这可以通过 $k, b$ 简单的维护）

于是考虑对于删除一个后 $m$ 的限制。

如果 $h_i \le m$，自然不需要关注，删除一个 $k$ 之后 $h_i \to h_i - \max(0, p_k - |x_k - x_i|)$。

我们需要 $h_i - \max(0, p_k - |x_k - x_i|) \le m$ 也就是 $h - (p_k - |x_k - x_i|) \le m$，考虑原本 $h_i > m$，如果后者不满足，那么必定不满足。

于是就是 $h_i - p_k \le m + |x_k - x_i|$，考虑绝对值又是 $\max(x_k - x_i, x_i - x_k)$，于是两边同时都需要满足，也就是：

$$\begin{cases} h_i + x_i \le m + x_k + p_k \\ h_i - x_i \le m - x_k + p_k \end{cases} $$

分别记录 $h_i + x_i$ 和 $h_i - x_i$ 的最大值即可判断 $k$ 删除后是否满足条件。

代码（我在乱搞……所以代码有些抽象）：https://codeforces.com/problemset/submission/1710/229413132

C. XOR Triangle

给你一个数 $n$，问：有多少对数 $0\leq a,b,c \leq n$ 满足 $a \oplus b,b \oplus c,a \oplus c$ 。三个数字构成了一个非退化三角形，也就是两条短边之和大于第三边的长度。$\oplus$ 表示二进制下的异或操作。

首先，很难发现对于所有数位，如果 $a \oplus b + b \oplus c > a \oplus c$，那么就满足 $x \oplus y + y \oplus z > x \oplus z$。其余两个限制同理。

于是考虑数位 DP，压位判断是否满足三个条件即可。

代码：https://codeforces.com/contest/1710/submission/229415904

D. Recover the Tree

你需要根据题目给出的信息构造出一棵树，满足如下条件：

1. 树的节点个数为 $n$。
2. 对于每个区间 $[l,r]$ 给出是或不是连通块。

数据保证有解，$n\leqslant 2000$。

首先满足小的区间是最优的，考虑如何满足大的区间。

考虑合并 $i, j$，那么此时的联通块大概是这样的：

按照上面的连边即可，注意是连到 $i$ 和 $j$，而不是 $i, j$ 所在连通块的某一个点，中间的块随意，利用并查集维护即可。

代码：https://codeforces.com/contest/1710/submission/229423482

E. Two Arrays

现有两个整数数组 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_m$。

Alice 和 Bob 将要玩一个游戏，Alice 先手，然后他们轮流进行操作。

他们在一个 $n\times m$ 的网格上进行游戏（网格有 $n$ 排 $m$ 列）。刚开始，有一个棋子放在网格的一排一列上。

在 Alice 或 Bob 轮次中，玩家可以选择以下两个动作中的一个进行操作：

1. 将棋子移动到一个不同的格子上，该格子必须和棋子的原位置在同排或者同列上。玩家不能将棋子移动到已经被访问过 $1000$ 次的格子上（也就是说，在游戏过程中，棋子最多可以在某个格子停留 $1000$ 次）。请注意，我们规定起始单元格在开始时被视作访问过一次。
2. 以 $a_r + b_c$ 的得分立刻结束游戏，$(r, c)$ 表示棋子当前所在的单元格（也就是说，棋子在第 $r$ 排第 $c$ 列上）。

Bob 想要最大化自己的得分，Alice 则想要最小化自己的得分。如果他们都以最佳方式玩这个游戏，则最终的得分是多少？

其实发现 $1000$ 次和 $1$ 次没有区别，直接忽略。

首先，我们知道博弈双方足够聪明，可以直接知道比赛结果 $res$，那么意味着 Bob 只能走大于 $res$ 的地方，而 Alice 只能走小于等于 $res$ 的地方。

于是可以得到一张二分图，这让我们想到经典的结论：Alice 赢的充要条件是二分图的最大匹配必须包含起点 $S$。

但是边数是 $O(nm)$ 的，非常难受，考虑转化思路，找二分图最大独立集，这要求每行每列都只有一边出现，我们给每个行列涂颜色。那么一个方格可以取当且仅当方格的颜色和行列所染颜色都一样。

于是对于整个图（$a, b$）排个序，于是发现黑白大概就是如图：

枚举这个点即可，但是直接枚举是不可以接受的，这是 $O(nm)$，但是考虑到这必定是一个凸函数，所以可以单调性优化，可以做到 $O(n + m)$ 找。

于是加上二分的复杂度为 $O(n \log n)$。

1707

A. Doremy's IQ

哆来咪·苏伊特参加了 $n$ 场比赛。 比赛 $i$ 只能在第 $i$ 天进行。比赛 $i$ 的难度为 $a_i$。最初，哆来咪的 IQ 为 $q$ 。 在第 $i$ 天，哆来咪将选择是否参加比赛 i。只有当她当前的 IQ 大于 $0$ 时，她才能参加比赛。

如果哆来咪选择在第 $i$ 天参加比赛 $i$，则会发生以下情况：

• 如果 $a_i>q$，哆来咪会觉得自己不够聪明，所以 $q$ 将会减 $1$；
• 否则，什么都不会改变。

如果她选择不参加比赛，一切都不会改变。哆来咪想参加尽可能多的比赛。请给哆来咪一个解决方案。

• 简单二分，前面部分只参加 $\le q$ 的比赛，后面部分经量参加，看是否可是使得 $q = 0$。
• 或者从后向前考虑，可以 $O(n)$。

B. Difference Array

你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。

显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。

首先有个不难发现的是相同的数，只需要有一个贡献即可。

然后发现会有 $O(\sqrt S)$ 个本质不同的数，也就是说，至多需要删 $O(\sqrt S)$ 次，每次删一个的代价是 $O(n \log n)$，于是你会发现这跑的飞快。

因为这复杂度是 $O(S \log n)$ 而不是根号的。考虑利用构造证明，如果需要每一次都只减少 $1$ 个值，而不产生相同的值，那么最优秀的显然是 $f(x) = 2^x$，因为存在 $\Delta f(x) = f(x - 1)$，于是这种东西至多是 $O(\log S)$ 个的，所以复杂度不会高于 $O(n \log S)$，然而存在神秘证明，操作次数是 $O(\frac S n)$ 的，所以复杂度是 $O(S \log n)$ 的，这看题解即可。

C. DFS Trees

有一图有$n$个点$m$条边。第$i$条边的权值是$i$
现在有一个错误的最小生成树算法（就是有bug）

vis := an array of length n
s := a set of edges

function dfs(u):
    vis[u] := true
    iterate through each edge (u, v) in the order from smallest to largest edge weight
        if vis[v] = false
            add edge (u, v) into the set (s)
            dfs(v)

function findMST(u):
    reset all elements of (vis) to false
    reset the edge set (s) to empty
    dfs(u)
    return the edge set (s)

每次调用$findMST(i)$时，会返回这个图的最小生成树，你要判定那些是正确的最小生成树。

首先，最小生成树是唯一的，于是整张图会变成一棵树加一些边。

在 DFS Tree 里面，只有返祖边，我们考虑每一天非树边在什么时候满足为反祖边。

如果 $(x, y)$ 不为祖先关系，那么是各自子树内即可。树上差分即可。

D. Partial Virtual Trees

给定 $n$ 个点的树以及质数 $p$，对每个 $k=1,2,\cdots,n-1$ 计算满足下述条件的点集序列 $\{S_i\}_{i=0}^k$ 数量 $\bmod\ p$：

• $\{1\}=S_k\subsetneq S_{k-1}\subsetneq\cdots\subsetneq S_0=\{1,2,\cdots,n\}$；
• 对每个 $S_i$ 以及 $u,v\in S_i$，都有 $\text{LCA}(u,v)\in S_i$。

其中 $\text{LCA}(u,v)$ 表示以 $1$ 为根时 $u$ 与 $v$ 的最近公共祖先。

真子集很恼火，于是利用容斥搞掉。

逆着删元素，于是 $f_{x, i}$ 表示 $x$ 在 $i$ 时被删除，初始全部点亮。

于是儿子必须全部消失或只剩下一个，$f_{x, i}$ 才能消失，转移参考 https://www.luogu.com.cn/blog/_post/454338 即可。

1685

A. Circular Local MiniMax

检查是否存在对于 $a_1, a_2, \cdots, a_n$ 的重新排列，使得 $i$ 从 $1$ 到 $n$ 中至少有一个以下条件成立。

• $a_{i-1} < a_i > a_{i+1}$
• $a_{i-1} > a_i < a_{i+1}$

首先奇数长度一定不可以，于是只用考虑偶数。

此时只需要分成两个部分，交错放置，然后判断即可。

B. Linguistics

Alina 发现了一种只由 $\text{A, B, AB, BA}$ 四种单词组成的语言，这种语言不含有空格，书写句子时只需要将单词直接连接起来即可。

她很好奇是否可以用 $a$ 个 $\text{A}$，$b$ 个 $\text{B}$，$c$ 个 $\text{AB}$，$d$ 个 $\text{BA}$ 拼接形成句子 $s$。

换句话说，是否可以用 $a+b+c+d$ 个单词以某种顺序拼接出句子 $s$，这 $a+b+c+d$ 个单词都得被用到，他们的顺序可以由你决定。

很抽象的贪心。考虑先把形如 $XYXYX...$ 的段都提出来，按照长度排个序。

首先如果长度为偶数，那么优先满足 $XY$ 的。在满足了所有的偶数之后，我们继续考虑奇数的，此时发现，两者可以满足的数量相加是恒定的，所以可以任意满足。

最后剩下了一点偶数的，那么贪心的放即可。

C. Bring Balance

Alina 有一个长度为 $2n$ 的括号序列 $s$，她想把这个括号序列变成一个合法的括号序列。每一次操作可以 reverse $s$ 的任意子串，求最小操作次数。

经典的画折线，发现至多需要两次，也就是翻转至高点左右两侧。

考虑什么时候只用翻转一次，找到至少翻转的那个区间 $[l, r]$，找到左右两部分最高的点 $L, R$，如果 $\forall i \in [l, r], h_i \le h_L + h_R$，那么可以只用一次，正确性显然。

D. Permutation Weight

给定一个 $1\sim n$ 的排列 $p$， $n \le 200$
对于一个 $1\sim n$ 的排列 $q$，定义其权值为：

$$ 找出 **任意一个** 权值最小化的 $1\sim n$ 的排列 $q$。 Hard Version 是找到字典序最小的。 先考虑简单版的怎么做。 设 $f = p^{-1}$，先不考虑 $q$ 是否是一个排列，那么存在 $q_i = p_{q_{i + 1}}$，两边同时套上 $f$ 得到 $f_{q_i} = q_{i + 1}$。 于是，可以钦定 $q_1 = 1$，于是可以推出 $q$ 的样子。 然而发现 $q$ 存在多个环，推不出来，所以需要交换某些东西，使得只存在一个环。为了达到下界，我们只能交换相邻的 $f_i, f_{i + 1}$，保证损失最小。 利用并查集维护可以做到 $O(n)$。 然而对于字典序最小，看到数据范围容易想到，每位钦定的选择某一个值，判断这个前缀是否可行，可以做到 $O(n^3)$。 我们重新看简单版的过程，我们有很多 $q_i \to f_{q_{i + 1}}$，考虑得到了一些 $(i, f_i)$，$q_i$ 则规定了其顺序，而答案则是 $\sum (q_i, f_{q_i})[0] - (q_{i - 1}, f_{q_{i - 1}})[1]$。 于是我们根据 $f_i$ 可以划分出一些环，发现在这些环内跳是没有代价的，这十分优秀。 现在转而考虑 $f_{q_{i - 1}} \to q_i$ 的这条边，发现需要经量使得两者接近，并且所有连完之后满足： - 所有边只形成一个环。 - 使得所有 $f_i$ 划分出来的环联通。 而为了使得答案最优秀，我们需要： - 每个边不会重复合并划分出来的环。 - $f_{q_{i - 1}} \to q_i$ 形成的图中，每个环编号都是连续的，且可以被拆分为递增和递减的两个段。 此时我们需要判断一个前缀是否合法/优秀，于是就可以采用如下方法： - 不存在两条单增链相交，不存在两条单减链相交（自环同时算作单增链及单减链）。 - 不存在未连边的点同时被单增链及单减链覆盖。 - 不存在被覆盖的某边 $(i, i + 1)$ 在同一个划分的环内。 - 剩下的所有作为边界的 $(i, i + 1)$ 可以使得所有颜色联通。 这可以利用差分 + 并查集每次 $O(n)$ 的维护。 于是总复杂度为 $O(n^3)$。 ## GYM 103495 > 这里挑选部分值得一谈的题。 ### B. Among Us 给出一张带边权的无向图，边权可被视为长度。最开始有 $2$ 个内鬼和至多 $8$ 个船员，内鬼起始位置给出，内鬼只能沿着边走。内鬼知道一系列形如“船员 $p$ 会在第 $t$ 秒出现在顶点 $x$ 的信息。若内鬼与船员在同一时间和同一地点出现，则 内鬼可以把船员给砍了。内鬼只能在前面给出的时间/地点砍人。你需要为 $2$ 个内鬼分别规划路径使得它们能够尽快将所有船员都给砍了。若方案存在则输出最短时间，否则输出 $−1$。 核心：状压，最短路，DP。 首先利用状压将两个内鬼分开，于是问题简化为对于一个人。 不难想出一个状态，设 $f_{x, t, S}$ 表示是否能够在杀了 $S$ 中的人后在 $t$ 时到 $x$。 如果固定 $x, S$，发现对于一个后缀 $t$ 都生效，那么可以将 $t$ 作为值，于是状态为 $f_{x, S}$ 表示杀了 $S$ 中的人并到达 $x$ 的最短时间。 接下来转移有两种： - $\to f_{y, S}$，也就是移动到 $y$。 - $\to f_{x, S | 2^k}$，也就是在 $x$ 蹲守某个人。 类似 djk 的跑即可。 ### D. Pattern Lock 给定 $n$ 行 $m$ 列的点阵图，用一条折线经过所有的点各一次，要求每条线段不经过除端点外的其他点，且形成的角都是锐角。 对于 $n, m$ 存在偶数的情况是简单的。  这样两行两行的构造即可。 对于都有奇数的，那么先构造一个 $3 \times 3$ 的，接下来会分出两个偶数矩阵即可。 大概就是  ### E. Stone Ocean 定义一个长为 $n$ 串的权重 $w(s)$ 为有多少个排列 $p$ 使得 $s[p_1]s[p_2] \ldots s[p_n]$ 是一个回文，现在有 $n \le 30$ 个串，从每个串随机选一个位置的字符，连接成一个长为 $n$ 的新串，求这个新串的 $w$ 的期望。 先考虑如何计算 $w(s)$。先判断是否能够成为回文，如果可以，枚举哪两个会配对，最后乘上 $(\frac n2)!$ 来修正这些配对的位置即可。 于是类似的，枚举哪两个字符串会配对，记 $mat(i, j)$ 表示 $s_i, s_j$ 选择相同字符的方案数。那么总贡献即是 $(\frac n2)! 2^{\frac n2} \prod mat_{i, j}$ 其中 $2^{\frac n2}$ 是选择一个子集作为左部，$\prod$ 内的东西是所有配对的对。注意在奇数的情况下需要新建一个虚点 $x$ 使得 $mat_{i, x} = |s_i|$，与虚点匹配的放在最中间，还要注意这个虚点不会影响前面的系数。 考虑 $n$ 很小，进行状压，$f[S] \times mat_{i, j} \to f[S | 2^i | 2^j]$，这是容易理解的。最后除以方案数即可得出期望。为了不重复贡献，每次 $i$ 只需要设为最小的即可。 乍一看是 $2^{30}$ 的状态数，然而实际上远远没有这么恐怖，由于我们每次选择了最小的 $i$，对于状态，必须满足前缀 $1$ 的个数 $\ge 1$ 的个数的一半，于是状态数大概为： $$

\sum_{i = 0}^{\frac n2} \binom{n - i}{i}

$$ 在 $n = 30$ 时 $= 1346269$（实际也是如此），利用类似队列的思路转移，那么只需要 $\times 30$，计算级别在 $4 \times 10^7$，能过。 题解状态数分析就是一坨，不好评价。 ### F. Jumping Monkey II 对每个点 $x$，以 $x$ 为起点出发时，求所有简单路径的 `LIS`，注意 $x$ 必选。 首先容易得出一个 $O(n^3 \log n)$ 的解法，也就是 $O(n^2)$ 的枚举路径，然后 $O(n \log n)$ 的求 `LIS`。 其次，枚举每一个根 $rt$，设 $f_{x, i}$ 表示以 $i$ 开头的 `LIS` 的最长长度，这容易利用线段树合并完成 $O(n^2 \log n)$。 发现这是 $O(n^2)$ 树上状态问题，考虑分治。这里的话边分治更简单，并且常数很小。 只是注意这里边分治需要在三度化的时候将点权下放到边权上：  最终复杂度 $O(n \log^2 n)$。 ### G. Five Phases 给定一个 $5$ 元环，需要进行 $k \le 10^5$ 次操作，每次操作可以进入如下操作之一，求到达目标局面的方案数。 - 单点 $\pm 1$ 或者全局 $\pm 1$。 - 相邻的 $3$ 个 $\pm 1$。 - 相邻的 $2$ 个 $\pm 1$，对面的那个 $\mp 1$。 联想到生成函数，是 $5$ 元的： $$

[x^a y^b z^c w^d v^e] \left(
\begin{aligned}
& x + y + z + w + v + \frac 1x + \frac 1y + \frac 1z + \frac 1 w + \frac 1 v \
& xyzwv + \frac 1 {xyzwb} \
& xyz + yzw + zwv + wvx + vxy + \frac 1 {xyz} + \frac 1 {yzw} + \frac 1 {zwv} + \frac 1 {wvx} + \frac 1 {vxy} \
& \frac {xy}{w} + \frac {yz}{v} + \frac {zw}{x} + \frac {wv}{y} + \frac {vx}{z}+ \frac {w}{xy} + \frac {v}{yz} + \frac {x}{zw} + \frac {y}{wv} + \frac {z}{vx}
\end{aligned}
\right)^k

$$ 经过通分化简，可以得到： $$

[x^a y^b z^c w^d v^e] \left(
\frac {(1 + xy)(1 + yz)(1 + zw)(1 + wv)(1 + vx)}{xyzwv}
\right)^k

$$ 将 $\frac 1 {xyzwv}$ 提出去，得到： $$

[x^{a + k} y^{b + k} z^{c + k} w^{d + k} v^{e + k}] \left(
{(1 + xy)(1 + yz)(1 + zw)(1 + wv)(1 + vx)}
\right)^k

$$ 先考虑一个简化的问题：$[x^a y^b z^c]((1 + xy)(1 + yz)(1 + zx))^k$。 考虑有哪些组合 $(xy)^l (yz)^m (zx)^n$ 可以贡献到目标，列出等式： $$

\begin{cases}
a = l + n \
b = l + m \
c = m + n
\end{cases}

$$ 发现 $l, m,n$ 都是唯一的，类似的推广，也就变成了 $5$ 个组合数相乘即可。 ### H. Reverse the String 给定字符串 $S$，至多可以翻转一个区间，求最小字典序。 首先发现翻转的开头是一定的，也就是第一个存在 $S_j \lt S_i$ 的那个 $i$。 之后也就只有 $O(n)$ 种可能，利用 `hash` $+$ 二分比较字典序即可。 ### L. Tree Game 给一棵树，每个点有权值，权值是一个排列。从叶子开始，每次重新排列 $x$ 和其所有儿子，然后向上递归。目标权值等于结点编号，给定其中一些权值，问有多少可能的权值排列可以排序成功。 首先考虑全部确定的情况，发现只需要不断交换模拟即可。 而加入 $0$ 之后呢，发现判断还是只需要模拟即可，只是 $0$ 是万金油，可以等于一切。 于是呢，考虑当前节点 $x$，现在可以重排一些东西，和一些 $0$，发现其实这些 $0$ 任意排列都可以，也就是可以贡献一个 $cnt!$。而又无法影响到子树内部，所以可以得到递推式： $$

f_x = cnt! \prod f_y

$$ 随便做即可。 ## GYM 103743 ### B.Prime Ring Plus 将 $1 ∼ n$ 分成若干个环，每个环上相邻两数之和是质数，$n \le 10^4$。 $O(n^2)$ 的枚举可以放在一起的，发现奇偶形成二分图，那么跑一个网络流即可，注意一个需要连两个。 复杂度 $O(n \sqrt {n^2}) = O(n^2)$。 ### D. Finding Pairs 给定一个序列和一个数 $k$，每次询问一个区间，问在区间中找若干对不含重复元素的距离为 $k$ 的数的最大权值和。 将 $\bmod k$ 相同的弄出来，可以作为一个单独的问题。 如果是暴力，自然想到设 $f_{i, 0/1}$ 表示考虑了前 $i$ 个数，最后一个数选没选的最大价值。 于是考虑可以莫队，但是回滚，设 $f_{i, 0/1, 0/1}$ 表示 $\bmod k$ 为 $i$ 的序列的 DP 数组，那么稍微特判一个只有一个/两个数的情况转移即可。 复杂度 $O(n \sqrt n)$。 ### E.Playing Cards 给定序列 $A, B$，以及一个 $k \le 10^9$，构造一个排列 $P$，使得下式最小： $$

\sum_{i = 1}^n \left\lceil \frac {\max(0, B_i - A_{P_i})}{k} \right\rceil

$$ 有一个不是那么优秀的做法，每次取出最小的 $A_i$，如果存在比 $A_i$ 小的 $B_i$，贪心匹配 即可，否则将 $A_i \leftarrow A_i + k$，并 $ans \leftarrow ans + 1$，将 $A_i$ 重新放入堆中，这样是 $O(n^2 \log n)$ 的。 注意这似乎不太好优化，我们将对于 $A_i$ 的 $+ k$ 变为对于 $B_i$ 的 $-k$，那么做法变为从大到小枚举 $A_i$，如果存在 $B_i \gt A_i$，那么不断 $B_i \leftarrow B_i - k, ans \leftarrow ans + 1$，直到所有 $B_i \le A_i$，此时 $A_i$ 与最大的 $B_i$ 配对即可。 利用线段树上二分即可优化为 $O(n \log n)$。 ### F. Pockets $n$ 种物品价值 $v_i$，体积 $w_i$，无限个，总容量 $k$。 如果购买 $i$ 个物品，则总容量变为 $i + k$。 至多购买 $m$ 个物品，求所有合法购买方案的价值之和，定义一个方案的价值为 $\prod v_i$。 对于多项式还是不会……考虑单次购买的生成函数：$f(x) = \sum v_i x^{w_i}$。 于是答案为：$\sum_{i = 0}^m \sum_{j = 0}^{i + k} [x^j] f^i (x)$。 注意到后面是生成函数前缀和可以转化为：$\sum_{i = 0}^m [x^{i + k}] f^i(x) \frac 1 {1 - x}$。 然而这个 $[x^{i + k}]$ 很难处理，考虑将系数平移一下： $$

[x^{m + k}] \sum_{i = 0}^m f^i(x) \frac {x^{m - i}} {1 - x}

$$ 然后可以将 $f^i(x)$ 转化为 $f^{m - i}(x)$ 的形式： $$

[x^{m + k}] \frac {f^m(x)}{1 - x} \sum_{i = 0}^m \frac {x^{m - i}}{f^{m - i}(x)}

$$ 后者可以利用 $\frac {1 - x^{k + 1}}{1 - x} = \sum_{i = 0}^k x^i$ 的形式化简： $$

[x^{m + k}] \frac {f^m(x)}{1 - x} \frac {1 - \cfrac {x^{m + 1}}{f^{m + 1}(x)}}{1 - \cfrac x {f(x)}}

$$ 再稍微化简一下： $$

[x^{m + k}] \frac {f^{m + 1}(x) - x^{m + 1}}{(1 - x)(f(x) - x)}

$$ 多项式全家桶即可。 ### H. Super Gray Pony 求长为 $n$ 的 $0/1$ 串 $S$ 求 $k$ 次格雷码后的结果，求格雷码是指将 $S$ 看做二进制数，求其在 $n$ 阶格雷码序列中的下标。 格雷码有个小小的性质：$Rank(x) = x \oplus (x >> 1)$。 于是求 $k$ 次对于前面的 $S_{x + i}$ 来说其贡献次数为 $\binom ki$。 利用 `Lucas` 来分析，只有 $i \& k = i$ 的那些 $S_{x + i}$ 会对于 $S_{x}$ 做出贡献。~~于是对于每一个地方来一次子集卷积？~~ 考虑 DP 的思路，设 $f_{x, i}$ 表示对于 $x$ 只考虑 $k$ 的前 $i$ 位构成的子集的贡献。 初始 $f_{x, 0} = S_x$，考虑第 $i$ 位，如果为 $0$，那么不会存在新的子集，那么 $f_{x, i} = f_{x, i - 1}$，如果为 $1$，那么可以存在新的子集，其从 $f_{x + 2^i, i - 1}$ 转移而来。 也就是 $f_{x, i} = f_{x, i - 1} \oplus f_{x + 2^{i - 1}, i - 1}$。 交换一下枚举顺序，先枚举 $i$，那么可以利用 `bitset` $O(\frac {n \log n}{w})$ 的完成。 ### J. Balanced Tree 求 $n$ 个点组成的每个节点都满足左右子树大小相差至多 $1$ 的二叉树个数。 容易想到一个记忆化搜索的方式： $$

f_n = \begin{cases}
2 f_{\frac n2} f_{\frac n2 - 1} & \text{n is even} \
(f_{\frac n2})^2 & \text{n is odd}
\end{cases}

$$ 不难证明状态数是 $2 \log n$ 的，答案一定形如 $2^c$，可以变为指数加法。 直接记忆化复杂度是 $O(T \log n \log \log n)$ 的，无法通过，但是可以通过分层记忆化的方式优化到 $O(T \log n)$，只是常数略大，需要狠狠卡常才能过。 此时其实会发现每一层至多两个状态，模拟这个过程即可去掉记忆化的常数。 然而 [@The_Last_Candy](https://codeforces.com/profile/The_Last_Candy) 给出了一种不同的方法。 将对于指数加法的式子改写为： $$

f(x) = f(\left\lfloor \frac {x - 1} 2 \right\rfloor) + f(\left\lceil \frac {x - 1} 2 \right\rceil) + [\text{x is even}]

$$ 发现偶数的地方会贡献一个 $2$，那么考虑是否可以通过类似数位 DP 的方式求得所有转移时为偶数的个数。 设 $f_{i, 0/1}$ 表示考虑了前 $i$ 位，当前位为 $0/1$ 的个数，然而由于存在 $-1$，所以还需要增加一个 $0/1$ 表示是否向前借位。 那么对于转移： $$

\begin{aligned}
x &= n 的第 i 高位 \
f_{i, 0, 0} &= \begin{cases}
f_{i + 1, 0, 0} + 2f_{i + 1, 1, 0} & x = 0 \
f_{i + 1, 0, 0} + 2f_{i + 1, 1, 1} & x = 1
\end{cases} \
f_{i, 1, 0} &= \begin{cases}
0 & x = 0 \
f_{i + 1, 0, 0} + 2 f_{i + 1, 1, 0} & x = 1
\end{cases} \
f_{i, 1, 1} &= \begin{cases}
f_{i + 1, 0, 0} + 2 f_{i + 1, 1, 1} & x = 0 \
0 & x = 1
\end{cases}
\end{aligned}

$$ 反着来变成 DP 减少常数，最后指数就是 $\sum f_{i, 0, 0}$。 ## GYM 104396 ### B. Honkai in TAIKULA 给定一张 $n$ 个节点 $m$ 条边的有向带权图，对每个节点，若不存在奇权圈（可经过重复顶点、重复边，若经过重复边，边权计多次），输出 `Battle with the crazy Honkai`，否则，输出最小奇权圈的权值（负无穷输出 `Haha, stupid Honkai`）。 由于需要存在圈，那么圈一定在强连通分量内，那么可以利用 `tarjan` 分为若干强连通子图进行求解。 考虑由于需要奇偶分开，那么拆成奇偶两个点即可。 考虑如果是跑 `SPFA` 的话就需要 $O(nm^2)$ 的复杂度，显然不太能过，所以需要用到 `Johnson` 全源最短路算法，优化为 $O(nm \log n)$。 注意有负权环存在的情况。 ### D. Rail Star 二维平面上有 $n$ 个点，设 $A_i,j$ 表示将第 $i$ 个点删除后，将剩下 $n − 1$ 个点划分为两个集合后，提取其中点数为 $j$ 的集合，这个集合的种类数。求出该矩阵。 类似于 [1860F](https://codeforces.com/contest/1860/problem/F) 的想法，一共 $O(n^2)$ 种斜率，带来 $O(n^2)$ 种映射方式，每种映射带来的一种排序都会对于答案做出贡献。 这 $O(n^2 \log n)$ 很容易维护这一个排序方式，但是我还不太清楚该如何维护答案。 ### E. LCM Plus GCD 输入 $x, k$，求大小为 $k$ 的不同的集合个数，其中所有数的 $\gcd + \mathrm{lcm} = x$。 考虑 $\mathrm{lcm} = k \gcd$，那么枚举 $\gcd$ 即可得到 $k$。 观察每一个数，将 $k = \prod {p_i}^{c_i}$，那么对于每一个数的分解，再除以 $\gcd$，指数需要满足 $\min = 0, \max = c_i$。 考虑实际上因数的个数 $\le 9$，那么考虑状压容斥，先枚举有哪些没有满足下界，在这个基础上枚举有哪些没有满足下界，复杂度 $O(Tm2^{2m})$。 ### G. Moving Boxes $n$ 个物品在一条直线上，每个需要从 $x_i$ 移动到 $y_i$ ，有一个机器人移动，机器人每次只能拿一个物品，速度为 $1$，转向需要 $c$ 秒，最后需要回到起点，方向回到初始方向。求运输完所有物品需要的最小时间。 贪心，还不太会。 ### L. Architect 给出 $n$ 个长方体，询问其是否拼接成一个 $W \times H \times L$ 的立方体，没有重叠和空隙。 1. 做法一，先判断体积和。将全部无交容斥为有交，数点问题即可。 2. 做法二，利用随机化将每个立方体的体积放缩，如果满足要求，那么无论如何放缩体积都是合法的，多次随机充分 $\to$ 必要。 3. 做法三，还是先判断体积和，从一维结论合理外推，充要条件是每个点都覆盖了偶数次，利用 `map` 判断即可。 > $\downarrow 2024.03.04$ ## 1936 ### [A. Bitwise Operation Wizard](https://codeforces.com/contest/1936/problem/A) 交互题，每次可以询问 $a_i | a_j$ 与 $a_x|a_y$ 的大小关系，求最大的 $a_i \oplus a_j$，其中 $a_i$ 是一个 $0 \sim n - 1$ 的排列。 首先贪心的肯定要选择最大的那个，然后选择一个数（选了最大的，自然这个就是最小的了）凑出一个 $2^k - 1$。 那么根据 $x | x = x$，利用 $O(n)$ 次形如 $(i, i, j, j)$ 的询问即可找出最大。 找到了 $i$ 最大，接下来需要 $a_i \oplus a_j = 2^k - 1$，只需要找到 $a_i | a_j$ 最大的那些 $j$ 中最小的那个即可。考虑满足 $a_i | a_j$ 最大的一定是 $a_i$ 补集的超集，而需要恰好凑出全部，那么自然是最小的那个，分别 $O(n)$ 次即可。 ### B. Pinball 给定一个 `<>` 组成的字符串，当一个球至于其上某一个位置，其会按照一下规则运动： - 如果所在字符为 `<`，那么向左一位，否则向右。消耗 1s 时间。 - 当球移动之后，原本所在位置字符取反，即 `<` 变成 `>`，反之同理。 - 如果移出串内，则停止运动，既可以是左边，也可以是右边。 多组数据，给定长度为 $n$ 的串，分别求出把球放在 $1 \sim n$ 这些位置需要多少秒才能走出这个串。可以证明一定可以在有限步内走出。 先考虑模拟，比较容易发现，实际上球在一段反复走，向两边拓，于是可以变成双指针 $O(n^2)$ 求。 观察双指针的本质，设出发点在 `>`，分讨出发点左侧（包括）`>` 的个数 $S_0$ 和右边 `<` 的个数 $S_1$。 当 $S_0 > S_1$，那么最终会从字符串右边出去，推推式子即可；当 $S_0 \le S_1$ 则反之，也是推推式子即可。 ### C. Pokémon Arena 有 $n$ 神奇宝贝。一开始，竞技场上只有第 $1$ 只神奇宝贝。 每只神奇宝贝都有 $m$ 种属性。而第 $i$ 只神奇宝贝的 $j$ 属性是 $a_{i,j}$ 。第 $i$ 只神奇宝贝的雇佣费用是 $c_i$ 。 为了最终让 $n$ 只神奇宝贝站在竞技场，可以按照任意顺序执行以下两种操作： - 花费 $k$（$k > 0$）的代价，将 $a_{i,j}$ 永久增加 $k$ 。 - 花费 $c_i$ 代价雇佣第 $i$ 只神奇宝贝与当前场上的神奇宝贝 $k$ 决斗，并选择任意属性 $j$。如果 $a_{i,j} \ge a_{k, j}$ ，则 $i$ 击败 $k$，$i$ 上场，否则保持不变。 求出让第 $n$ 只神奇宝贝站在竞技场上所需要支付的最低费用。 > 傻逼翻译。 最直观的想法是，一个神奇宝贝一定不要上场两次，否则直接跳过中间部分。 另一个十分重要的观察：不会连续选择相同的 $j$。否则不如直接跳过中间次决斗，省下雇佣费。 相当于只有去决斗前才会调整 $a_{i, j}$，并且之后都不会在用到这个值。 于是如果让 $i$ 用属性 $j$ 与 $k$ 决斗，那么一定需要的花费是 $c_i + \max(0, a_{k, j} - a_{i, j})$。 利用这个东西建图，可以做到 $O(n^2 m)$。考虑可以优化建图。 将 $c_i$ 提出来，拆点处理，接下来考虑 $\max(0, a_{k, j} - a_{i, j})$ 的边，发现实际上只需要在同层间前后缀一下即可。 于是建出图来跑 DJK 即可。 ### D. Bitwise Paradox 我原本以为只是支配对相关的题目，因为只有 $O(n)$ 个对，但是带修就炸了。考虑 $b_i | b_{i + 1} | \ldots | b_{j}$ 有一个很好的性质，在固定 $i$ 的情况下，只有 $O(\log V)$ 种取值。 所以放在线段树上，维护前缀，后缀，与值与最大值，合并即可。 直接合并是 $O(\log^2 V)$ 的，但是利用支配对考虑，双指针合并变成 $O(\log V)$。 总复杂度 $O((n + q) \log n \log V)$。 ### E. Yet Yet Another Permutation Problem 首先有一个很 `naive` 的 $O(n^2)$ DP： $$

f_{i, j} =
\begin{cases}
[i \ge j](i - j + 1) f_{i - 1, j} + \sum_{k < j} f_{i - 1, k} & j \ne P_i \
0 & j = P_i
\end{cases}

$$ 前面直接做，后面前缀和即可，最后答案是 $f_{n, n}$。 没什么优化的前途，考虑 $P$ 的前缀 $\max$ 数组 $Q$。 考虑构造出来的排列和 $Q$ 存在某一位相同，设为 $i$，那么需要满足 $Q_i$ 在 $i$ 或者之前出现，并且 $i$ 前都没有比 $Q_i$ 大的。 逆着不好考虑。顺着不会考虑，还是没太懂题解的 DP 是怎么来的。 TODO。$$