Day 1 A. 生成树计数

考虑这棵树的 序列,设 表示 序列中出现的次数,则有

考虑一个序列 的贡献,是

设后面这个 关于 的生成函数是 。再设

考虑枚举 是哪一项被算的,则有

求出 后,需要代入 并求和,于是还要对 预处理一个

总复杂度

Day 1 B. 无限之环

跑费用流,对于度数 的点直接建边,对于度数 的点可以拆成上下和左右两部分建边,对于度数 的点解个方程。

Day 1 C. Hello world!

设一个 , 对 的操作,暴力修改暴力查询;对 的操作,重建 棵树,查询时搞个 BIT,修改的时候暴力向上找,修改到 了就并查集合并一下。

Day 2 A. 小 Y 和地铁

考虑两个线段 ,如果前者包含后者,则后者的端点方向不同造成 的代价;如果交叉,则 的方向相同造成 的代价。直接枚举是 的。

考虑按左端点排序以后,如果知道了前 条线段的右端点方向,那么可以直接贪心出 的左端点方向,因此是 的,加上最优解剪枝即可过。

Day 2 B. 小 Y 和二叉树

先求出所有子树/子树外的最小的序列开头。

首先编号最小的度数 的点一定是序列开头,在树的最左下方。

如果固定了某个点作为当前子问题的序列开头,可以贪心右儿子和右父亲的放法,递归求解。如果固定了某个点作为当前子问题的根,可以贪心左右儿子的放法,递归求解。

Day 2 C. 小 Y 和恐怖的奴隶主

搜一下发现状态最多 个,加上记答案一共 维,先预处理出 的次幂的答案,然后询问的时候用向量乘矩阵,复杂度就是 是维数)。

Day 3 A. 简单数据结构

这个题由于限制了每个数的插入次数最多为 ,所以总复杂度很稳。

给每一个数开一个桶记录一下后面长为 的答案数量,每次后端插删的时候更新约数,然后更新约数的约数。前端插删的时候枚举倍数暴力求一下这个数的答案就行了。

Day 3 B. 福若格斯

首先手推一下每个数的 surreal number。

这里规定 表示先手胜,

然后一共有 一共 种状态,其中前 种可以求和,组合数算一下 的方案数分别有多少。

然后 的状态会受到 的奇偶性和 哪个比较多影响。需要注意的是 产生影响的话 的个数差需要 才会造成对应的影响。

Day 3 C. 避难所

可以发现样例的构造方法是

于是可以构造最优解是 ,而贪心解是 的东西。 足够大的时候大致取 即可。

小的话就暴力一下形如 的答案是否可行即可。

Day 4 A. 我的生命已如风中残烛

首先考虑暴力,每次暴力找后继绕过去,如果绕的时候出现了绕着一个凸包转多圈的情况,相当于可以直接模掉这个凸包的长度。所以每次找循环节,线转一圈长度至少减半。

优化找后继,可以以每个点为中心预处理出极角序,再预处理从某个点过来的时候的第一个可行位置,转的时候拿个指针扫下去就行了。

Day 4 B. 榕树之心

DP 出一个子树内部互相消,可以消成至少几个点。那么就是把儿子中大小最大的挑出来,看其它儿子能不能把这个消没有。特判一下奇偶。

的答案可以把 的路径缩成一个点求一下 DP 值。

Day 4 C. 某位歌姬的故事

首先离散化,求出每一段的最大值,判一下不合法。

然后对于同一个最大值,把这个最大值的区间全部抠出来,再把是这个最大值的限制全部抠出来,做一个 DP 就行了。