2019年10月

[Summary]

一点小记录

10-2

Process

T1开场就写了，T2一开始想到了一个贪心做法，后面发现是错的。最后写了一个退火，花了较长时间。T3不太会做，博弈论不太熟悉，就只写了30分

T1

[区间dp] [动态规划]

直接区间dp即可

T2

[贪心]

直接贪心是假的，因为 $A_{i}-B_{i}$ 的大小会影响到当天是否会被淹没，而又应该将 $A_{i}$ 更大的留到最后一次爬上去。(但是也 A 掉了 )

所以要枚举最后一天爬上去用的是哪个药丸，然后剩下的就可以根据 $A_{i}-B_{i}$ 的大小贪心了

暴力做是$O(n^2)$的，可以用数据结构维护，做到$O(n \log n)$

T3

[2-SAT] [SG函数] [博弈]

sol from GC

首先可以把行列抽象成点，连出一个 2-sat ，并且因为边双向，所以只要联通就是强连通，并查集就可以处理。因为玩家只考虑最大化自己的分数，所以首先会尽量齐心协力达到所有硬币都为正的局面，然后再根据操作步数去判断谁多 1 分。

把 $x_{0}$ 和 $x_{1}$ 在同一个强连通分量里的情况特判掉，然后考虑对联通块黑白染色，染成黑色表示选择这个联通块内点所表示的翻转方案 ，那么显然对于 $x_{0}$ 和 $x_{1}$ 所在的联通块，它们不能染成相同的颜色，我们把这种关系连上边，会得到若干个二级联通块，每个二级联通块可以看做一个独立的游戏，并且只有两种方案可选。

若两种方案需要翻转的行列数皆为奇，先手胜，SG=1 ；皆为偶，SG=0 ；一奇一偶，根据 SG 定理，SG=Mex{0,1}=2 。然后把所有子游戏的 SG 异或起来即可，若为 0 ，先手败。

10-3

Process

T1搞的时间有点长，期间一度陷入死胡同。T2开始没想到点子上，在想如何优化单次$n^2$的dp。后来往组合方面想，就一步步推出来了。T3没动

思维太慢了！！！T2一个简单的$n^2$暴力都想了很久才找到方向

个人觉得今天的题出得非常好，T2有点THUSC2019 D1T1的感觉，只是码量稍微有点大了...

T1

一开始想的是从根开始依次还原，发现有问题，后来发现从叶子开始依次还原就可以了

T2

[方差] [组合数学] [计数] [线段树] [NTT] [卷积]

$D(X) = E(X^2) - E^2(X)$

考虑枚举子序列的长度$len$

$\displaystyle \sum E(X^2)$很好算，它就等于$\displaystyle \sum_{i}\frac{\sum_{j} a_j^2 \times \binom{len-1}{i-1}}{i}$（考虑每个数的贡献，因为地位等价所以可以一起算）

但是$\displaystyle \sum E^2(X)$不好算，因为不等于$\Big(\displaystyle \sum E(x)\Big)^2$

可以把式子展开

利用

所以$\displaystyle \sum E^2(X) = \sum_{i}\frac{\sum_{j}a_j^2 \times \binom{len-1}{i - 1} + 2\cdot \sum a_ua_v \times \binom{len - 2}{i - 2}}{i^2}$

又因为和$a$有关的项可以提出来算，所以问题就转化成了两部分：计算，以及对于每个$len$计算后面那一坨式子

• 前半部分：因为$\sum a_ua_v = \big(\sum a_i\big)^2 - \sum a_i^2$，所以线段树维护$\sum a_i$和$\sum a_i^2$即可

• 后半部分有三个式子：

  $\begin{aligned} f[n] &= \sum_{i=1}^{n}\binom{n - 1}{i - 1}\times \frac{1}{i}\\ g[n] &= \sum_{i=1}^{n}\binom{n - 1}{i - 1}\times \frac{1}{i^2}\\ h[n] &= \sum_{i=2}^{n}\binom{n - 2}{i - 2}\times \frac{1}{i^2}\\ \end{aligned}$

  都可以卷积，或者也可以神仙推式子

T3

[神仙题] [组合数学] [计数]

讲一下如何算答案

$\begin{aligned} ans &= \sum_{m=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n-m}{m}\sum_{i=0}^{m}\binom{m}{i}\binom{k}{n-i}\\ &= \sum_{m=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n-m}{m} \binom{m +k}{n} \end{aligned}$

枚举长度为$2$的段数$m$，第一个组合数就是枚举所有可能的排列方式，乘上它后相当于已经确定了序列的形态了

接下来确定取值：先从$m$个长度为$2$的段中，选出$i$个段作为长度相等的段。那么剩下要选的，互不相等的取值就只有$n-i$个了。从$1\sim k$这$k$个数中选$n-i$个数，然后按顺序依次填到之前确定的序列中去即可

最后再用范德蒙德卷积优化一下

10-4

Process

T1写了个暴力找找规律就搞出来了，T2花了较长时间，写了一个细节稍多的做法，最后还是调出来了。T3一开始想写$O(n^2)$的做法，但细节没有想清楚，导致没时间写了

想题还是太慢，这两天T2都是中等偏简单的题，自己却花了很长时间才想清楚。

T1

[组合数学]

T2

[线段树] [数据结构] [分治]

我的做法：

把线段树看成一个分治结构，每次统计跨中点的区间的答案

需要对于每个节点维护答案、前后缀和，以及深度

具体细节见代码

T3

[栈] [贪心]

首先有一个贪心：从右往左扫，若当前数与左边的数合并后$\ge 0$，则把他们合并。最后再将得到的新序列从左往右依次合并

设$pre_i$表示第$i$个数最多能往左合并到的位置，那么会形成一些$[pre_i, i]$这样的段

显然从$r$开始不断跳$pre$，再特殊处理一下$l$所在段，即能求出答案

把询问离线，挂在右端点上，用个栈动态维护上述过程即可

需要注意的是，在用栈动态维护的过程中，得到的数可能很大。但若在某一时刻答案$\ge 10^9$，则它再以后都会$\ge 10^9$，不会更小了

这是因为$a_i$最小也只有$-10^9$，而每次答案会先翻倍再加上前面的数，所以一定不会更小

10-5

Process

一个小时搞完的T1（实际上是错的。。。），开始以为T2可以直接缩边双跑$O(n^2)$暴力，写了一两个小时之后发现假了，必须要缩点双。T3看懂题花了好长时间，20分暴力还写挂了（以为题目给的点权是十进制的）

T1

[构造]

先特判$n$和$m$不全为偶数的情况，然后有两种构造方法：

.((((.
(()())
()()()
(()())
()()()
.)))).

这样构造是$n+m-4$的

((((((
()()()
)()()(
))))))

这样构造是$\max \{n, m\} + \frac{\min\{n, m\}}{2} - 1$的

两种取最优的即可

T2

[仙人掌] [最小生成树] [图论]

题目给出的图实际上就是一个仙人掌（每条边只属于一个简单环中）

考虑对于原图中的每个环，把环上的最小的边断掉，再把这个环上其他边加上该边的权值，得到的答案是相同的

因为在环上任意两点的答案一定会包含最小的边

这样操作完后，原图就变成一棵树了。直接按边权从大到小排序，用并查集考虑每条边对答案的贡献即可

T3

见此

10-7

Process

