现实：已经自闭了

感觉远古场都是 AB 力度比较大，但是后面的题难度上不去。。

A

首先发现 $K_n$ 的三元环个数是 $\binom n 3$，我们先找到最大的 $n$ 满足 $\binom n 3 \leq m$，在题目限制内一定存在这样的 $n$。

剩下的怎么做呢？我们可以建个新点，发现如果新点连向 $x$ 个完全图上的点就会带来 $\binom x 2$ 个三元环。

可以轻松证明一定能用不超过 $100$ 个点表示出来。

B

设 $c_i$ 表示第 $i$ 列黑色的个数，容易发现 $c_i = c_{i+k} = c_{i+2k} \ldots$

所以我们就把 $m$ 缩成了和 $n$ 同阶的一个数，接下来 $O(n^4)$ dp 即可：$f_{i,j}$ 考虑了前 $i$ 列，用掉了 $j$ 个数，转移枚举下一列填多少个数。

C

画图找规律：

发现这个图主题是一条链+若干条边，是将一个 $D(n-1)$ 放在左边，$D(n-2)$ 放在右边，连一下 $1$ 和右边图的开头设这个边是 $e_1$，左边图的结尾和右边图的开头设这个边是 $e_2$。

首先发现后面的图的点想跑到前面必须走过 $e_2$，前面的点到后面的点可以跳到 $1$ 然后 $e_1$，也可以跳到 $|D(n-1)|$ 然后 $e_2$。

我们可以递归处理：首先 $n$ 最多只有 $80$，一个朴素的暴力是考虑我们当前询问在第 $n$ 层，点是 $u,v$，记为 $f(u,v,n)$，分类讨论一下：

• $u,v$ 都属于后面的图，直接递归到 $D(n-2)$ 做就行了。
• $u,v$ 一个属于前面，一个属于后面。那么 $u$ 可以选择先到达 $1$ 再走 $e_1$ 到达右边图然后转化为右边的子问题，或者是先到达 $|D(n-1)|$ 走 $e_2$ 到达右边的图。
• $u,v$ 都属于前面，这里不只能直接递归！可以让他们都跑到 $|D(n-1)|+1$ 汇合，所以也要枚举一下哪个去 $1$ 哪个去 $D(n-1)$

这样一次能分出来四五层时间直接爆掉了，所以我们要考虑优化。

我当时写了个记忆化（肯定只对 $u=1$ 或 $v=n$ 记忆化），然后 T 飞了，不知道为啥。

我们考虑分出的叉大多数是有一个点是 $1$ 或者 $|D(i)|$ 的情况，我们可以考虑预处理每个点在每层对应的点距离 $1$ 和 $|D(i)|$ 的情况。也是分类讨论一下：

• $u$ 在右边：到达 $|D(i)|$ 直接递归，到达 $1$ 要先到 $|D(i)|+1$ 然后走 $e_1$。
• $u$ 在左边：到达 $1$ 可以枚举是直接走到 $1$ 还是先走到 $|D(i)|$ 然后依次走 $e_2,e_1$ 到达，到达 $n$ 需要预处理 $D(i)$ 从 $1 \to |D(i)|$ 的最短路径 $d_i$ ，就变成一个查询如何到 $|D(i)|+1$ 的问题了。先枚举左边到达 $1$ 还是 $|D(i)|$ 走对应的边一步走过去，然后花费 $d_i$ 走到 $|D(n)|$。

D

两个区间合法等价于差分后的区间相等。

不能相交相当于限制了区间开头可以选取的区间。

相等相当于限制了两个后缀的 $\text{lcp}$。后缀数组+二维数点即可。

E

我们来考虑分治：每次取中间的一条线，考虑所有经过这条线的路径，在一个分治过程中我们只考虑跨过这条线的所有询问，只需要预处理 $f_{i,j,k}$ 表示点 $(i,j)$ 能否到达线上第 $k$ 个点（只往右往下），类似地 $g_{i,j,k}$ 表示点 $(i,j)$ 能否到达线上第 $k$ 个点（只往左往上），对于一组询问 $(x_1,y_1,x_2,y_2)$ 相当于是要判断是否存在一个 $k$ 满足 $f_{i,j,k} \text{and} g_{i,j,k} = 1$。直接分治是 $O(q \log n + n^3 \log n)$，发现那个预处理可以使用 bitset 优化，时间复杂度优化到 $O(q \log n + \frac{n^3}{\omega} \log n)$。