难度分布

• Easy: C,K,L,M,N
• Easy-Medium：J,F,I,G
• Medium：D,E,H
• Medium-Hard：A,B

A. Convolution

• 2^(ab)=sqrt(2)^((a+b)^2-a^2-b^2)
• 对每个 a+b，求出 sqrt(2)^(-a^2-b^2) 的和
• NTT
• 时间复杂度：O(nlogn)

B. 双圈覆盖

• 先将每个点度数变成3：拆点
• 之后⼀定有偶数个点，且去掉环后点两两配对了
• 第⼀类圈：最外层的环
• 第⼆类圈：配对边 和 {(2i,2i+1)} 构成的⼀系列欧拉回路
• 第三类圈：配对边 和 {(2i,2i-1)} 构成的⼀系列欧拉回路

C. 酒馆战棋

• 最好情况：普通随从破盾，剧毒随从杀怪
• 最坏情况：剧毒随从破盾
• 模拟即可

D. 递增递增

• 出题⼈做法：
• 因为 a[1…n] 递增，考虑最⾼位，a[1…k] 为0，a[k+1…n]
  为 1，然后分成左右两半做
• 维护当前已经定的值和 a[L…R] 的最紧的限制的关系
• 有更好的做法，但这个做法更通⽤

E. Access

• f[x][i] 表示⼦树 x 经过 i 次 access 的形状个数
• 合并时，access 次数等于所有⼉⼦⼦树⾥ access 次数之
  和（要钦定⼀个⼉⼦来将它的实边延⻓上去）
• ⼀种情况；没有⼉⼦的实边延⻓上去了：那么要额外执⾏
  ⼀次 access(x)
• 时间复杂度：O(nk)

F. 图与三⻆形

• ⾮同⾊三⻆形：⿊⿊⽩或者⽩⽩⿊
• 恰好两个点连出来的边不同⾊

G. 单调栈

• ⾸先 f[1] 肯定是 1，把所有是 1 的位置拿出来，把 K…1 倒
  序放⼊，其他 f[x]-=1，然后递归下去做

H. 异或询问

• 做法1：[L,R] xor x 可以分成 O(logn) 个连续的区间，对每
  个区间去⽤ multiset 计算答案
• 做法2：将 trie 树建出来，把 L,R 在上⾯⽤类似线段树区间
  询问的⽅法去进⾏询问

I. 变⼤

• 最优解⾥ a[1…n] 肯定是分成若⼲段，每⼀段⾥最⼤值唯
  ⼀，且最后这⼀整段都会变成这个最⼤值。
• ⻓度为 L 的⼀段需要的次数是 L/2，背包⼀下即可。

J. K 重排列

• 考虑 i->p[i] 连边后，周期就是所有环的⻓度的 LCM，所以
  充要条件就是每个环的⻓度都是 K 的约数
• 每次枚举最⼩点所在的环的⻓度，⽤组合数学的⽅法求⽅
  案数

K. 最⼤权值排列

• 越靠中间对答案影响越⼤
• 所以⼤的数尽量往中间放

L. 你吓到我的⻢了.jpg

• BFS

M. ⾃闭

• 注意读清楚题意

N. 合并

• 很多奇奇怪怪的贪⼼交上来了
• 其实⽆论怎么进⾏合并，最后的答案⼀定是 a[1…n] 两两的
  乘积之和
• 所以只要你写的贪⼼没算错答案就肯定是对的