补题进度：3/10 (13)
Csy Contest
*A
题意
给定一个序列 a[1..n]，对于每个长度为 m 的连续子区间，求出区间 a 的最大值以及从左往右扫描该区间时 a 的最大值的变化次数。
1 ≤ m ≤ n ≤ 107。
题解
经典的单调队列问题，但习惯从前往后的统计话发现很难处理${2,1,3,4…}$和${2,3,3,4…}$，倒着维护一个递减的单调队列，队头元素即max， 队列中的数的数量即为max变化次数。
B
题意
给定一个字符串 S[1..n]，m 次询问指定它的一个连续子串。
你需要统计该子串有多少条分割线满足这条分割线前后两个字符串都是回文串。
1 ≤ n, m ≤ 105。
题解
回文树
留坑
C
题意
给定一个 n 个点的无向图，m 次加边或者删边操作。
在每次操作后统计有多少个匹配包含$ k = 1, 2, …,n/2$ 条边。
2 ≤ n ≤ 10, 1 ≤ m ≤ 30000。
匹配：选择的k条边使得这2·k个点独立
题解
D
打表即可看出结论
E
题意
给定一个 n × m 的矩阵，可以将其中不超过 A 个位置的值设为 0。
找到不超过 B 个不相交的列数都为 m 的连续子矩阵，使得和最大。
1 ≤ n ≤ 100, 1 ≤ m ≤ 3000, 0 ≤ A ≤ 10000, 1 ≤ B ≤ 3
题解
F
把q和t最后的值xor等于所以的值xor，不等于0的话q和t的值肯定不相等，先手肯定能赢
G
题意
给定平面上 n 个点，起点横坐标最小，终点横坐标最大。
每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。
求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。
2 ≤ n ≤ 200000。
题解
H
题意
给定一棵 n 个点的树，除 1 外每个点有一只怪兽，打败它需要先消耗 ai 点 HP，再恢复 bi 点 HP。
求从 1 号点出发按照最优策略打败所有怪兽一开始所需的最少 HP。
2 ≤ n ≤ 100000。
题解
I
题意
给定一个正整数序列 a[1..n]，每个数在 [1, m] 之间，有些数
已知，有些数未知。
求未知数随机填的情况下以下值的期望：
n∏−3
i=1
v[gcd(ai
, ai+1, ai+2, ai+3)]
4 ≤ n ≤ 100, 1 ≤ m ≤ 100。
题解
J
题意
给定平面上 n 个带信息的点，m 次询问一个平行坐标轴的矩形内所有点的不可减信息和。
1 ≤ n ≤ 105， 1 ≤ m ≤ 106。
题解
K
题意
给定第一象限内 n 个点，任意两点间连边，权值为两点坐标的点积。
求这个完全图的最小生成树。
2 ≤ n ≤ 100000。
题解
L
暴力模拟
M
题意
给定一个 n 个点，m 条边的有向图，q 次询问 s 到 t 经过至少 k 条边的最短路。
2 ≤ n ≤ 50, 1 ≤ m, k ≤ 10000, 1 ≤ q ≤ 100000。