拿到题之后以为T1是找规律，找了好久都没找出来，于是写了一个自认为复杂度错的dp，后来仔细想想发现是对的。T2写了整除分块，一个细节地方写错了，爆成20，T3没时间看了。。。

T1

[记忆化搜索] [树形DP]

树形DP ，设 f(0/1, x) 为 x 是否选择时，以 x 子树的最大匹配和匹配数。发现对于表示区间长度相同的结点，它们的 DP 值是相同的，于是 map 记忆化 $O(n \log n)$ DP 即可。

复杂度正确的关键在于线段树同一层上最多只有两种表示区间的长度相差 1 的结点。

Proof ：若某一层有两种节点，设大小分别为 2n 和 2n+1 ，则每个节点会分成两个大小为 n 的节点或一个大小为 n ，另一个大小为 n+1 的节点，下一层依然只有两种大小的节点，成立。

T2

[整除分块]

对于确定的 x ，它在区间 [L,R] 内的倍数有 $cnt=\lfloor \frac{R}{x} \rfloor-\lfloor \frac{L-1}{x} \rfloor$ 个，其中最小一个的系数为 $k_{mn}=\lfloor \frac{L-1}{x} \rfloor + 1$ ，那么 S(x) 的所有非空子集的元素大小和可以表示为 $2^{cnt-1} \times x \times \frac{cnt \times (2k_{mn}+cnt-1)}{2}$

整除分块即可

T3

[贪心] [二分答案]

二分答案

设$f[i]$表示在 $i$ 放技能能否存活， $a[i]$ 为前$i$ 秒累计的被动血量变化，那么上一次放技能的点 $j$ 必须满足 $f[j]=1,i-j \ge cd$ 并且 $\max_{k \le} \lbrace a(k) \rbrace \le hp+k\cdot j , k\in [j+1,i]$

但实际上通过思考可以发现，若把判断条件改成$k\in [1, i]$也并不影响答案，于是符合条件的$j$必然是单调不降的

另一种情况，$i$ 是第一次放技能的点，那就只需要 $hp \ge \max \lbrace a[k] \rbrace, k\in [1, i]$

只要预处理$a[i]$ 的前缀 max 即可

10-8

Process

考了我、jwb、cxr出的联考题。校内效果似乎不是很理想，我的T2得分的人并不多。。。T1是一道FST好题。cxr的T3出得非常好！

T3

Description

给一个长度为$n$的数字串$S$（包含$?$，$?$表示可以任填$0\sim 9$）和一个长度为$m$的数字串$T$。定义一个串$S$是好的，当且仅当$T$作为子串在$S$中出现至少一次

$Q$次询问，每次给出$k$，求第$k$大的好串

$n\le 5\times 10^4, m\le 20, q\le 10^5, k\le 10^{18}$

Solution

[倍增] [数位dp] [动态规划] [树链剖分] [KMP]

首先可以数位dp，设$dp[i][j]$表示$S$考虑到第$i$位，匹配了$T$串$j$位的方案数。kmp处理下一位填$0\sim9$的数时$j$如何变化。转移和这道题类似

这样做是单次$O(n)$，因为需要依次确定每一位填什么，考虑优化

类似重链剖分的过程，每一位选出一个dp值最大的后继作为重儿子，倍增预处理出重链信息，查询时如果能跳重链就跳重链，否则暴力确定后继

这样做的复杂度是$O(\log k \log n)$的，因为每暴力确定一次后继，$k$减少至少一半；而每跳完一次重链都一定会暴力确定一次后继（否则肯定可以继续往后跳重链）。所以经过的轻重链都是$O(\log k)$级别的，而每次跳重链复杂度为$O(\log n)$

总复杂度$O(nm\log + q\log k \log n)$

10-10

Process

几乎一整场在写T1，开场写了个贪心过了大样例， 但是小数据随便拍就错了，然后就一直在修修补补，最后写了个二分图匹配才拍上。写完T1只剩半小时，T3暴力写完就没时间了。结果大家T1都写的贪心还都A了。。。感觉好不公平。。。

T1

[贪心] [二分图匹配]

直观想法是直接贪心，即从大到小考虑每一行/列，尽量把行列最大值相同的交一起。但这是错的，因为这样做出来的交点个数不一定最优。用二分图匹配实现行列配对的过程即可

T2

[长链剖分] [数据结构]

之前考过这道题的一个部分分，居然忘了怎么做。。。

首先对于一个确定的$d$，肯定是贪心选最长的$l$条链，可以用类似长剖的方法实现

考虑每次增加 1 的深度，然后加入该层的结点并更新当前所有链的长度，并维护前 $l$ 长的链。显然可以预处理出原树的长链剖分，那么就唯一确定了每个点在任意时刻所属的链

$\log$可以随便做，但这题必须$O(n)$。考虑利用每次每条链长度最多变化 1 的性质，用桶来 $O(1)$ 更新前 $l$ 长的链。具体而言，对每个长度维护有多少链属于前 $l$ 大，每次尽量把长度 +1 的链看做位于前 $l$ 长使得答案更优

T3

[矩阵快速幂]

考虑用矩阵依次处理整个过程，只要能够做到依次处理每个字符，那么#运算就能用矩阵快速幂优化

如何构造矩阵呢？显然，构造的矩阵在运算时必须要满足线性性，否则不能矩乘

因为题目没有括号，只有+ - *，考虑把某一时刻的答案拆成a + b * c的形式，分别维护a、b、b * c这三项（注意必须是b * c，否则不满足线性性）。讨论一下+ - *这三种运算符，以及新加一个数字这四种情况时的转移矩阵即可

举个例子：往后加一个数字$d$

$a+b * c \rightarrow a + b * (10c + d)$，所以a、b项不变，b * c项乘十再加$b * d$

所以T[2][2] = 1, T[3][3] = 10, T[2][3] = d;

剩下的转移矩阵类似，具体见代码

10-11

Process

先开的T2，写了一个线段树 + set 的做法，卡了卡常能过样例就没管了。然后去搞T1，式子化到一半不会处理组合数前缀和我是个智障...于是写了个40分暴力，并且因为常数太大T了一个subtask。T3基本没看

T1

注：以下的整除符号均省略

考场上想到的化式子方法：

然后不会求$\binom{d}{B}$的前缀和。。。（显然前缀和就是杨辉三角最右边右下角的那个值）不过这样算复杂度不对，也跑不过去

正解需要换一个思路，考虑把上式的$dg$提到前面去

$\begin{aligned} ans &=\sum_{dg=1}^{min(n, m)} \frac{n}{dg} \frac{m}{dg} \sum_{d|dg} \binom{d}{B} \mu(\frac{dg}{d})\\ &=\sum_{i=1}^{\min\{n, m\}} \frac{n}{i} \frac{m}{i} \sum_{d | i} \binom{d}{B} \mu(\frac{i}{d}) \\ &=\sum_{i=1}^{\min\{n, m\}} \frac{n}{i} \frac{m}{i} f(i) \end{aligned}$

只要快速计算$f(i)$前缀和即可

$\displaystyle f(i) = \sum_{d | i}\binom{d}{B}\mu(\frac{i}{d})$

设$g(i) = \binom{i}{B}$, 那么$f = g * \mu \Rightarrow g = f * 1$

$g$的前缀和很好算，所以可以直接杜教筛，复杂度不会算

T2

我的做法: 显然，合法情况不能有越过$[r_1, r_2]$的弦，所以只需要计算$r_1$的答案。用线段树 + set 维护一下不合法的位置即可

