Codeforces Round #425 (Div. 2)

A. Sasha and Sticks

简单题,问有 n 个棍子,每个人轮流取恰好 k 个,不够取则输,问谁会赢。 n\ mod\ k 判断奇偶性即可。

 

B. Petya and Exam

字符串匹配,? 符号可以匹配 good letters,* 符号可以匹配任意 bad letters 的字符串,包括空串。
分两种情况考虑:
1.没有 * 号直接匹配。
2.有 * 号,先匹配左边一直到 *,记录下 b 串匹配到的位置 nowl, 在从右边开始匹配一直到 *,记录下 b 串匹配到的位置 nowr.
如果此时 nowl < nowr 即匹配成功。

 

D. Misha, Grisha and Underground

给你一棵树,有 q 组询问,给 a, b, c 三个点,任意组合作为 s, t, f, 每组询问问 sftf 的路径最多有多少重合的节点。
首先对整棵树预处理,方便求 LCA. 对于每组询问,穷举 a, b, c 三个点分别作为 f 点。对于一组 s, t, fs, t 其中一个是 f 的后代二另一个不是,那么必然重合的节点数为 0. 反之 s, t 一定是汇聚到一点 g 之后再一同出发去 f 点。而汇聚的这一点 glca(s, t), lca(s, f), lca(t, f) 中最深的一个。而重合的路径一定是 min(dis(s, f) , dis(t, f), dis(g, f)), 如此便求出答案。

 

总结

一年多没打 cf 的确手感生疏了不少, B 题因为小细节方面 fst 了, D 题也是不停的 debug 到最后一分钟才过了。总的来说发挥不是特别令人满意,开坑待补题。😤😤😤😤😤😤

发表评论

电子邮件地址不会被公开。 必填项已用*标注