Phantom Bird

外观

看 COCI 2020 蓝绿题

约 865 字大约 3 分钟

OI

2025-4-23

[COCI 2020/2021 #1] Papričice

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

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

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

[COCI 2020/2021 #3] Sateliti

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

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

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

[COCI 2020/2021 #3] Selotejp

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

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

[COCI 2020/2021 #3] Vlak

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

[COCI 2020/2021 #4] Vepar

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

[COCI 2020/2021 #4] Hop

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

妙哉。

[COCI 2020/2021 #4] Patkice II

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

[COCI 2020/2021 #5] Planine

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

[COCI 2020/2021 #5] Sjeckanje

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

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

[COCI 2020/2021 #6] Anagramistica

直接排序 + hashmap，然后统计相似类个数 aia_i。小于 22 的可以直接扔掉
然后是简单的 DP.
设前 ii 个相似类已经处理好，并且恰有 jj 对单词相似的方案数为 f(i,j)f(i,j)
于是 f(i,j)=∑1≤r≤j,ai/2f(i−1,j−r)+(ai2r)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)O(cak)=O(nk)（cc 为相似类个数）
使用滚动数组，空间 O(ak)O(ak)

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)