AtCoder Grand Contest 040 题解
A - ><
题意
给定一个长度为 \(N-1\) 的只包含 < 和 > 的字符串 \(S\)。
一个非负整数序列 \(a_1,a_2,\ldots,a_N\) 被称为好的当且仅当满足以下条件：
- 若 \(S_i\) 是
<，则有 \(a_i<a_{i+1}\)； - 若 \(S_i\) 是
>，则有 \(a_i>a_{i+1}\)。
求一个好的序列的元素之和的最小值。
\(N\le 5\times 10^5\)
题解
显然 \(a_i\) 的下界为左边连续 < 的数量与右边连续 > 的数量的较大值。
当 \(a_i\) 都取这个下界时显然满足条件。
所以直接求出 \(a_i\) 后计算即可。
时间复杂度 \(O(N)\)。
B - Two Contests
题意
给定 \(N\) 个区间 \([l_i,r_i]\)，将他们分成非空的两组。定义一个区间的权值为这个区间中包含的整点数量，定义一组区间的权值为这组区间的交的权值。
求两组区间的权值之和的最大值。
\(N\le 10^5\)
题解
不妨将所有区间右端点加 \(1\)，将权值转化为区间长度。
首先考虑其中一组区间的交为空的情况。为了使得长度之和最大，另一组一定只有一个区间，并且是所有区间中最长的。
接下来考虑两组区间都非空的情况。假设第一组区间为 \(S\)，那么答案式子为
\[\min_{i\in S}r_i-\max_{i\in S}l_i+\min_{i\not\in S}r_i-\max_{i\not\in S}l_i\]
令 \(R=\min r_i,L=\max l_i\)，即全局右端点的最小值和全局左端点的最大值。
我们不妨强制 \(\min\limits_{i\in S} r_i=R\)，此时又分两种情况。
当 \(\max\limits_{i\in S} l_i=L\) 时，所有区间都可以被放入 \(S\) 中。所以我们一定会尽可能地把区间放入第一组，将最长的区间放入第二组。
当 \(\max\limits_{i\in S} l_i\ne L\) 时，考虑枚举 \(\max\limits_{i\in S} l_i=L'\)。由于 \(\min\limits_{i\in S}r_i=R\)，是全局最小值，所以放入第一组的区间只需要满足 \(l_i\ge L'\) 即可。我们仍然会尽可能地把满足条件的区间都放入第一组，将其他区间放入第二组。
于是对于这种情况，我们只需要将区间按 \(l_i\) 排序，预处理出 \(r_i\) 的后缀 \(\min\) 后枚举一个前缀放入第一组，可以 \(O(1)\) 计算答案。
时间复杂度 \(O(N\log N)\)。
C - Neither AB nor BA
题意
给定一个偶数 \(N\)，求通过若干次以下操作可以将字符串 \(S\) 变成空串的，长度为 \(N\) 且只包含 A、B 和 C 的字符串 \(S\) 的数量：
- 选择 \(S\) 中相邻两个字符，并将他们删去。但是不允许删除
AB或BA。
对 \(998244353\) 取模。
\(N\le 10^7\)
题解
发现删除相邻两个字符有一些性质：
- 删除的两个位置奇偶性不同；
- 删除后其余位置的奇偶性不变。
于是我们可以考虑把所有奇数位的 A 变成 B，B 变成 A，这样我们的限制条件相当于变成了不能删除连续两个 A 或连续两个 B。
充要条件是 A 和 B 的数量都不超过 \(\frac{N}{2}\)。必要性显然，充分性可以通过每次删除多的字符证明。
于是用容斥计算即可。时间复杂度 \(O(N)\)。
D - Balance Beam
题意
有 \(n\) 条线段，每条线段长度都为 \(1\)。在第 \(i\) 条线段上，A 的速度为 \(\frac{1}{a_i}\)，B 的速度为 \(\frac{1}{b_i}\)。
A 会将 \(n\) 条线段按他想要的顺序排列形成一条长的线段，并以最左边的点作为起点。
然后 B 会在这条长度为 \(n\) 的线段上等概率随机一个实数点作为起点。
A 获胜的条件是，A 和 B 同时出发后，按给定速度行走，A 能在 B 到达最右边之前的某个时刻追到 B。
求 A 的最大胜率。以最简分数形式给出。
\(n\le 10^5\)
题解
假设已经固定了线段的顺序，显然能使 A 获胜的点一定是一个前缀。
若我们以距最左边点的距离为 \(x\) 坐标，时间为 \(y\) 坐标，可以得到两条折线，其中 A 折线的终点为 \((n,S)\)，其中 \(S=\sum a_i\)。
为了求出最远的能使 A 获胜的点，我们将 B 折线从 \(x\) 轴下方向上移，直到与 A 折线有交点。此时记 B 折线与 \(x\) 轴的交点为 \((p,0)\)，那么 \(p\) 就是最远能使 A 获胜的点。
我们考虑一条新的折线 C，在 A 与 B 的交点左边取折线 B，右边取折线 A，那么 C 是一条从 \((p,0)\) 开始到达 \((n,S)\) 的折线。注意到每个方案都可以对应这样的一条折线，所以我们接下来考虑所有这样的折线。
为了使 \(p\) 尽量大，我们一定会让折线 C 尽量“陡峭”。令 \(k\) 为包含 \(p\) 的线段，在 C 经过的线段中，除 \(k\) 的斜率为 \(b_k\) 以外，斜率上界为 \(\max(a_i,b_i)\)。
事实上，我们可以达到这一上界。只要将 \(a_i < b_i\) 的线段放在折线 A 与 B 的交点前面，\(a_i \ge b_i\) 的线段放在后面即可。
于是我们考虑枚举 \(k\)，然后按 \(\max(a_i,b_i)\) 从大到小依次加入线段，直到 \(b_k+\sum \max(a_i,b_i)\ge S\)。这可以通过预处理前缀和实现。
时间复杂度 \(O(n\log n)\)。
E - Prefix Suffix Addition
题意
有一个初始为 \(0\) 的序列 \(x_1,\ldots,x_n\)。
你可以执行若干次以下操作：
- 选择一个 \(k\ (1\le k\le n)\) 和一个不降的非负整数序列 \(c_1,\ldots,c_k\)，执行 \(x_i\gets x_i+c_i\)。
- 选择一个 \(k\ (1\le k\le n)\) 和一个不增的非负整数序列 \(c_1,\ldots,c_k\)，执行 \(x_{n-k+i}\gets x_{n-k+i}+c_i\)。
求使得 \(x_i=a_i\) 的最少操作次数。
\(n\le 2\times 10^5\)
题解
对于两次前缀加操作，若非零位置有交，一定可以通过调整仍然满足条件，并且不变劣。后缀加同理。
于是问题转化成了求两个序列 \(\{x_i\},\{y_i\}\)，满足：
- \(x_0=y_0=x_{n+1}=y_{n+1}=0\)
- \(x_i,y_i\ge 0\)
- \(x_i+y_i=a_i\)
最小化 \(\sum [x_i>x_{i+1}]+[y_i<y_{i+1}]\)。
令 \(f_{i,j}\) 表示前 \(i\) 个数，\(x_i=j\) 时上式的最小值。对于每个 \(i\)，有性质：
- \(f_{i,j}\) 单调不增；
- \(0\le f_{i,0}-f_{i,a_i}\le 2\)。
于是我们记录两个分界点，每次二分两个分界点进行转移即可。
时间复杂度 \(O(n\log n)\)。
F - Two Pieces
题意
数轴上有两个点，一开始都在原点。每次你可以执行以下两种操作之一：
- 选择一个点向右（正方向）移动一个单位；
- 将左边的点移动到右边的点的位置。
你需要执行 \(N\) 次操作。求最后左边的点在 \(A\)，右边的点在 \(B\) 的方案数。
两种方案被认为不同当且仅当某次操作之后两个点的坐标集合不同。
\(N\le 10^7\)。
题解
考虑用 \((x,d)\) 来表示一个状态，其中右边的点在 \(x\)，两点距离为 \(d\)。相当于有以下三种操作：
- 将 \(x,d\) 同时加 \(1\)；
- 将 \(d\) 减 \(1\)，需要满足操作以后 \(d\ge 1\)，即操作前 \(d\ge 2\)；
- 将 \(d\) 置 \(0\)。
此时由于第二种操作限制了 \(d\ge 2\)，每种操作一定互不相同，所以问题转化为求操作序列数量。
考虑确定前两个操作序列，然后插入第三种操作。
注意到第一种操作恰好执行 \(B\) 次，考虑枚举第二种操作的操作次数 \(k\)。这个方案数可以用折线法进行计算。
然后考虑插入第三种操作。注意到插入后需要满足以下两个条件：
- 最终 \(d\) 到达 \(B-A\)；
- 不会使第二种操作不合法。
注意到将一个第三种操作插入到 \((x_i,d_i)\) 后，会导致后面的 \(d_j\) 都减 \(d_i\)。
为了满足第一个条件，需要保证最后一个第三种操作满足 \(d_i=A-k\)。
为了满足第二个条件，需要保证每个第三种操作都满足 \(d_i\) 是后缀的严格最小值，即不存在 \(j\ge i\) 满足 \(d_j \le d_i\)。
也就是说，我们可以在最后一次 \(d_i=0,1,2,\ldots,A-k\) 后面连续插入任意数量个第三种操作，并且需要保证 \(d_i=A-k\) 后面一定有一个第三种操作。用隔板法计算即可。
时间复杂度 \(O(n)\)。
