cojR13

Source

commetoj R13

D「火鼠的皮衣 -不焦躁的内心-」

请先思考后再展开

首先想到的是求出二次剩余,即$ans=\sum_{i=0}^n [i\%2=0] C_n^i (\sqrt a)^i b^{n-i}=((b+\sqrt a)^n+(b-\sqrt a)^n)/2$

如果每个数都有二次剩余的话直接CRT就好了,但众所周知有一半的数都没有二次剩余

还好这时灵光一闪想到了拓域,即$(i,j)=i*\sqrt a+j$去快速幂,和的二元组中一定$i=0$

然后这里2可能没有逆元,一个经典的解决办法就是$P*=2$(我见识少不知道,还好xgc会),code

当然其实也可以分析一下,考虑一下二元组中j是怎么被贡献出来的,显然此时根号的次幂是个偶数,所以-1会被消掉,上面的两个二元组的j其实是一样的,只求一个,不用/2,code

E 「燕的子安贝 -永命线-」

请先思考后再展开

如果我们知道直线的斜率,那就是要两条距离为2d的平行线内点尽量多,一定存在一种最优方案使得两条平行线其中一条上有点

于是我们枚举在其中一条平行线上的点A去更新答案,考虑哪些斜率(不妨规定其方向为,能使另一条平行线在右侧的方向)能覆盖点B:
$$
\\ \alpha=atan2(B_y-A_y,B_x-A_x),\beta=asin(\frac{2d}{|AB|})
\\ 对于|AB| \le 2d即B在圆内,[\alpha,\alpha+\pi]
\\ 对于|AB|>2d,[\alpha,\alpha+\beta] \cup [\alpha+\pi-\beta,\alpha+\pi]
$$
见图知真相(对顶角):

然后就是在各个角度中选择被覆盖最多的即可,注意到虽然角度是个环但并没什么卵用,跨环啥的直接拆开来就行了

我是直接用map作为差分的,这样的话记得要合并差<eps的部分;其他做法不太清楚,$O(n^2logn)$,code

F「蓬莱的弹枝 -七色的弹幕-」

请先思考后再展开

这题是在大家讨论的熏陶下想到的

对序列分块,每个块存里面元素的链表、值域的桶(开short即可,unorder很慢会tle)

那么操作1就是移动根号次链表的端点,操作2就是区间打个lazy标记,操作3就是直接询问桶

只要把链表维护好就很好写了,然而硬是写了1.5h,调了1h,比赛结束才刚过样例没开拍,然后车队里的xgc要写平衡树(不影响复杂度),直到目前都还没调出来……

$O((n+q) \sqrt n)$,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/66eeb7d6.html
转载请注明出处,谢谢!