cxr的做法: 算$r_1$的答案时，可以给每条线段随机赋一个权值，统计前缀异或和相等的区间有多少个即可

10-13

Process

想了一上午的T1都没想出来，不知道怎么回事。T2大家都做过原题，T3找了下规律写了32分暴力

T1

[数据结构] [时光倒流]

感觉很巧妙的一道题，好像很睿智但是自己就是想不到。。。

把操作倒着考虑，设当前操作$[l, r]$，那么$[r + 1, r + (r - l)]$这一段的字符肯定是当前这一次操作"造"出来的，所以可以把它们的父亲指向$[l, r]$中对应位置，然后把他们删掉，再处理前一次操作（因为在前一次操作中这段字符肯定是没有出现的）

用vector维护即可（因为需要找当前存在的第$l$个位置在哪里，所以不能直接并查集维护。也可以用平衡树实现）

Code

inline void Solve ()
{
	static vector <int> vec;
	static int fa[MAXN + 5];

	for (int i = 1; i <= K; ++i) vec.pb (i);

	for (int t = Q; t >= 1; --t)
	{
		int l = A[t].x, r = A[t].y, len = r - l + 1;
		if (vec.size() <= r) continue;

		int p = ((l & 1) || (l == r)) ? l : l + 1;
		for (int i = r; i < min ((int) vec.size(), r + len); ++i)
		{
			fa[vec[i]] = vec[p - 1];
			p += 2;
			if (p > r) p = (l & 1) ? l + 1 : l;
		}

		vec.erase (vec.begin() + r, vec.begin() + min ((int) vec.size(), r + len));
	}

	for (int i = 1, j = 1; i <= K; ++i)
	{
		if (!fa[i]) Ans[i] = S[j++];
		else Ans[i] = Ans[fa[i]];
		printf("%c", Ans[i]);
	}
}

T2

之前做过，见这里

10-14

Process

T1搞了比较长的时间，一开始sb了以为最多就一种顺子。。。拍出错了之后才发现要搜顺子。。。T2直接写了个5行的bitset。T3把读入格式的$c_i$和$v_i$看反了，调了好久的样例，最后没时间优化了

做题速度太慢，感觉还没找到自己考试的节奏，要抓紧时间调整状态了！！

T1

[搜索] [贪心]

本质有用的牌型只有对子、三张、三带一、四带二、顺子

爆搜顺子，剩下的贪心

T2

[bitset]

数据随机，期望分布得会比较均匀，用bitset的_Find_next找后继即可

T3

[动态规划] [背包] [bitset] [二进制拆分]

设$dp[i][j][k]$表示到第$i$种，选了$j$种，容量为$k$是否可行，暴力背包转移是$n^4$的

考虑优化，首先可以bitset除掉一个$\omega$

大概是这个意思

for (int i = 1; i <= N; ++i)
    for (int j = i - 1; j >= 0; --j)
        for (int l = 1; l <= A[i].y && l * A[i].x <= L; ++l)
            Dp[j + 1] |= Dp[j] << (A[i].x * l);

然后可以二进制拆分，这样就能优化到$\frac{n^3 * \log c_i}{\omega}$了

Code

for (int i = 1; i <= N; ++i)
	for (int j = i - 1; j >= 0; --j)
	{
		int res = 1, now = A[i].y;
		bitset <MAXN + 5> tmp;
		while (now >= res)
		{
			if (A[i].x * res <= L) tmp |= (tmp << (A[i].x * res)) | (Dp[j] << (A[i].x * res));
			now -= res;
			res <<= 1;
		}
		if (now && A[i].x * now <= L) tmp |= (tmp << (A[i].x * now)) | (Dp[j] << (A[i].x * now));
		Dp[j + 1] |= tmp;
	}

10-15

Process

T1是gc讲过的题，之前没写，考试当场写的。T2猜了个结论，估计是spj的原因只有25分。T3贴了之前考过的一道题的程序，有一点不一样，但是拿到了90分

T1

[二分答案] [主席树]

对于一次询问，可以二分答案，把$\ge mid$的数设成$1$，$< mid$的数设成$-1$，那么只要左端点$\in[l1, r1]$， 右端点$\in[l2, r2]$的区间中，存在某个区间和非负，则说明答案大于等于$mid$。这个判断不难

多组询问的话，每次不能暴力设数，那么主席树预处理即可

T2

[构造] [贪心]

设$leaf$为叶子数量，则答案为$\lceil \frac{leaf}{2} \rceil$

考虑构造，先随便dfs一次，把所有叶子按dfs序排序，每次取第$i$个叶子和第$i + \frac{leaf}{2}$个叶子连边即可

Proof

T3

[贪心] [堆]

sol写得很好：

Sol

需要注意，算答案的时候两种类型的点都要一起合，不能只合$a < b$的；以及operator <要注意细节问题

Code

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;

int N, A[MAXN + 5], B[MAXN + 5];
vector <int> G[MAXN + 5];

struct info
{
	int x, a, b;

	info (int _x = 0, int _a = 0, int _b = 0) { x = _x, a = _a, b = _b; }

	inline bool operator < (const info &rhs) const
	{
		int op0 = (a <= b), op1 = (rhs.a <= rhs.b);
		if (op0 != op1) return op0 < op1;
		if (!op0)
		{
			if (b != rhs.b) return b < rhs.b;
			if (a == rhs.a) return 0;
			return a < rhs.a;
		}
		else
		{
			if (a != rhs.a) return a > rhs.a;
			if (b == rhs.b) return 0;
			return b < rhs.b;
		}
	}
};

namespace DSU
{
	int fa[MAXN + 5];
	inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i; }
	inline int get_fa (int x) { return x == fa[x] ? x : fa[x] = get_fa (fa[x]); }
	inline void link (int x, int f) { x = get_fa (x), f = get_fa (f); fa[x] = f; }
}

int fa[MAXN + 5];

inline void dfs_pre (int x)
{
	sort (G[x].begin(), G[x].end());
	for (int i = 0; i < G[x].size(); ++i)
	{
		int y = G[x][i];
		if (y == fa[x]) continue;
		fa[y] = x;
		dfs_pre (y);
	}

	if (fa[x]) G[x].erase (lower_bound (G[x].begin(), G[x].end(), fa[x]));
}

inline void Init ()
{
	DSU :: init ();

	dfs_pre (1);
	static priority_queue <info> Q;
	static int vis[MAXN + 5];
	for (int i = 2; i <= N; ++i) Q.push (info (i, A[i], B[i]));

	while (!Q.empty())
	{
		int x = Q.top().x, a = Q.top().a, b = Q.top().b; Q.pop();

		if (vis[x]) continue;
		vis[x] = 1;

		int f = DSU :: get_fa (fa[x]), _a = A[f], _b = B[f];
		if (f && info (f, _a, _b) < info (x, a, b))
		{
			DSU :: link (x, f);
			A[f] = max (_a, _a - _b + a);
			B[f] = A[f] - _a + _b - a + b;
			Q.push (info (f, A[f], B[f]));
		}
	}

	for (int i = 1; i <= N; ++i) if (DSU :: get_fa (i) != i) G[DSU :: get_fa (i)].insert (G[DSU :: get_fa (i)].end(), G[i].begin(), G[i].end());
}

