开始日常 AtCoder 的 ABC 场以外题解（不咕咕咕的话。

A Regular Triangle

B Red or Blue

C Snuke the Wizard

给定一个长度为 $n$ 的一排房间，每个房间有个字母，一开始每个房间只有一个人。

之后有 $q$ 次操作，每次操作将待在所有房间字母为 $s_i$ 的房间内的所有人，向左或右平移一个格子。

若移动到最左边和最右边之外，这个人就没得了，求最后剩多少人。

注意到，人是一个格子一个格子平移的，不会有人跨越的现象。

因此掉落到左边一定是一个前缀，掉到右边的一定是一个后缀，二分前缀和后缀的长度即可。

降智严重，sb 二分竟然没想到。

D Modulo Operations

好题！

给定一个数字 $x$，有一个集合 $S$，每次随机从集合内删除一个数 $y$，将当前数字 $x$ 变成 $x$ mod $y$。

求将集合删光时，当前数字的期望。

注意到，每次都是取模操作，所以当前数字一定是单调不增的。其次，若一开始选了一个比较小的数字，则后面可以任意选择较大的数而不会产生影响。

这就等价于，给定一个单调递减的操作序列 $S$，对于第 $i$ 个操作，有 $1 \over n-i+1$ 的概率，对当前数取模。

对于已经进行过的 $i-1$ 次操作，每个数都有一个出现的概率，于是我们考虑第 $i$ 个数对于每个概率的影响，若选了这个数，进行这个操作，反之代表这个数会进行之后的操作。

也就是对于 $f(i,x)$ 表示进行到第 $i$ 次操作时，当前数为 $x$ 的概率，有转移方程

$$
f(i,x \text{ mod } a_i)=f(i-1,x) \cdot {1 \over n-i+1} \
f(i,x) = f(i-1,x) \cdot (1 - {1 \over n-i+1})
$$

显然只要操作序列单调递减，上述转移正确；若操作序列不单调递减，则会在某一个上升处，这个位置的数对概率的影响并没有计算到。

模板

1
2
3
4
5
6
7
8
9
10
11
12

int pre[maxn];
void init() {
    for (int i = 1; i <= n; i++) pre[i] = i;
}
int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return ;
    pre[x] = y;
}

A Detective Book

B Good String

C Playlist

有 $n$ 首歌，每首歌有长度 $t_i$ 和好听度 $b_i$，选出至多 $k$ 首歌，他们的权值是好听度的最小值乘时长和，求最大权值。

按照好听度排序，倒着维护长度的前 $k$ 大。

D Minimum Triangulation

F Extending Set of Points

一个点集，若有点 $(x_1,y_1),(x_1,y_2),(x_2,y_1)$ 则也会有点 $(x_2,y_2)$。

给定一串加点或删点操作序列，若之前出现过当前点则为删点，否则为加点，求每次操作后的点数。

将两个维度拆开，加入一个点 $(x,y)$ 意味着编号为 $x$ 的白点连向了编号为 $y$ 的黑点，否则为删边。

每次询问就是询问，一个联通块内黑点数乘白点数，对所有联通块求和。

于是，我们要维护一个带删边的并查集，以及集合大小信息。

线段树分治 + 带撤销并查集。

线段树分治，即对时间维建立线段树，将每个点的贡献放到线段树的结点上打 $\log n$ 个标记。

最后，分治时统计当前区间的贡献，这个地方需要有并查集的撤销操作。

久违的菜的真实的 XLor。

A Even Substrings

B Chocolates

读错题是怎么回事？

C Edgy Trees

给定一棵树，有一些关建边，求点集有多少大小为 $k$ 的有序子集，满足集合内存在一个相邻两点的树上路径经过关建边。

考虑反面，一个集合内不经过关建边，当且仅当这些点都在一个由非关建边连接而成的子联通块内。

连接所有非关建边，求一下每块大小即可。

D Steps to One

给定整数 $m$，每次在 $[1,m]$ 内随机选择一个数 $x$ 加到序列内，当序列 $\gcd$ 为 $1$ 时，停止操作。求序列长度的期望。

考虑莫比乌斯反演。

对于因子 $d$，求序列 $\gcd$ 被 $d$ 整除的期望 $f(d)$，且序列至少选择一个 $d$ 倍数（否则有重复），令 $q=[m/d]/m$ 有下式

