久违的菜的真实的 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$ 有下式

再特判一下 $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$，当前的答案为

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

G Petya and Graph

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

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

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

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

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

搭配飞行员

二分图匹配。

太空飞行计划

最大权闭合子图。

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

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

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

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

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

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

感谢 Ellery 贡献的题解。

题面

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

的非负整数解数。

其中 $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$ 步

因此，$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$ 的概率，最终答案为

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

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

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

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

A Regular Bracket Sequence

B Discounts

C Painting the Fence

给定长度 $n$ 的序列上的 $q$ 条线段，从中删除两端使得剩余被覆盖位置数量最大。

枚举两个线段，要求计算这两段上有多少个位置只被覆盖一次，线段重合部分上有多少个位置只被覆盖两次。

D Stressful Training

给定 $n$ 台电脑，每台电脑初始有电量 $a_i$，每小时消耗电量 $b_i$，有一个充电器每小时可为一台电脑充电，求使得所有电脑工作 $k$ 天所需要充电器的最小每小时充电量。

考虑二分，贪心构造。每天将没电时刻最早的那台电脑拿出来充电，并且如果某天有多台电脑在此刻没电，那么构造失败。

注意：二分边界，使用数组和指针来维护，而不是上数据结构！

二分不出来的我 T^T。

F Clear the String

给定一个字符串 $s$，每次可以删除一个相同的连续段，求最小删除次数。

区间 DP 裸题。

考虑 $f[l][r]$ 表示删除区间 $[l,r]$ 的花费。

转移时，若 $s[l]=s[r]$

否则

区间 DP 不出来的我 T^T。

G Greedy Subsequences

定义贪心子序列 $a_{p_1},a_{p_2},a_{p_3},\dots$ ，满足，$p_{i+1}$ 是大于 $p_i$ 的第一个满足 $a_{p_{i+1}} > a_{p_i}$ 的下标。

求序列 $a$ 的每一个长度为 $k$ 连续子区间的最长贪心子序列长度。

可以发现，对于整个区间而言，贪心子序列实际上构成的一个树的结构，每个点都会连向唯一一个点，且可能存在前面的若干点连到这个点上。

考虑维护一个单调递减的单调栈，来建出这棵树（森林）。

对于每次询问实际上是在顶点编号在 $[i,i+k-1]$ 范围内的对应虚树上，询问树（森林）的最大高度。

使用线段树维护每个点的高度，区间左指针移动表示虚树上删除了一个点，右指针移动表示虚树扩大，需要给对应子树区间内所有点高度 $+1$。

妙啊！

模板

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

int mu[maxn], vis[maxn], prime[maxn], tot;
void getMu() {
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * prime[j] < maxn; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

A Dice Rolling

B Letters Rearranging

C Mishka and the Last Exam

有一个长度为偶数的单调不减序列 $a$，给定了一个长度为其一半的序列 $b$，满足

要求恢复出序列 $a$。

贪心，左边的数必须尽量小。

D Beautiful Graph

给一个图上每个点染上 $1,2,3$ 三种颜色，要求相邻顶点的颜色和为奇数，求方案数。

每个点分奇偶两种状态，一个联通块取定一个点后，块内奇偶性确定，遍历两遍即可。

注意遍历时的判环和判是否走过某个点写法。

遍历图都不会写了 T^T。

E Intersection of Permutations

给定两个序列 $a,b$，有两种操作。

交换序列 $b$ 的两个数，询问序列 $b$ 的 $[l2,r2]$ 区间内有多少个数在序列 $a$ 的 $[l1,r1]$ 区间内。

在序列 $b$ 上每个前缀维护主席树，再带上修改操作，树状数组套主席树即可。

cdq 分治不会写 T^T。

G Multidimensional Queries

维护一个序列，每个位置是一个 $k$ 维向量（$1\le k \le 5$）。

有两种操作，单点覆盖和询问区间两点间最大的曼哈顿距离。

建 $32$ 棵线段树即可。