inline void Solve ()
{
	Init ();

	static priority_queue <info> Q;
	Q.push ((info) {1, A[1], B[1]});

	int ans = 0, res = 0;
	while (!Q.empty())
	{
		int x = Q.top().x, a = Q.top().a, b = Q.top().b; Q.pop();

		res -= a;
		if (res < 0) Chkmax (ans, -res);
		res += b;

		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			if (DSU :: get_fa (y) != y) continue;
			Q.push (info (y, A[y], B[y]));
		}
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 2; i <= N; ++i) A[i] = read<int>(), B[i] = read<int>();
	for (int i = 1; i < N; ++i)
	{
		int x = read<int>(), y = read<int>();
		G[x].pb (y);
		G[y].pb (x);
	}
}

signed main()
{

#ifdef hk_cnyali
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

10-16

Process

今天考了杨光的题，T1简单容斥计数，T3可以找规律，T2是个有点难的数据结构题

写了270分，T2因为常数问题挂掉了17分

T1

[容斥] [计数]

先把所有点排序， 设 $f_i$ 表示从原点到$i$号点，不经过其他障碍点的方案数。它就等于总方案减去其他障碍点的方案。可以枚举第一个碰到的是哪个障碍来计算。最后答案就是总方案减$\sum f_i$

T2

[bitset] [扫描线]

把每个正方形放到其左下角的点处统计答案， 对每种颜色计算哪些正方形能覆盖到它。只有一个点$(a, b)$时，$x \in [a, a + k - 1], y\in [b - k + 1, b]$的所有点都能覆盖。但如果有多个点的话，直接算就会算重

考虑扫描线（从上往下依次加行），每种颜色维护一个bitset。每新加一行的第$j$列元素$A_{i, j}$时，在对应颜色的bitset中找到第$j$列的前驱和后继，这样就知道这次操作真正会贡献的位置了。

扫描线在删除时会有小问题，因为你并不知道把这个点删掉后，是否还存在一个位于这一列的点。（即在同一列有多个点）这个问题很好解决，预处理$g[i][j]$表示从$(i, j)$往下的$K$个位置是否有和$A_{i, j}$相同的值即可

具体实现时，维护每一行的差分标记，每次做一遍前缀和即可

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 3000;
const int MAX_VAL = 1e5;

int N, M, K;
int A[MAXN + 5][MAXN + 5];
int Down[MAXN + 5][MAXN + 5];

inline void Init ()
{
	static int buc[MAX_VAL + 5];
	for (int i = 1; i <= MAX_VAL; ++i) buc[i] = INT_MAX;
	
	for (int j = 1; j <= M; ++j)
	{
		for (int i = N; i >= 1; --i)
		{
			if (buc[A[i][j]] - i <= K) Down[i][j] = 1;
			buc[A[i][j]] = i;
		}

		for (int i = 1; i <= N; ++i) buc[A[i][j]] = INT_MAX;
	}
}

bitset <MAXN + 5> L[MAX_VAL + 5], R[MAX_VAL + 5];

int delta[MAXN + 5];

inline int get_pre (int id, int x) { return M - (int) L[id]._Find_next (M - x); }

inline int get_next (int id, int x) { return (int) R[id]._Find_next (x); }

inline void Solve ()
{
	Init ();

	static int cur[MAXN + 5];
	int ans1 = 0; LL ans2 = 0;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			int c = A[i][j];
			int l = max (1, max (j - K + 1, get_pre (c, j) + 1)), r = min (j, get_next (c, j) - K);

			if (l <= r && !R[c][j]) ++cur[l], --cur[r + 1];
			L[c][M - j] = R[c][j] = 1;
		}

		if (i > K)
		{
			for (int j = 1; j <= M; ++j)
			{
				int c = A[i - K][j], x = i - K, y = j;
				int l = max (1, max (y - K + 1, get_pre (c, y) + 1)), r = min (y, get_next (c, y) - K);
				if (!Down[x][y]) L[c][M - y] = R[c][y] = 0;
				if (l <= r && !R[c][y]) --cur[l], ++cur[r + 1];
			}
		}

		if (i >= K)
		{
			for (int j = 1; j <= M - K + 1; ++j)
			{
				delta[j] = cur[j] + delta[j - 1];
				Chkmax (ans1, delta[j]);
				ans2 += delta[j];
			}
		}

	}

	cout << ans1 << ' ' << ans2 << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();

	for (int i = 1; i <= N; ++i) for (int j = 1; j <= M; ++j) A[i][j] = read<int>();
}

int main()
{

	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}

T3

把逆矩阵打出来找规律后不难发现，第$i$行$j$列的值的平方就是$\big(C_i^j\big)^2 \times i^{2m}$

再找找规律发现$\sum_j \big(C_i^j\big)^2$就等于$\binom{2i}{i} - 1$，直接计算即可

10-17

Process

今天是dy的题，开场先把T3模板题写了，然后就一直在想T2正解。最后没想出来，就只有最裸的暴力分了

T1

[博弈] [拓扑排序]

和这道题几乎一模一样

T2

[bfs] [并查集]

需要桶排，直接sort会被卡常

T3

[CDQ分治]

考虑每个询问/修改在生效时产生的贡献，是个比较裸的三维偏序，直接cdq分治即可

10-18

Process

想了一会儿T1无果，然后先开的T2，发现是思博题。最后T1写了个暴力加了点剪枝，T3写了个线性基的暴力就交了。没想到T1居然A了。。。数据太水了。。。

T1

[堆] [数据结构]

考虑对每个值预处理出答案。用大根堆维护一些值域上的连续段，每个段维护两个信息：长度和初始值域上的起始位置（堆以长度为关键字）。即一开始只有(max_val, 1)这一个段。

对于每个操作$x$，只需要找到长度$\ge x$的段，暴力拆开。因为每次拆开后，上半部分的段就一定会沉到最底下。

这样做复杂度是对的，因为每个段长度至少为$1$，所以总共最多切$O(max\_val)$次

T2

[矩阵快速幂]

直接矩阵快速幂

T3

[线性基] [分治] [树]

如果有$n$个数，其线性基内元素可以异或出$k$，则异或和为$k$的方案数等于$2^{n - x}$，其中$x$为线性基内元素个数；否则为0

因为线性基只能合并无法删除，考虑如何把原树扣掉一条链合并出出来

定义逆序遍历为，把每个点的儿子都reverse后的遍历

先考虑$x$是$y$祖先的情况：求出原树的后续遍历，以及逆后序遍历。那么$x$到$y$的路径就是后序遍历在y之前的点（红色 + 绿色） 并上 逆后序遍历在y之前的点(紫色 + 绿色) 并上 x的所有祖先

---

当$x$和$y$没有祖先关系时（假设$x$在$y$左边），$x$左边和$y$右边的部分，以及$lca$上面的部分都很好算。但是还有一部分是$lca$子树内，在$x$右边且$y$左边的部分。这一部分可以由dfs序以及逆dfs序的一段连续的区间拼凑起来

对于这些连续区间的询问，我们可以离线分治处理，也可以用猫树（其实就是把分治结构预处理出来）在线回答

总复杂度$O(\log^2 n)$

Code (6.8K)

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;
const int MAXM = 4e5;
const int MAX_VAL = 32767;
const int MOD = 998244353;

int N, M, W[MAXN + 5];
vector <int> G[MAXN + 5];

namespace HLD
{
	int fa[MAXN + 5], dep[MAXN + 5], size[MAXN + 5], son[MAXN + 5];
	int top[MAXN + 5], dfn[MAXN + 5], idfn[MAXN + 5], dfs_clock;

