2021“MINIEYE杯”中国大学生算法设计超级联赛（8）

AC代码

1002 Buying Snacks

1003 Ink on paper

二分最短距离，然后用并查集暴力维护联通性。有亿点卡常。

1004 Counting Stars

考虑到两种操作分别为将该数最高位左移一位和删除最低位的1，询问与修改都是区间操作，很容易想到需要使用线段树维护。左移操作可以使用区间乘实现，而删除操作对于每一个数生效次数其实不会超过31次，所以可以用单点修改维护。由于常数会比较大，建议使用zkw线段树。

1006 GCD Game

质因数分解的nim博弈变形题，将每个树转化为质因子次数和即为nim博弈模板题。

1008 Square Card

两圆相交面积的模板题。

1009 Singing Superstar

AC自动机模板题。

总结

首先1006因为一开始思路有误，wa了一发。1003由于常数比较大被卡，后来优化常数才过。1009套个模板，一开始由于评测机的问题疯狂被卡，后来重测都过了。1008由于pi的常数设置错误，wa了一发。之后在1004由于先队树的常数比较大，加了多次优化都过不去，后来改成zkw线段树才过。