2022 ICPC 杭州站

gym

知乎

---

尝试先读题而不是写缺省源感觉不太好
E 一头雾水。F 是签到就先上去写了，结果读错题交了个样例都没过的代码，小改了一下就过了。G 不太会做。zsy 把 M 丢给我想了一下
然后 gjk 把 D 过了。看榜发现 K 过了很多人，需要快速判断比较两个字符串等价于比较哪两个字符，反应了一下才意识到是 trie，上去写了，但没判一个是另一个前缀 WA 了一发
gjk 给了个 C 分治背包的做法，不知道 $3000$ 的平方对数能不能过，我想了下感觉不好优化就让他写了，后来才看到物品体积 $\le 10$
期间 zsy 在做 A。我跟榜看 G，没什么想法，gjk 猜 $m>n$ 时一定无解我证出来了，现场学习了一下树同构（其实做法和我国赛场上编的树哈希差不多，我当时还是有点实力的），抢了 zsy 的机子。corner case 判不完全 WA 了一发。然后 zsy 艰难地过掉了 A
剩下 2h+ 的时候就一筹莫展了。在 I 和 M 之间徘徊，I 猜了个做法当然不对。M 不会加一个数再求 $gcd$，我把跟树有关的东西都想了一遍，感觉肯定是有性质被忽略了，zsy 提到了做差但我没反应过来。最后 zsy 会了但没写完

体验极差，罚时吃太多了，甚至没有金。以后还是得把所有题都读了，卡题的时候初步思考后我就没什么贡献了

---

G. Subgraph Isomorphism

• $m=n-1$

YES

• $m=n$

如果环上外挂的子树都同构那么 YES
如果环长为偶数且外挂的第奇/偶数个子树分别同构那么 'YES'
否则 NO

• $m>n$

至少有两个环。只考虑这两个环和连接部分，一条链 和 有三度点 无法同构

F. Da Mi Lao Shi Ai Kan De

题意：有 $n$ 个 group。对于第 $i$ 个 group，有 $m_i$ 个字符串，依次考虑每个字符串：如果含有子串 bie 且不在 group $0$ 中就输出并加入 group $0$。如果当前 group 没有字符串被加入 group $0$，输出 Time to play Genshin Impact, Teacher Rice!

group $0$ 不清空，所以不是多测