$$
f(d)=\sum_{i=1}^{\infty} (i+1) \cdot q^i \cdot (1-q)
$$

再特判一下 $d=1$ 的贡献即可。

E Maximize Mex

给定 $m$ 个集合和 $n$ 个人，每个人属于集合 $c_i$， 有权值 $p_i$。

有 $d$ 次操作，每次删除一个人，求从每个集合内选出一个人组成新的集合的 $mex$ 最大值。

显然，将删除变成插入操作，且易知答案具有单调性。

考虑二分图匹配，左边的点集为 $m$ 个集合，右边的集合为权值 $p$，当且仅当集合有一个权值为 $p$ 的人时连边，且 $p$ 小于当前的答案。

对于每个答案，左边点集只会连向权值小于等于当前答案的边，如果此时最大匹配等于答案，那么显然存在一种分配方案。

我们不需要每次重新跑匹配，当二分图成功匹配后，表示存在一种派出方案，更新答案，并将答案对应的权值连边，继续在此基础上跑匹配。

A Vasya and Book

B Vova and Trophies

给定一个 $01$ 串，求交换某一对字符后，最长的连续 $1$ 串。

只能交换一次，遍历时维护一下前一次的线段长度和端点。

注意判一下在连续 $1$ 串后面补了一个 $1$。

C Multi-Subject Competition

有 $n$ 个人，$m$ 种学科，每个人擅长学科 $s_i$，能力值为 $r_i$。

求派出一些人，满足每种学科擅长人数相同时的，总能力值最大值。

每种学科中的人按能力值大小排序，枚举每个学科的参与人数，遍历时维护一个前缀和即可。

注意写的时候复杂度不要退化。

D Maximum Diameter Graph

要求构造 $n$ 个点，满足每个点 $i$ 度数不超过 $a_i$，求最大的图的直径（最短路的最大值）。

显然只需要扣出一棵树即可，满足树的直径最大。

进一步，如果度数都比 $2$ 大，肯定连一条链最优。

但是，考虑到有 $1$ 度结点，对于前两个接在头尾两处，剩余的接在其他点上。

E Increasing Frequency

给定一个序列 $a$ 和整数 $c$，现在你可对一个区间 $[l,r]$ 内的所有数加上 $x$，求序列内最多有 $c$。

显然就是找一段区间的众数，加上区间外 $c$ 的出现次数。

预处理 $c$ 个数的前缀和 $pre$。

枚举每一种数值 $x$，对于第 $i$ 个 $x$，记为 $x_i$，当前的答案为

$$
\max_{j=1\dots i}(pre[n]-pre[x_i]+pre[x_j-1]+i-j+1) \
= pre[n]-pre[x_i] + i + 1 + \max_{j=1\dots i}(pre[x_j-1]-j)
$$

后面一块可以遍历时维护出来。

G Petya and Graph

给定一个 $n$ 个点 $m$ 条边简单无向图，求权值最大的一个子图，权值为边权和减去点权和。

注意到 $n,m \le 1000$ 和题目定义的权值，考虑最大权闭合子图模型。

对所有边建一个点，建立超级源点到每条边上，容量为边权，并将所有点连向一个超级汇点，容量为点权。

对于，一条边它的依赖关系其实就是相邻的两个点，对应连边。

跑一个最大权闭合子图即可。

搭配飞行员

二分图匹配。

太空飞行计划

最大权闭合子图。

闭合子图：子图中每个点的出边指向的结点也在子图内。

有 $n$ 个商品，$m$ 个物资，生产一个商品需要某些物资，商品有价值，物资有费用（出现时只算一次），求最大利益。

建一个超级源点 $S$ 指向所有商品，容量为商品权值，建一个超级汇点 $T$，所有物资指向 $T$，容量为物资费用。

对于依赖关系，建一条容量为无穷大的边。

最大权闭合子图为商品正权值之和减去最大流（最小割）。

最大权闭合子图为最后所有与超级源点相连的点。

感谢 Ellery 贡献的题解。

题面

给定系数序列 $a$ 和 $B$ 的范围 $[mn,mx]$，求不定方程

$$
a_1 \cdot x_1 + a_2 \cdot x_2 + a_3 \cdot x_3 + \dots + a_n \cdot x_n = B
$$

的非负整数解数。

其中 $1 \le n \le 12, 0 \le a_i \le 5 \times 10^5, 1 \le B \le 10^{12}$。

分析