	inline void dfs (int x)
	{
		dep[x] = dep[fa[x]] + 1;
		size[x] = 1;
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			if (y == fa[x]) continue;
			fa[y] = x;
			dfs (y);
			size[x] += size[y];
			if (size[y] > size[son[x]]) son[x] = y;
		}
	}

	inline void dfs (int x, int now)
	{
		idfn[dfn[x] = ++dfs_clock] = x;
		top[x] = now;
		if (son[x]) dfs (son[x], now);
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			if (y == fa[x] || y == son[x]) continue;
			dfs (y, y);
		}
	}

	inline void init () { dfs (1), dfs (1, 1); }

	inline int get_lca (int x, int y)
	{
		while (top[x] != top[y])
		{
			if (dep[top[x]] < dep[top[y]]) swap (x, y);
			x = fa[top[x]];
		}
		if (dep[x] > dep[y]) swap (x, y);
		return x;
	}

	inline int get_dis (int x, int y) { return dep[x] + dep[y] - 2 * dep[get_lca (x, y)] + 1; }

	inline int get_son (int x, int anc)
	{
		int d = dep[anc] + 1;
		while (dep[top[x]] > d) x = fa[top[x]];
		return idfn[dfn[x] - (dep[x] - d)];
	}
}

using HLD :: size;
using HLD :: get_lca;
using HLD :: get_dis;
using HLD :: get_son;
using HLD :: get_son;

struct basis
{
	static const int MAX_LEN = 15;

	int A[MAX_LEN + 1], cnt;

	inline void init () { memset (A, 0, sizeof A); cnt = 0; }

	basis () { init (); }

	inline int insert (int x)
	{
		for (int i = MAX_LEN; i >= 0; --i)
		{
			if (!(x & (1 << i))) continue;
			if (!A[i])
			{
				for (int j = 0; j < i; ++j) if (x & (1 << j)) x ^= A[j];
				for (int j = i + 1; j <= MAX_LEN; ++j) if (A[j] & (1 << i)) A[j] ^= x;
				A[i] = x;
				++cnt;
				return 1;
			}
			x ^= A[i];
		}
		return 0;
	}

	inline int query (int x)
	{ 
		for (int i = MAX_LEN; i >= 0; --i)
			if (x & (1 << i))
			{
				if (!A[i]) return 0;
				x ^= A[i];
			}
		return 1;
	}
	
	inline basis operator + (const basis &rhs) const
	{
		basis now = *this;
		for (int i = 0; i <= MAX_LEN; ++i) if (rhs.A[i])
			now.insert (rhs.A[i]);
		return now;
	}

};

struct Graph
{
	int dfn[MAXN + 5], idfn[MAXN + 5], dfs_clock;
	basis prefix[MAXN + 5];

	inline void dfs (int x, int f)
	{
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			if (y == f) continue;
			dfs (y, x);
		}

		idfn[dfn[x] = ++dfs_clock] = x;

		prefix[dfs_clock] = prefix[dfs_clock - 1], prefix[dfs_clock].insert (W[x]);
	}

	inline void init (int op)
	{
		if (op) for (int i = 1; i <= N; ++i) reverse (G[i].begin(), G[i].end());

		dfs (1, 0);

		if (op) for (int i = 1; i <= N; ++i) reverse (G[i].begin(), G[i].end());
	}

} Gra[2];

int dfn[2][MAXN + 5], idfn[2][MAXN + 5], dfs_clock[2];
basis prefix[MAXN + 5];

inline void dfs0 (int x, int f)
{
	idfn[0][dfn[0][x] = ++dfs_clock[0]] = x;
	prefix[dfs_clock[0]] = prefix[f], prefix[x].insert (W[x]);

	for (int i = 0; i < G[x].size(); ++i)
	{
		int y = G[x][i];
		if (y == f) continue;
		dfs0 (y, x);
	}
}

inline void dfs1 (int x, int f)
{
	idfn[1][dfn[1][x] = ++dfs_clock[1]] = x;

	reverse (G[x].begin(), G[x].end());

	for (int i = 0; i < G[x].size(); ++i)
	{
		int y = G[x][i];
		if (y == f) continue;
		dfs1 (y, x);
	}
	
	reverse (G[x].begin(), G[x].end());
}

inline void Init ()
{
	Gra[0].init (0), Gra[1].init (1);
	dfs0 (1, 0), dfs1 (1, 0);
	HLD :: init ();
}

int K[MAXN + 5];
basis Ans[MAXN + 5];

struct query
{
	int l, r, id;
	query (int _l = 0, int _r = 0, int _id = 0) { l = _l, r = _r, id = _id; }
};

namespace DIV
{
#define mid ((l + r) >> 1)

	inline void solve (int l, int r, vector <query> res, int op)
	{
		if (!res.size()) return ;

		if (l == r)
		{
			for (int i = 0; i < res.size(); ++i)
			{
				int id = res[i].id;
				Ans[id].insert (W[idfn[op][l]]);
			}
			return ;
		}

		static basis A[MAXN + 5], B[MAXN + 5];
		vector <query> L, R; L.clear(), R.clear();

		A[mid + 1].init (), B[mid].init ();
		for (int i = mid; i >= l; --i) A[i] = A[i + 1], A[i].insert (W[idfn[op][i]]);
		for (int i = mid + 1; i <= r; ++i) B[i] = B[i - 1], B[i].insert (W[idfn[op][i]]);

		for (int i = 0; i < res.size(); ++i)
		{
			int ql = res[i].l, qr = res[i].r, id = res[i].id;
			if (ql > qr) continue;
			if (ql <= mid && mid <= qr) Ans[id] = Ans[id] + A[ql] + B[qr];
			else
			{
				if (qr < mid) L.pb (res[i]);
				else R.pb (res[i]);
			}
		}

		solve (l, mid, L, op), solve (mid + 1, r, R, op);
	}

#undef mid
}

query Que[MAXN + 5];

inline void Solve ()
{
	Init ();

	static vector <query> Q[2];

	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>(), k = read<int>(), lca = get_lca (x, y); 
		if (dfn[0][x] > dfn[0][y]) swap (x, y);
		Que[i] = query (x, y, k);

		if (lca == x)
		{
			Ans[i] = Gra[0].prefix[Gra[0].dfn[y] - 1] + Gra[1].prefix[Gra[1].dfn[y] - 1] + prefix[dfn[0][lca] - 1];
			continue;
		}

		Ans[i] = Gra[0].prefix[Gra[0].dfn[x] - 1] + Gra[1].prefix[Gra[1].dfn[y] - 1] + prefix[dfn[0][lca] - 1];

		int ls = get_son (x, lca), rs = get_son (y, lca);

		Q[0].pb (query (dfn[0][x] + size[x], dfn[0][rs] - 1, i));
		Q[1].pb (query (dfn[1][y] + size[y], dfn[1][rs] + size[rs] - 1, i));
	}

	for (int k = 0; k < 2; ++k) DIV :: solve (1, N, Q[k], k);

	static int pw[MAXN + 5];
	pw[0] = 1;
	for (int i = 1; i <= MAXN; ++i) pw[i] = (LL) pw[i - 1] * 2 % MOD;

	for (int i = 1; i <= M; ++i)
	{
		int x = Que[i].l, y = Que[i].r, k = Que[i].id;
		int all = N - get_dis (x, y);

		if (Ans[i].query (k)) printf("%d\n", pw[all - Ans[i].cnt]);
		else puts("0");
	}
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i < N; ++i)
	{
		int x = read<int>(), y = read<int>();
		G[x].pb (y);
		G[y].pb (x);
	}
	for (int i = 1; i <= N; ++i) W[i] = read<int>();
}


