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]$

$$
f[l][r]=min(f[l][r-1],f[l+1][r],f[l+1][r-1]+1)
$$

否则

$$
f[l][r]=min(f[l][j],f[j+1][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$，满足

$$
b_i=a_i+a_{n-i+1}
$$

要求恢复出序列 $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$ 棵线段树即可。

A Minimum Integer

B Accordion

C Division and Union

给定 $n$ 个线段，将线段分成两个集合，两个集合之间的线段没有交集。

按左端点排序，将和第一个相交的一整段抠出来，剩余放在第二个集合内。

D GCD Counting

求树上最长路径，满足路径上点权的 $\gcd$ 大于 $1$。

点分治一下。

点权不是很大，考虑把路径的质因子抠出来 $dp$。

E Polycarp’s New Job

G (Zero XOR Subset)-less

给定一个长度为 $n$ 的序列，将序列分成最多线段，满足线段集合的任意子集没有异或和为 $0$。

转换成前缀和，即变成选择最多的单点，且必须选择最后一个点，使得任意子集异或和不为 $0$，即线性无关，线性基插入即可。

A Sea Battle

B Draw!

按照时间顺序给定一场比赛某些时刻的比分，求最多有多少时刻出现平局。

时间按照不降序给出，相邻两个时间点可能会出现重合，维护一下最后统计的平局时间，防止遗漏。

C Birthday

D Gourmet choice

给定一个 $n \times m$ 的表，表示第一块 $n$ 个物品和第二块 $m$ 个物品之间的权值关系，大于，小于或相等，要求恢复出每个物品的权值。

将权值相同的点缩点后跑拓扑排序即可。

一开始缩点的时候没写 find(x) 挂了一堆 T^T。

F Asya And Kittens

有一个 $1$ 到 $n$ 的排列，有 $n-1$ 次操作，每次将两个数字所属的块合并，这两个块一定相邻，要求恢复出原排列。

并查集维护一下所属关系，链表维护每个块内有哪些点。

B 解题

给一个 $10^6$ 位的大数（每位数均为 $1$ 到 $9$），一次操作可以保留一段连续区间，其余位置置 $0$。

有 $q$ 次询问，每次询问一次操作后得到的最小的 $m$ 的倍数。

类似于询问区间异或等于 $0$，这里变成模 $m$ 加法，询问一段连续区间模 $m$ 为 $0$。

从低位往高位扫一遍，维护每种模数出现的最后位置，第一次出现同余即是最小的 $m$ 倍数。

D 进制转换

询问 $[l,r]$ 区间内有多少个数在 $k$ 进制表示下有 $m$ 个尾 $0$。

转化为前缀和。

$k$ 进制下恰好有 $m$ 个尾 $0$，即是 $k^m$ 倍数而不是 $k^{m+1}$ 的倍数。

为了避免一些乱七八糟的情况，我选择交 python。

E 中位数

给定一个有向无环图，每个点有一个权值 $a_i$，求 $1$ 到 $n$ 的路径中，路径经过点的点权的中位数的最大值。

二分答案，$check$ 能否构造出中位数为 $mid$ 的路径。

将点权大于等于 $mid$ 赋值为 $1$，否则为 $-1$，求 $1$ 到 $n$ 的 DAG 最长路，判断最长路是否非负即可。

F 方差

给定一个序列，求大小为 $m$ 的子集中的方差最小值。

排过序后，一定是连续的 $m$ 个数，扫一遍即可。

A Water Buying

B Tanya and Candies

给定一个序列，求有多少个位置删除后，奇数位置和等于偶数位置和。

预处理每个后缀的奇数和，偶数和即可。

C Palindromic Matrix

回文矩阵，左右翻一下，上下翻一下，都和原矩阵相同。

注意一下奇数时的处理即可。

写错了个条件 FST 了 T^T。

D Coffee and Coursework

有 $n$ 杯咖啡，要写 $m$ 页书。每杯咖啡有权值 $a_i$，每天喝第一杯咖啡可以写 $a_i$ 页，第二杯咖啡 $max(0,a_i-1)$ 页，第三杯咖啡 $max(0,a_i-2)$ 页。求最少多少天可以写完 $m$ 页。

对所有咖啡权值排序。

二分答案。显然，权值大的咖啡尽量在每天第一个喝。

E Yet Another Ball Problem

F1 Tree Cutting (Easy Version)

A Best Subsegment

给一个序列，找平均值最大且最长的连续区间的长度。

差点没反应过来？平均值最大一定是序列的最大值，就是找最长的连续最大值。

B Emotes

C Magic Ship

给一个长度为 $n$ 的 UDLR 风向序列周期出现，每天你会被风向吹一格，你自己可以移动一格，两者独立，求从起点走到终点最少需要多少天。

二分天数。当天数大于最小值时，显然可以反方向走风向，也可以到达终点，因此可以二分。

预处理出，周期序列上每天的风向偏移量，可以得到 $mid$ 天后总共偏移了多少，最后判断一下曼哈顿距离即可。

D Magic Gems

求长度为 $n$ 的满足条件的不同 01 串个数，0 必须是连续的 $m$ 个位置。

考虑 $dp[i]$ 表示长度为 $i$ 的答案，有转移方程 $dp[i]=dp[i-1]+dp[i-m]$。

由于 $n$ 很大，$m$ 很小，矩阵快速幂加速 $dp$ 转移即可。

E Decypher the String

给定一个串，要你猜某个 $1$ 到 $n$ 的排列，按照这个排列做一个映射得到的加密串是什么。

你只有 $3$ 次询问，$1 \le n \le 10000$。

由于 $26^3 > 10000$，对每个位置 $26$ 进制拆分后，最多 $3$ 位数。

第一次询问，$abc…zabc…z…$，则 $a$ 相同的位置无法确定，第二次询问即是 $26$ 进制拆分的第二位，第三次询问同样。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

struct Mat {
    static const int M = 2;
    ll a[M][M];
    Mat() { ms(a, 0); }
    void clear() { ms(a, 0); }
    void eye() { for (int i = 0; i < M; i++) a[i][i] = 1; }
    ll* operator [] (ll x) { return a[x]; }
    const ll* operator [] (ll x) const { return a[x]; }
    Mat operator * (const Mat& b) {
        const Mat& a = *this; Mat r;
        for (int i = 0; i < M; i++)
            for (int j = 0; j < M; j++)
                for (int k = 0; k < M; k++)
                    r[i][j] = (r[i][j] + a[i][k] * b[k][j]) % mod;
        return r;
    }
    Mat pow(ll n) const {
        Mat a = *this, r; r.eye();
        while (n > 0) {
            if (n & 1)  r = r * a;
            n >>= 1; a = a * a;
        }
        return r;
    }
    Mat operator + (const Mat& b) {
        const Mat& a = *this; Mat r;
        for (int i = 0; i < M; i++)
            for (int j = 0; j < M; j++)
                r[i][j] = (a[i][j] + b[i][j]) % mod;
        return r;
    }
    void print() const {
        for (int i = 0; i < M; i++) for (int j = 0; j < M; j++)
            printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};

A Sasha and His Trip

$1$ 到 $n$ 个地点排成一行，相邻两个距离为 $1$，现在要从 $1$ 不回头走到 $n$。

走一个单位距离，消耗一点油，油箱最大容量为 $v$，每个点有一个加油站，第 $i$ 点加油的费用为 $i$ 块钱每升，求最小花费。

一开始尽量加满，然后每个位置如果油箱有空余且不能支持走完全程，就加油。

写错加油的容量，过了好久才过 T^T。

B Sasha and Magnetic Machines

给一个一个序列，选两个数 $a_i$ 和 $a_j$，选一个 $a_j$ 的因子 $x$，将两个数变成 $xa_i$ 和 $a_j \over x$，求序列总和最小能变成多少。

式子写出来

$$
\min(xa_i+{a_j \over x}-a_i-a_j)=\min((x-1)(a_i-{a_j \over x}))
$$

贪心的想，$a_i$ 肯定选最小的，$j$ 枚举即可。

C Sasha and a Bit of Relax

给一个序列，求有多少长度为偶数的连续子序列，满足序列前一半和后一半的异或和相等。

其实这个一半是骗你的，往一半上想就凉了。

实际上，就是求长度为偶数的区间，异或和为 $0$，统计一下每种异或前缀和的个数即可。

D Sasha and One More Name

将一个回文串，切几刀，拼成一个和一开始不同的回文串，求最小切几刀。

首先，判断出无解的情况，显然如果前一半每个字母都相同，不管怎么切都不会弄成一个不同的回文串。

对于一个回文串，他肯定存在一个前缀不是回文串，对称地切两刀，交换前后缀位置就是一个新的回文串，且与之前不同，所以刀数最多为 $2$。

所以就要判断能不能切一刀，可以发现这个串是一个回文循环串，由于 $1 \le n \le 5000$，暴力即可。

F Sasha and Interesting Fact from Graph Theory

求满足条件的 $n$ 个点带边权的树个数，边权取值范围是 $1$ 到 $m$，满足给定了 $a$ 和 $b$，树上 $a$ 到 $b$ 路径长度恰好为 $m$。

先只考虑 $a$ 到 $b$ 的路径，我们可以枚举这个路径上的边数 $i$，然后相当于将 $m$ 划分成了 $i$ 个数，由插空法可知有 $m-1 \choose i-1$ 种情况。路径上有 $i-1$ 个点可以随意选择，方案数为 $(i-1)!{n-2 \choose i-1}$。剩下 $n-1-i$ 条边的边权可以随意选择，方案数为 $m^{n-i-1}$。最后一部分就是求剩下的点挂在这条链上的树的个数。

由 Cayley定理，我们知道 $n$ 个带标号的点组成 $k$ 棵无根树的森林的方案数为 $k n^{n-k-1}(1 \le k \le n-1)$。

我们可以考虑将前一步选出来的路径上 $i+1$ 个点拿出来，加上剩余的点组成 $i+1$ 棵无根树。对于每棵无根树，为避免重复，将树上标号最小点设置定为根，这些根按第一部分连成树链即可。因此，只需要在最后乘上 $(i+1)n^{n-i-2}$。