[COCI 2020/2021 #1] Papričice

好像是属性店铺树形 DP的形式，但是是皇恩店铺换根 DP不太可能。
两种情况。

1. 两个断点在没有祖先关系
2. 一个断点是另一个的祖宗

能否通过选择根规避掉 #2？(*)
例如重心？
似乎可以。
那么，$\mathrm{ans} = \max(\mathrm{siz}[i], \mathrm{siz}[j], N-\mathrm{siz}[i]-\mathrm{siz}[j])$，枚举 $i$ 然后二分权值是容易想到的方法。
正确的。但是题解是用递归栈分类讨论 (*) 处问题的。
懒得写了。

[COCI 2020/2021 #3] Sateliti

看了题解才看得懂题，翻译背锅。

每个图像都可以由原图平移 $(x,y)$ 然后坐标取模得到。

如果枚举 $(x,y)$ 然后一个一个比较字典序的话，是 $O(n^4)$ 的，不能接受。考虑行状压，变为 $O(n^3)$，可以接受。

[COCI 2020/2021 #3] Selotejp

只涉及行列整体操作，看起来像转二分图。
最小覆盖。
……不能覆盖关了的啊
那没事了
翻译再次背锅。
注意到数据范围很小，显然状压。（靠数据范围猜复杂度是常用操作）
网格图上状压一般只有三种：

• 状压第一行，做不了。
• 状压当前行，$O(n 2^{2m})$
• 插头 DP，$O(nm 2^m)$

[COCI 2020/2021 #3] Vlak

有向图博弈。
显然这个图是 Trie.
直接算 SG，时间复杂度 $O(|c|\sum|S|)$，可以。
好吧，没有异或，不用 SG .

[COCI 2020/2021 #4] Vepar

阶乘分解质数的方法，虽然忘了，但是应该很快，大概 $O(n\log n)$。
在数据范围内的质数大约有 60 万个，有点悬，但大概没有更好的方法。
……

[COCI 2020/2021 #4] Hop

（一阵强劲的音乐在脑海中响起）
“每对满足 $a<b$ 的百合 $(a,b)$ 必须属于青蛙 $1,2$ 或 $3$ 中的其中一只。”
让我们说中文。
哦，边染色啊。
先用整除 O(n^2) 建图。显然图为 DAG
……
注意不到
看题解罢
哦，原来是数字限制。
那很不抽象了。

妙哉。

[COCI 2020/2021 #4] Patkice II

非常经典的 DP，设达到 $(a,b)$ 的代价为 $f(a,b)$
显然路径不能成环，否则会无限动。因此一个点的四个方向互斥是可以保证的。
当然，最后写出来是最短路的形式。但是我还是习惯它类最短路 DP

[COCI 2020/2021 #5] Planine

woc，计算几何
照亮整个山谷的光源一定在 V 字形的上端。
显然贪心得越远越好，（当然，不能在无穷远处）
找一条足够远的直线作为天幕，此时变为一维问题。

[COCI 2020/2021 #5] Sjeckanje

区间修改，查询分割之后极差和的最大值。
考虑没有修改怎么做。
似乎与单调区间有关。

不会。感觉蓝题都不咋会的亚子……
退化力！

[COCI 2020/2021 #6] Anagramistica

直接排序 + hashmap，然后统计相似类个数 $a_i$。小于 $2$ 的可以直接扔掉
然后是简单的 DP.
设前 $i$ 个相似类已经处理好，并且恰有 $j$ 对单词相似的方案数为 $f(i,j)$
于是 $f(i,j) = \displaystyle\sum_{1\le r\le j, a_i/2} f(i-1,j-r) + \binom{a_i}{2r}$
时间复杂度 $O(cak)=O(nk)$（$c$ 为相似类个数）
使用滚动数组，空间 $O(ak)$