下分大失败？

A Splitting into digits

输出 $n$ 个 $1$。

B Game with string

栈模拟。

第一次插人失败很难受啊，还好是小号啊？

C Grid game

一个 $4 \times 4$ 的方格图，往里面填 $1 \times 2$ 和 $2 \times 1$ 两种方块，放完后每一行，每一列填满的话就删除，要求填的时候不能无处可填，求一个方案。

考虑这样一种填法，竖着的都放在最左边，横着的放在右边，这样每进来 $2$ 个竖的都会被消掉，进来的是横的每 $4$ 个会消掉，不会产生冲突。

D Game with modulo

猜模数 $a$，每次询问两个数 $x$ 和 $y$，得到 $x \text{ mod } a$ 和 $y \text{ mod } a$ 的大小关系。

如果 $x > a$，那么 $ x \text{ mod } a < {1 \over 2}x$，因此可以先倍增求出 $a$ 的范围，在这个范围内二分即可。

自闭了。

A Little Sub and Pascal’s Triangle

求杨辉三角第 $n$ 层的奇数个数。

组合数 $n \choose k$ 为奇数，充要条件为 $n \text{ AND } k = k$。

答案为 $2^p$，其中 $p$ 为 $n-1$ 二进制表示中 $1$ 的个数。

G Little Sub and Tree

I Little Sub and Isomorphism Sequences

两个序列同构的条件为：

1. 长度相同；

2. 每个数的出现次数相同。

维护两个操作：

1. 单点覆盖；

2. 询问全局两个同构的不同连续子序列的长度最大值，即满足
   $$
   a_{i},a_{i+1},\dots,a_{i+k-1} \
   a_{j},a_{j+1},\dots,a_{j+k-1}
   $$
   这两个不同的序列同构，询问 $k$ 最大值。

想一想发现，显然两个子序列同构肯定是共用 $k-1$ 个位置，那么维护一下每个数出现的最左边和最右位置，询问的时候 $set$ 里面维护最大距离即可。

证明一下：

考虑两个同构串共用了 $m$ 个位置，对于两个串的非共用部分，总能找到一对相同的数字，以这两个数字为端点，显然可以构造出一组更长的同构串，因此最优情况就是 $k-1$ 位置都共用了。

B 唐纳德先生与网络降级计划

有一个 $n$ 个点的无根树，现在要求给每条边定向，使得每个点的出度至多为 $1$，并且对所有 $1 \le i \le q$ 满足 $s_i$ 到 $t_i$ 有通路。

其实就是对每个路径定一个方向，最后考虑一下剩余的边，使得度数不大于 $1$。

对每个询问打一个标记，表示这个点往上走多少个需要被染色为某一个方向，离线后扫一遍即可。

$-1$ 写成 $+1$ 调了三个小时是怎么回事啊？

D 唐纳德先生与 .DOC

猜一发样例对了。

E 唐纳德先生与假骰子

猜一发样例对了。

咕咕咕了一个月的补题。

A 仰望星空

总共 $n$ 天，已知第一天权值为 $b$，最后一天权值为 $a$，每天权值不会增加，问一共有多少种可能的权值总和。

中间 $n-2$ 天的权值和的范围是 $[ (n-2) \times a, (n-2) \times b ]$，一共有 $(n-2)(b-a)+1$ 种。

B 清点星辰

$n$ 个点随机均匀地撒在 $1 \times 1$ 的矩形内，求最短距离的期望。

随机模拟，注意保证总的复杂度为 $1e8$。

C 她的名字

给一个长度为 $2000$ 的数字串，每次询问从母串中取出 $N$ 个字符，组成结尾为 $XY$ 的子序列方案数。

预处理每种数字的出现次数的后缀和。

预处理每一种 $XY$ 的情况，即每一个数字为 $X$ 的位置的后缀有多少 $Y$，前面有多少个数字。

对于每个询问，每个 $X$ 的位置 $pos$，对应后缀 $Y$ 的个数 $cnt$，答案为 $\sum {pos-1 \choose N-2 } \times cnt$。

注意保存一下重复的询问答案。

E 管理孩子

二分答案。

对于每个子树，维护一个权值：这棵子树中的某个节点最多还能够覆盖多少节点（+）或者这棵子树还有多少个顶点没有被覆盖到（-），可以用正负号表示这两种权值（不会同时出现）。

dfs 到某一个节点时，考虑这个节点所有儿子的权值，这些权值有正有负，所有负的权值的和，也就是这个子树总共还有多个点没有被覆盖。

显然最多只有一个带有正权值的儿子对这个子树的覆盖有贡献，因为如果覆盖到了根节点，那么其他正儿子就不能再覆盖根节点了（不联通），所以需要选择一个权值最大的正儿子。

如果正儿子权值比较大，就让这个顶点覆盖这个子树所有未覆盖顶点，然后将还能够覆盖的个数回溯到当前子树的父亲。

如果正儿子权值比较小，那么就需要当前子树的父亲来覆盖自己，将还需覆盖的个数回溯回去。

如果构造成功，那么根节点会返回一个非负值。否则，表示根节点的父亲需要提供一些覆盖给这棵树，即构造失败。

每道题都 WA 了一发，思路不清，代码还长是怎么回事？

A Integer Sequence Dividing

把 $1$ 到 $n$ 的所有整数划分进两个集合 $S_1,S_2$，最小化 $|sum(S_1)-sum(S_2)|$，模 $4$ 讨论即可。

B Array K-Coloring

一共有 $k$ 种颜色，对长度为 $n$ 的数组每个位置染色，要求数字相同的位置颜色不同，并且每种颜色都要出现过。

每种数字维护一个最后出现的颜色，一开始预处理好每种颜色的开始位置，防止颜色出现没有 $k$ 种。

C Doors Breaking and Repairing

两个人修门和拆门，一共 $n$ 个门，轮流选择一个门拆和修，如果拆到 $0$ 后，就不能再修了，两个人都很机智，求最多拆多少个门。

如果 $x > y$，肯定可以把全部都拆掉。

如果 $x \le y$，自己肯定不会拆大于 $x$，小于 $x$ 轮流拆和修，统计一下即可。

D Balanced Ternary String

贪心。

E Monotonic Renumeration

给一个长度为 $n$ 的数组 $A$，对任意数字相同位置，生成数组 $B$ 所有对应位置的值也相同，并且生成数组 $B$ 满足 $B[0]=0$ 并且每个位置都和前面要么相同要么 $+1$，问方案数。

把所有相同位置线段合并，剩余 $cnt$ 条线段，答案为 $2^{cnt-1}$。

F Elongated Matrix

给一个 $n \times m$ 的矩阵，行可以任意两两交换，问交换后从上到下从左到右遍历这个矩阵，求相邻位置差的绝对值的最大值。

二分答案，将可以相邻的两行连边，判断哈密顿通路。

注意预处理和哈密顿通路的状压。

题面

给一棵 $n$ 个顶点的树，维护两个操作：

1. 所有深度为 $l$ 的点权值加 $x$。

2. 询问子树权值和。

分析

我们有两个思路：

1. 直接暴力修改（显然不行）。

2. 给深度打上标记，在子树的 dfs 序区间内找深度为 $d$ 的个数，再乘上标记（时空都不够）。

然后，我们引入根号算法，对于一层深度小于 $\sqrt{n}$ 个点，暴力修改，点的个数大于 $\sqrt{n}$ 打标记，预处理好每个深度的点的个数的前缀和。

查询时，查区间和，再加上枚举 $\sqrt{n}$ 个标记的和。

时间复杂度 $O(n\sqrt{n} + q(\log n + \sqrt{n}))$。