Contest Info

date 2017.08.27 9:00-14:00

practice link

Solutions

I. Matching in a Tree

题目大意： 维护一个初始仅有根节点（编号为 0）的 trie 和一个初始为空的字符串 \(S\)。定义 \(P_i\) 为 trie 上从根走到节点 \(i\) 的路径对应的字符串，\(Q_i\) 为 \(S\) 的长度为 \(i\) 的前缀。

接下来 \(m(m\le10^6)\) 次事件，事件分为三种：

• ADD u v c 新增一个 trie 的节点 \(v\)，父亲为 \(u\)，通过转移 \(c\) 得到，保证 \(v\) 为当前 trie 最大编号加一
• ASK p1 p2 t 问是否存在一个前缀 \(Q_i\)，满足 \(p_1\le i\le p_2\)，且 \(Q_i\) 是 \(P_t\) 的子串
• INS p1 p2 在字符串 \(S\) 的尾部加上一个字母，它可能是 \(p_1\) 到 \(p_2\) 之间的任意一个字母

保证 \(S\) 最终长度不超过\(1000\)。

题解： 发现这题的在线条件是假的，trie 上新增的节点在出现前不会被问到，同理字符串后面的位置不会影响前面的询问。这样我们可以先把 trie 建出来，将询问存在 trie 的节点上，对 trie 进行 dfs。与 \(S\) 的匹配用 Shift-And 算法去做。匹配结束后，我们还要合并到根路径上的匹配结果。询问的时候就是去对应的 bitset 中问一个区间中是否存在 1。时空复杂度均为 \(\mathcal{O}(mL/\alpha)\)，\(\alpha\)为 bitset 优化的常数。

Replay and Summary

Replay

Z 一来先看了看 A，觉得比较签到，想写个二分。写了几句话，在旁观察的 W 说直接暴力就行了，然后写完就过掉了。接着 D 看了看 B 题的时限，觉得直接对每种颜色树状数组维护就可以了，写了一会儿发现不对，就让 W 来写 K 题。

W 的 K 题 wa 了之后，打印出来静态查错，D 又看了看题发现 E 也很签到，过来先 a 了。然后给 B 题加了一个 cdq 分治，提交 re 了，也打印出来静态查错。接着两人相继改了改提交了几发，D 又 re 几次之后发现循环上界开大了 1 爆数组了，改掉之后又 re，再看了看发现没改完，改完之后过掉了，错失一血。W 在 D 给造了几组数据之后，发现一个小错误，也过掉了。

然后 W 继续想已经想了一会儿的 D 题，之前写了 wa 掉了。Z 发现 H 好像很水，也开始写。W 跟 D 讨论讨论了 D 的转移，发现之前有个转移写错了，改了改矩阵也过掉了。Z 接过键盘写 H，写完就过了。

Z 开始做 I ，猜了个小结论开始打表验证。D 看了看 C 题跟 W 讨论了一发，觉得就是三元环计数，也开始写。Z 写完 I 题 wa 了一发，然后给 W 讲了讲做法，然后发现是一个计算的细节（应该先分别除了再相减，写成了相减了再除）出了问题。此时 D 的 C 题 tle 了一次，W 建议用 unordered_map 代替 map，果然改掉就过了。然后 Z 把 I 的细节改掉也过了。

此时时间才过去了一半，已经过了 8 题，感觉这场很有戏啊。然后开始分别开题，W 和 Z 看了看 F，没太明白操作 1 的 reverse，提问也 No response，样例也没有，就感觉不太可做。然后 D 看了 G，觉得就是模板题，但是没带就开始现写（因为之前弊队计算几何模板出问题了，所以这次带的是昂神的模板，其实是有这个题的，但是眼瞎没看到），re 了很多发之后最后还是 wa 的。J 题 W 看了之后感觉是 shift-and 算法，但是也只在集训的字符串专题写过一次，并且本题还有些细节没想清楚，所以本题也没写。然后 L 题之前想了想 hash 的暴力匹配，感觉复杂度有问题？ 后来想到了第二个答案至多是 2 的时候，已经陷入了 kmp 的怪圈，此题同样 GG。

第一次打现场赛状况有点多 @_@ ，不过总的来说成绩还是不错。