int main()
{

#ifdef hk_cnyali
	freopen("celebration.in", "r", stdin);
	freopen("celebration.out", "w", stdout);
#endif


	Input ();
	Solve ();

	return 0;
}

10-20

Process

花了将近一个小时才写完T1，不知道怎么回事看错了数据范围，把3e5看成2e5了，炸成$50$。T2花了一点时间，大概在11:20左右拍上了。T3没来得及写

T1

发现$n>7$时肯定能凑出来0，直接输出，否则爆搜

T2

[KMP] [二分] [Hash]

总方案减去重复的

对于$t$的每个前缀，求出其在$s$中的出现次数prefix[i](二分哈希求)。再对$t$串kmp一下，此时多算的部分就是prefix[i - fail[i]]

T3

[动态规划] [直径] [树]

sol from GC

把一条边删掉后，连边后树的最长链要么是两个连通块内的最长链，要么就会过加上的这条边，而这条边的端点一定是两个连通块最长链的中点(加权中点)。

只需要考虑最长链上的边，因为其他边删掉后答案是原直径

枚举最长链上的每条边 $(u, v)$

• 对于第一种情况，沿着链正反两次树形 dp 就可以解决。

• 对于第二种情况，分开对断边后形成的两个联通块进行考虑，链上的点 $a$ 作为新边端点时，其所在联通块内以它为根的最长链为

  1. 它到原最长链端点

  2. 它往 $(u,v)$ 方向走并在中途转向叶子结点

  这两种情况中的较大值，而我们要最小化这个。可以发现随着 $(u,v)$ 的变化，最优点 $a$ 的变化是单调的，所以预处理链上每个结点到叶子的最长路，求链上每条边两端联通块的最优点 $a$ ，再连起来与第一种情况的答案 chkmax 即可。

时间复杂度 $O(n)$, 具体细节见代码吧

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e6;
const int MAXM = 4e6;
const int MOD = 998244353;

int N, e = 1, Begin[MAXN + 5], To[MAXM + 5], Next[MAXM + 5], W[MAXM + 5];

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

namespace INPUT
{
	typedef unsigned long long ULL;
	int B,D;
	ULL num;
	inline ULL get ()
	{
		num ^= (num << 13);
		num ^= (num >> 17);
		num ^= (num << 5);
		return num;
	}
	inline void gen() 
	{
		scanf("%d%llu%d%d",&N,&num,&B,&D);
		for (int i = 2; i <= N; ++i)
		{
			int a = get() % min (i - 1, B) + i - min (i - 1, B);
			int b = get() % D;
			add_edge (a, i, b);
			add_edge (i, a, b);
		}
	}
}

namespace DIAMETER
{
	int o;
	LL maxdep;

	inline void dfs (int x, int f, LL d)
	{
		if (Chkmax (maxdep, d)) o = x;

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (y == f) continue;
			dfs (y, x, d + W[i]);
		}
	}

	int stk[MAXN + 5], top;
	int stk_id[MAXN + 5], top_id;
	int D[MAXN + 5], Id[MAXN + 5];

	inline void dfs_path (int x, int t, int f)
	{
		if (D[0]) return ;
		stk[++top] = x;

		if (x == t)
		{
			int _top = top;
			while (_top) D[++D[0]] = stk[_top--];
			_top = top_id;
			while (_top) Id[++Id[0]] = stk_id[_top--];
			return ;
		}

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (y == f) continue;

			stk_id[++top_id] = i >> 1;
			dfs_path (y, t, x);
			--top_id;
		}

		--top;
	}

	inline void work ()
	{
		o = maxdep = 0; dfs (1, 0, 0);
		int p = o; 
		maxdep = 0; dfs (o, 0, 0);
		dfs_path (p, o, 0);
	}
}

using DIAMETER :: D;
using DIAMETER :: Id;

int is_key[MAXN + 5];
LL dis[2][MAXN + 5], to_leaf[2][MAXN + 5]; // dis: 到直径端点的距离，to_leaf: 到最远的叶子的距离
LL f[2][MAXN + 5], g[2][MAXN + 5]; // f: 子树内直径, g: 以它为端点的直径

inline void dfs (int x, int fa, int op)
{
	LL max = 0, sec = 0;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];

		if (y == fa) continue;

		dfs (y, x, op);

		if (is_key[x] && is_key[y]) dis[op][x] = dis[op][y] + W[i];
		if (!is_key[y]) Chkmax (to_leaf[op][x], to_leaf[op][y] + W[i]);

		Chkmax (f[op][x], f[op][y]);
		if (g[op][y] + W[i] > max) sec = max, max = g[op][y] + W[i];
		else if (g[op][y] + W[i] > sec) sec = g[op][y] + W[i];
	}

	Chkmax (f[op][x], max + sec);
	g[op][x] = max;
}

LL Ans[MAXN + 5];

inline void Solve ()
{
	DIAMETER :: work ();
	for (int i = 1; i <= D[0]; ++i) is_key[D[i]] = 1;

	dfs (D[D[0]], 0, 0);
	dfs (D[1], 0, 1);

	static LL diam[2][MAXN + 5], _max;
	
#define calc(a) max(dis[0][D[a]], _max - dis[0][D[a]])
	for (int i = 1, a = 1; i < D[0]; ++i)
	{
		int x = D[i];
		Chkmax (_max, dis[0][x] + to_leaf[0][x]);
		while (a < i && calc (a) > calc (a + 1)) ++a;
		diam[0][x] = calc (a);
	}
	
#undef calc
#define calc(a) max(dis[1][D[a]], _max - dis[1][D[a]])
	_max = 0;
	for (int i = D[0], a = D[0]; i > 1; --i)
	{
		int x = D[i];
		Chkmax (_max, dis[1][x] + to_leaf[1][x]);
		while (a > i && calc (a) > calc (a - 1)) --a;
		diam[1][x] = calc (a);
	}

#undef calc

	for (int i = 1; i < N; ++i) Ans[i] = DIAMETER :: maxdep;
	for (int i = 1; i < D[0]; ++i)
	{
		int x = D[i], y = D[i + 1], id = Id[i];
		Ans[id] = max (max (f[0][x], f[1][y]), diam[0][x] + diam[1][y] + W[id << 1]);
	}

	LL ans = 0;
	for (int i = 1; i < N; ++i) ans ^= (LL) i * (Ans[i] % MOD) % MOD;

	cout << ans << endl;
}

inline void Input () { INPUT :: gen (); }

int main ()
{

	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}

10-21

Process

这场考得比较正常，T1T2都比较简单，T2写了个无脑李超树，T3考场上只会暴力，但实际上也不难

T1

要么取左端点要么取右端点

T2

[kruskal重构树] [李超线段树]

首先按点权从大到小建出kruskal重构树，对于每个 $\min\{a_i\}$ 求出最大的$n$。也就是求出来了若干个函数$f(x) = kx+b$，每次询问一个$x$，求所有函数的最大值。无脑李超树即可

T3

[线段树] [数据结构] [前缀和]

