2022 ICPC 杭州站

发布时间 2023-09-30 15:53:26作者: ft61

gym

知乎


尝试先读题而不是写缺省源感觉不太好
E 一头雾水。F 是签到就先上去写了,结果读错题交了个样例都没过的代码,小改了一下就过了。G 不太会做。zsy 把 M 丢给我想了一下
然后 gjk 把 D 过了。看榜发现 K 过了很多人,需要快速判断比较两个字符串等价于比较哪两个字符,反应了一下才意识到是 trie,上去写了,但没判一个是另一个前缀 WA 了一发
gjk 给了个 C 分治背包的做法,不知道 \(3000\) 的平方对数能不能过,我想了下感觉不好优化就让他写了,后来才看到物品体积 \(\le10\)
期间 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\) 不清空,所以不是多测