先任意取一 $a_i$，当我们找到一个符合条件的 $B$ 有 $B \text{ mod } ai = d $ 时，因为符合条件所以有一组整数解 $(x_1,x_2,x_3,\dots,x_i,\dots,x_n)$。

此时 $B+a_i$ 必定也是符合条件的，这个时候的整数解会变成 $(x_1,x_2,x_3,\dots,x_i+1,\dots,x_n)$。

所以我们对于每一个余数 $0,1,2,3,\dots,\min(a)-1$，只需要找到符合条件的最小的B即可。

在余数 $[0,\min(a)-1]$ 上建立点集，用 $dist[i]$ 来表示模 $min(a)$ 的余数为 $i$ 的最小 $B$ 值。

为了求出 $dist$ 数组，考虑 dijkstra 的松弛操作，对于 $i$，加上其他任意一个 $a_j$ 时，会出现一个新的余数 $k = (i + a_j) \text{ mod } \min(a)$，可以理解为由点 $i$ 向点 $k$ 连接了边权为 $a_j$ 的边。

对于每个点 $i$ 都有了一个 $dist[i]$。如果 $dist[i]$ 大于 $B$，则其对答案是没有贡献的；若小于则对答案贡献为 $(B – dist[i]) / \min(a) + 1$。

区间前缀和差分一下得到最终答案。

A Sushi for Two

给定一个序列，求最长的一个子串，满足 $00 \dots 011 \dots 1$。

预处理每个位置后的最长连续 $1$ 或 $2$，扫一遍即可。

B Circus

有 $n$ 个人，每个人可以表演 a 或 c 两种节目，将 $n$ 个人分成大小相同的两块，满足第一块能够表演 a 的人和第二块表演能够 c 的人数相同。

一共有四类，两种都无法表演，表演一种和两种都不能表演。

枚举第一块表演 a 的个数和第二块表演 c 的个数，解一个关于两种都行的方程即可。

注意各种边界条件。

C Skyscrapers

给定一个 $n \times m$ 的矩阵，独立询问每个位置所在行和列，用数字 $1$ 到 $x$ 去替换这一行一列的数字，使得原来的行内数字大小关系不变，列内数字大小关系不变。

对每一行和每一列分别离散化，询问就是行列比当前位置的数小的个数的最大值，以及对应大的最大值，最后加 $1$。

D Camp Schedule

给定 $01$ 串 $s$ 和 $t$，要求任意调换 $s$ 串内的顺序，使得新串包含最多的子串 $t$。

对 $t$ 串建 $KMP$ 的 $fail$ 指针，扫一遍贪心构造即可。

F Cooperative Game

有一个长度为 $t+c$ 的有向链，其中 $t+c$ 连向 $t+1$。

起点为 $1$，终点为 $t+1$，一开始有 $10$ 个人在起点。

每次可以移动一些点到其对应的下一个位置，返回哪些点在相同位置。

要求在 $3 \times (t+c)$ 次操作内将这些人移动到起点。

龟兔赛跑判环。

取两个点，每次一个点走 $1$ 步，一个点走 $2$ 步，设最后相遇在第 $x$ 步

$$
x-t \equiv 2x-t (mod \text{ } c)
$$

因此，$c|x$，然后起点和相遇点一同往后移动，显然第一次相遇在 $t$ 处。

题面

给定一个长度为 $n$ 的序列 $a$，有 $q$ 次操作，每次操作交换 $a_x,a_y$。

现在，对于每次操作，你可以选择做或者不做，一共有 $2^q$ 种情况，求逆序对数之和。

其中 $1 \le n, q \le 3000$。

分析

发现 $n$ 很小，可以枚举序列的每一对。

将问题转化为概率，题目变成求逆序对数的期望。

考虑每一个数对的贡献，记 $f[i][j]$ 表示 $a_i>a_j$ 的概率，最终答案为

$$
2^q \cdot \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} f[i][j]
$$

考虑每次操作 $(x,y)$ 对概率的影响，显然有一半的概率不变，即 $f[x][y]$，有一半的概率交换，即 $f[y][x]$。

除此以外，还有一部分是通过某一个位置中转，交换了 $(x,y)$，设中转位置为 $k$。

$x$ 和 $k$ 先交换，然后交换 $k$ 和 $y$，类似的得到相应概率 $dp$ 转移。

时间复杂度：$O(n^2+nq)$。