• 这个做法本质上是在优化暴力，即先从前往后考虑一次，再从后往前考虑一次

• $t_i = s_i + s_{l - 1} - \min\{s_j\}$，它的意义为，正着考虑完一遍$[l, r]$后的前缀和数组。$\max\{t_i - t_r\}$实际上就是要求每个后缀合法

• 设 $ans$ 表示$[l - 1, r]$中选出两个数使右边的减左边的最大的结果，那么

  $\begin{aligned} &\max\{t_i - t_r\} \\ =& \max\{t_i\} - t_r \\ =& \big(s_{l - 1} + ans \big) - \big(s_r + s_{l - 1} + \min\{s_i\}\big) \\ =& ans - s_{r} + \min\{s_i\} \end{aligned}$

  又因为答案还要加上$s_{l - 1} - \min\{s_i\}$，所以最后剩下 $ans - s_r + s_{l - 1}$

10-22

Process

这场打自闭了，搞了几乎一整场的T1，写了个假的树套树做法，到快考完的时候才发现是错的。T2一开始想了个贪心没调出来（实际上就是正解，只是细节有问题），后来搞了个乱搞A了。T3题都没看

T1

[线段树] [二分]

考虑依次确定每个位置的值。预处理出最大得分，那么当前这个位置填$>a_i$的数时，合法区间是一段前缀；填$\le a_i$的数时，合法区间也是一段前缀，于是可以二分。

如何快速判断是否合法？

把所有数（$a_i, b_i$）一起排序，按顺序建线段树。统计每个区间中有多少个$a_i$，多少个$b_i$，尽量多地在底层合并。 只需要支持单点修改。

大概是这个意思

inline void push_up (int o)
{
	int res = min (node[ls].sum[0], node[rs].sum[1]);
	node[o].ans = node[ls].ans + node[rs].ans + res;
	node[o].sum[0] = node[ls].sum[0] + node[rs].sum[0] - res;
	node[o].sum[1] = node[ls].sum[1] + node[rs].sum[1] - res;
}

T2

[树状数组] [贪心]

按权值从小到大考虑每个数，每次取往左/往右更小的那边走，用树状数组维护位置。权值相等的数要一起考虑

T3

[栈] [启发式合并] [堆]

排序，栈建树，设 $f(i,j)$ 表示在以 $i$ 为根的子树内所选择的第 $j$ 层的最大权值和。显然对于确定的 $i$ 而言 $f(i,j)$ 单调递减，然后按照深度启发式合并，每次将子树的信息直接相加，再将根的权值丢入堆作为新增一层的抉择即可。

10-23

Process

今天考得比较正常，只是T1花的时间太长了，一个半小时才写完，开始一直卡在如何区间加等差数列上了，想半天才发现可以二阶差分。T2一开始只会暴力，一步步优化之后A了。T3没时间做了，就写了个暴力

T1

[差分]

动态维护答案，$(d - x)^2 = d^2 - 2dx + x^2$，分别维护这三项的和即可

T2

[最短路] [FWT] [子集和DP]

先对每个关键点求一遍单源最短路，那么我们就知道对于每个点而言，在某些关键点中只要选了任意一个，就不满足题意了

然后补集转化，设 $F(S)$ 表示在只保留 $S$ 中的关键点的前提下一共有多少个点不可在 $T$ 时间内到达，然后就能子集和 DP 了，也可以FWT

T3

考虑把操作倒过来，看作从$1\sim n$的排列，入栈出栈后，能构成多少种不同的排列，且第$pos$位为$x$

注意，需要将pos = n - pos + 1, x = n - x + 1

定义$Catalan(n, m) = \binom{n + m}{m} - \binom{n + m}{m - 1}$, 它的意义为，用$n$个左括号，$m$个右括号能凑出多少种合法的括号序列（任意前缀左括号数$\ge$右括号数）

枚举位置在$pos$之前，且权值大于$x$的数的个数$i$，那么这$i$个数一定是$x + 1 \sim x + i$（证明不难），即这$i$个数需要构成合法的括号序列，方案为$Catalan(i, i)$。剩下在$pos$前的数中，还剩下$pos - i - 1$个数，它们的权值比$x$要小。而在$x$之前已经有$x-1$个数入栈了，所以相当于要求$x-1$个左括号，$pos - i - 1$个右括号能构成多少种括号序列，方案数为$Catalan(x - 1, pos - i - 1)$

最后考虑位置在$pos$后的数，它们有一部分的权值比$x$小，一部分比$x$大。那么相当于钦定了一部分左括号放在最前面，并且后面有一些任意填的左括号和右括号需要组合。所以最后这一部分可以倒着考虑，即先不考虑权值比$x$小的那些左括号，而是考虑剩下的右括号如何和左括号匹配。考虑完这些括号之后，权值比$x$小的那些左括号就自然匹配上了。方案数为$Catalan (n - pos, n - x - i)$

Code

int ans = 0;
pos = n - pos + 1, x = n - x + 1;
for (int i = 0; i <= n; ++i)
	ADD (ans, (LL) Catalan (i, i) * Catalan (x - 1, pos - 1 - i) % MOD * Catalan (n - pos, n - x - i) % MOD);
cout << ans << endl;

10-24

Process

今天题目中规中矩，都是中等偏简单一点的题目，感觉三道题都在考算法，会这个算法就能秒掉，不会就没了

T1

[tarjan] [点双] [缩点]

先tarjan求一遍点双，标记连接点双的环，若存在一条连接点双内的两点，且不在环上的边，则该点双不合法

注意在点双内遍历出边时，不能遍历割点的出边，因为割点可能被算多次复杂度。

T2

[AC自动机] [矩阵快速幂] [动态规划]

AC自动机模板题

暴力DP是$dp[i][j]$表示到$i$节点，已经填了$j$个字母的答案。对AC自动机上每个点预处理fail树上所有祖先的权值和，直接转移即可

然后显然可以矩乘优化，把普通矩乘的*、+变成+、max即可

T3

[线段树] [线段树优化建边] [拓扑排序]

暴力做法是对于这$k$个点，直接向$[l, r]$内的其他点连边，然后直接拓扑排序。线段树优化建边即可

10-25

Process

考得比较差，T2很简单的题想了很久才想出来，T3又没时间做了。时间分配上还是存在比较大的问题。只有20天了，赶快抓紧时间调整状态

T1

枚举$c$，把$a * b$加到map中，每次查$\frac{1}{c}$即可。需要注意本质不同相关的一些细节

T2

[二分答案] [动态规划]

把物品和背包从小到大排序，那么就是要在物品序列上选出尽量长的子序列满足题意

因为背包一定是取一段后缀，所以可以先二分答案，转化成判定性问题，再贪心地对物品权值从小到大这个限制做dp即可

T3

[动态规划] [背包]

设 $dp[i][j]$ 表示深度至多为$i$，由$j$个点构成的有根树的数目，答案就是$dp[i][n] - dp[i - 1][n]$

考虑编号从大到小加点，每次相当于把若干个$i-1$的树选出来构成一个森林，再把当前点作为根把这片森林连起来

显然选的过程可以用完全背包转移:

假设当前有一个大小为$j$的森林$A$，要往其中加入一个大小为$k$的树$B$。钦定$B$的根的编号为的所有点中最小的（否则会算重），然后只需要在$j + k - 1$个编号中选$k - 1$个给$B$的子树即可。因为$A$中编号的相对大小关系已经确定了（实际上本身它们的编号是确定的，不过是相对于$j$个点来说的，而现在需要扩展到$j + k$个点）

