自闭了。

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}))$。

题面

给一棵 $n$ 个点带权边权的无根树，要求在在树上选一些边，构成树上的正好 $m$ 条路径，并且每条边最多只能在一条路径中出现，要求最大化每个选择方案中的最小路径长度。

分析

二分答案。

链

二分答案，$check(mid)$ 判断能不能将一条链划分成 $m$ 个最小值为 $mid$ 的段，每段可以贪心的选取大于等于 $mid$ 的最小段。

菊花

只有两种情况，一种是只选择一条边，第二种是选择跨过根节点的两条边。

对于长度大于等于 $mid$ 的边，单独构成一条链，对于长度小于 $mid$ 的边，贪心地去和最小的能连在一起长度大于等于 $mid$ 的边组成一条链。

回到一般的树上

树上每个节点与其父亲只有一条边，因此在一个节点完成类似于菊花情况的匹配的时候，可能会剩下多条边，而这些边中选一个最大的传递到父节点，与当前节点到父节点的边组成一条链，在父亲节点类似的做菊花情况的操作。

Candidate Master！

A Gennady and a Card Game

模拟。

B Petr and a Combination Lock

差点不会 dfs 了。

C Yuhao and a Parenthesis

给 $n$ 个括号序列，两两配对，每个最多出现在一对里面，求最多能匹配上多少对。

将所有括号序列转成 $l$ 个左括号和 $r$ 个右括号。当且仅当，左右括号至少一个为 $0$ 才对答案有贡献，统计每种左右括号个数的出现次数，左右括号相等时才能凑成一对，已经平衡的序列个数除二加到答案里面。

D Makoto and a Blackboard

给出一个数 $n$ 和次数 $k$，每次将这个数随机变成他的一个因子，这个操作恰好执行 $k$ 次，求最后出现的数的期望。

大力猜了一发，只需要求 $n$ 的所有素因子 $p^\alpha$ 的期望 $f_p(\alpha, k)$，全部乘起来即可。

实际上，从每个素因子里面取这个事件之间相互独立，乘积的期望等于期望的乘积。

下面求这个 $n=p^\alpha$ 的期望，有递推式

推了半天推不出公式，直接记忆化搜索，复杂度不知道。

出题人是不是弹丸粉？

F Alex and a TV Show

维护 $n$ 个多重集合，有 $4$ 种操作：

1. 第 $x$ 个集合变成 ${v}$；

2. 第 $x$ 个集合变成第 $y,z$ 两个集合的多重集的并集；

3. 第 $x$ 个集合变成第 $y,z$ 两个集合的积集元素的 gcd；

4. 询问第 $x$ 个集合内有多少个 $v$，模 $2$ 输出答案。

分析

询问要求模 $2$，考虑用 bitset 进行维护，如果我们维护的是每个数的出现次数，操作三将难以维护。

转化为维护集合内每个数是多少个数的因子，记集合内有 $a(d)$ 个数含有因子 $d$，$x$ 的出现次数为 $f(x)$，那么

下面那个是我抖机灵凑出来的。

因子和询问系数可以预处理得到。

对于操作一，直接将因子集合赋值，操作二等价于按位异或，操作三等价于按位且，操作三等价于用预处理的容斥系数作用在 bitset 上，即按位且后 $1$ 的个数。

对于操作三，单独考虑某一个因子，他对积集的这个因子出现次数的贡献为另一个集合含有这个因子的个数，最终这个因子出现次数就是两个集合内出现次数的乘积。

A New Year and the Christmas Ornament

$ans=3min(y,b-1,r-2)$。

B New Year and the Treasure Geolocation

给出 $n$ 组坐标和 $n$ 组偏移，每一个坐标对应一个偏移，顺序打乱，但是所有坐标加偏移得到的位置相同。

答案为 $x$ 和 $y$ 的均值。

C New Year and the Sphere Transmission

$n$ 个人组成一个环，从第 $1$ 个开始间隔 $k(1 \le k \le n)$ 报数，直到回到 $1$，定义 $f_k$ 表示这个循环节的编号之和，输出 $n$ 的所有可能 $f$。

编号为 $k$ 的路径是一个首项为 $1$ 的公差为 $\gcd(n,k)$ 的等差数列（由裴蜀定理容易知道），$O(1)$ 计算 $f_k$。因为只有 $n$ 的因子才对答案有贡献，质因数分解即可。

D New Year and the Permutation Concatenation

将 $1,2,\cdot\cdot\cdot,n$ 的所有排列按字典序连在一起，求长度为 $n$ 的连续子区间之和为 $\frac{n(n+1)}{2}$ 的个数。

将每个排列分成两块，前面 $k$ 个的排列的每一个对应了 $n-k$ 的排列，连续的 $(n-k)!$ 个两边连在一起对答案有贡献，$g(k)=\frac{n!}{k!}(k!-1)$，对 $g(k)$ 求和。

E New Year and the Acquaintance Estimation

$n+1$ 个点的图，给出前 $n$ 个点的度数序列，问第 $n+1$ 个点的所有可能取值。

根据握手定理可以知道最后一点度数的奇偶性，并且如果度数可以取到 $x,y(x < y)$，那么 $[ x, y ]$ 中都可以很容易构造出来。

因此可以二分上下界。

对于一个点的度数是否可行，可以应用 Erdos-Gallai Theorem 判定。

F New Year and the Mallard Expedition

一个人从左往右走，道路被分为很多条草地、水和山，在草地上速度为 $5m/s$，在水里游的速度为 $3m/s$，飞的速度为 $1m/s$，每走或游一米可以获得一点能量，飞行每一米都需要一点能量，求最小时间（所有路程能量都是在实数范围内取值）。

考虑贪心，在草上走路，在水里游，在山上飞。如果飞山时能量不足，就在之前补充能量。如果最后能量多余，能量的一半提供给草地和水里（消耗能量和没有获取能量）。能量兑换为路程时，必须要满足路程数的两倍不超过能量总数，因为飞山的时候可能会要求必须在草里获取能量。