agc024 题解

link

code

A (color{gray}igstar)

对于差而言每次操作相当于交换，因此判断 (k) 奇偶性即可。

B (color{gray}igstar)

不变的部分是一个值域连续上升子序列，直接找即可。

C (color{green}igstar)

从后向前，直接推推就可以得到对答案的贡献。

D (color{blue}igstar)

先考虑第一问，手模一下可以发现确定一个根之后所有深度相同的点是可以同构的。

因此第一问答案就是直径的一半。

第二问，确定根后相当于每一层取儿子个数最大值然后乘起来。

数据范围小，直接枚举根，注意根可以是一条边。

E (color{blue}igstar)

不是很难的小清新数数。

插入等价于选一个位置，向右平移，然后再原地放一个更大的数。

考虑把序列中的数看成一个集合，等价于选一个数，插入一个比他大的数。

如果已知最后集合中数的集合，怎么求方案数？

考虑从小到大加数，那么比当前数小的都本质相同，先预处理出 (f_{i,j}) 表示 (<x) 的数有 (i) 个，(x) 有 (j) 个的方案数，这个可以 (O(n^2)) 的 dp 求。

然后直接放即可，令 (g_{i,j}) 表示当前进行到 (i)，前面总共有 (j) 个数的方案。

时间复杂度 (O(n^2K))，好像可以用卷积优化？

F (color{Gold}igstar)

神秘的 dp 套 dp。

考虑对于一个数找他的所有子序列。

先建子序列自动机，然后每个子序列对应唯一了。

然后 dp，(A) 表示当前的子序列，(B) 表示还没有匹配的东西，注意到 (|A|+|B|le n)，因此可以压在一起，再设一维把这两个隔开，最高位加一把 (B) 隔出来，然后转移即可。

复杂度 (O(n2^n))。