代码长这样

for (int j = 0; j <= N; ++j) if (g[j])
	for (int k = 1; j + k <= N; ++k) if (dp[k])
		Add (g[j + k], (LL) g[j] * dp[k] % MOD * C (j + k - 1, k - 1) % MOD);

g是临时转移数组。注意需要先枚举$j$再枚举$k$，因为用到的g[j]必须是完整的

10-26

Process

考得还算正常，T1一开始没看清楚题，花了40分钟左右；T2是个已经烂大街的套路；T3题面写得太*，没看懂

T1

直接差分即可

T2

[高斯消元] [树上高消]

根据树上高消的套路，把$f[x]$写成f[x] = A[x] * f[fa] + B[x] * f[anc] + C[x]的形式即可

时间复杂度$O(n)$

T3

看懂题意之后就变成sb题了

题目就是要求满足$d = \sum_{i = 1}^m |d - i| \times \frac{w_i}{\sum w}$ 的$d$

也就是$\sum_{i = 1}^m |d - i| \times w_i - \sum w\times d = 0$

把它看成一个函数，发现当$d$增加的时候，前面那一堆的变化量小于等于后面的变化量，所以它是单调不升的，即可以二分

因为$d$可能是小数，不好直接二分。但可以先二分$d$的整数部分，然后可以将绝对值去掉，再直接解一个一元一次方程

用树状数组动态维护一下上面那个函数即可（维护$\sum_{i=1}^d w_i$和$\sum_{i=1}^d w_i * i$）

10-27

Process

被gc爆踩！T2睿智$n^2$DP居然想不出来。。。

T1

[容斥]

直接容斥，对列容斥，行的方案数可以直接算

$ans = sum_{i} \binom{n}{i} (2^i - 1) ^ m$

T2

[动态规划] [k-d tree]

考场降智。显然每个点最多被两条线段覆盖。区间按右端点排序，$dp[i][j]$表示放到第$i$个区间，上一个放的区间为$j$的答案，暴力转移是$O(n^3)$的，前缀最小值优化即可，复杂度$O(n^2)$

我考场上的做法是不记第二维状态，而是记录到DP的值中，但是这是错的，但在外面套一个二分就对了。然后里面的dp就变成了一个二维数点，KDT即可。复杂度$O(n \log n \sqrt n)$的

T3

咕咕咕

10-28

Process

爆零了，T2睿智题考场上想复杂了其实是没想清楚，调到考试结束才调出来

T1

扫雷大模拟

T2

[dsu on tree] [启发式合并]

我的做法可以对每个$u$求出答案，但是做法很复杂现在也想不清了

判断子树/挖掉子树是否可行可以dsu on tree，求最长路径直接换根dp

T3

咕咕咕

10-29

Process

肝了一整场T1，一开始没想清楚导致最后没调出来

T1

[概率和期望] [毒瘤]

期望很好算，根据期望的线性性直接算每个格子的期望，再求和即可

具体计算方法： 设$a$为它周围的空位数量，$b$为它周围的雷的数量，则它的贡献为

$\sum_{i=0} ^ {a} \binom{a}{i} \binom{n * m - k - a - 1}{w - k - i} \times (b + i)$

方差还是转化成平方期望减期望平方，平方期望的式子直接拆开：

$E\big((\sum_{i=1}^{n}x_i)^2\big) = \sum_{i=1}^{n}\sum_{j=1}^{n}E(x_ix_j)$

只要快速计算$E(x_ix_j)$即可

发现$x_ix_j$不独立，不能拆开，只能合一起算。具体计算方法与求期望方法类似，详见代码

直接这样做是$O((nm)^2)$的，预处理一些东西，再动态维护一些东西就能做到$O(nm)$了，细节就不具体展开了。。。

T3

[字符串] [AC自动机]

建出trie，发现trie树上只要有祖孙关系的两点一定不能同时选

先考虑前缀两两不包含的情况，那么求出trie树的深度就是答案（同一深度的点可以同时选）

若前缀有包含，建出AC自动机后，在trie树的基础上，从fail[x]向x连边，求DAG最长链即为答案。（因为fail链上的点不能同时选）

Solution

10-30

Process

T1很快写完，然后就在搞T3，搞了很久搞了89分。T2没什么思路

T1

[线段树] [set]

直接暴力做，把相同的一起做即可。复杂度可以均摊分析。

写的时候再一次用线段树代替了set，细节少很多

T2

[树]

维护答案集合（有人的点的集合），发现每次会把叶子缩起来（还有可能新加一个点），模拟一下这个过程即可

T3

[组合数学] [打表]

考虑一些子问题：

• $(0, 0)$走到$(n, m)$的方案数：$\displaystyle G(n, m) = \binom{n + m}{n}$

• $(0, 0)$走到第$n$行第$i$列($i \le m$)的方案和：$\displaystyle \sum_{i=0}^{m} G(n, i) = G(n + 1, m)$

• $(0, 0)$走到第$i$行第$j$列($i \le n, j \le m$)的方案和：$\displaystyle \sum_{i=0}^{n} \sum _{j = 0} ^{m} G(i, j) = G(n + 1, m + 1) - 1$

• $(0, 0)$走到矩形$(x_1, y_1), (x_2, y_2)$的方案和：$\displaystyle \sum_{i=x_1}^{x_2} \sum _{j = y_1} ^{y_2} G(i, j) = G(x_2 + 1, y_2 + 1) - G(x_2 + 1, y_1) - G(x_1, y_2 + 1) + G(x_1, y_1)$

那么在不考虑矩形B的情况下，从矩形A走到矩形C的方案数就可以利用上面最后一个式子，通过$O(16)$枚举两个矩形的边界计算

考虑在此基础上计算经过矩形B的方案数，枚举在走的过程中先碰到矩形B的哪个点，发现只可能在左边界或下边界上，因为这个范围很小所以可以直接暴力枚举统计

最后再优化一下组合数，分块打表就能通过了

10-31

Process

开场先找了T2的规律，然后去写T3的部分分，本来想写个乱搞的，结果想着想着就想出来正解了。T1最后十几分钟看了下，发现和xcy之前讲的那道题很像，但想不清正确性，最后没时间了就还是贴了个上去，没想到A掉了。。。

T1

就是这道题，只不过这里先按$g$从大到小排个序就行了

T2

通过找规律发现$D(n, k) = \sum_{i=0}^{k}\binom{n}{i}$，组合数随便拆开算算就行了

T3

按P的顺序去填A，贪心填就行了（讲不清楚，不如看代码）

Code

for (int i = 1; i <= N; ++i) A[P[i]] = - (N - i + 1);

for (int i = 1; i <= N; ++i)
	if (K > (Q[i] - 1)) K -= Q[i] - 1, B[Q[i]] = 0;
	else
	{
		puts("Yes");

		static int buc[MAXN + 5];
		for (int j = 1; j < Q[i]; ++j) buc[j] = -A[j];
		nth_element (buc + 1, buc + K, buc + Q[i], greater <int>());
		B[Q[i]] = buc[K] - 1;

		for (int j = i + 1; j <= N; ++j) B[Q[j]] = N;

		for (int j = 1; j <= N; ++j) printf("%d ", A[j]); puts("");
		for (int j = 1; j <= N; ++j) printf("%d ", B[j]); puts("");
		exit (0);
	}