赛时
真是的,赛前目标230+,结果真就拿了230
T1不到半小时过了
T2仔细分讨了一下,发现了很多性质
感觉起来很麻烦,但是感谢没有放弃
然后花了3h切了
想这种分讨题目,写之前不光要想思路,还要想实现,这样正确性更高一点
赛时因为不知道a还能大于p,多调了好久
在开写代码之前应当再看眼题目!!!看条件和数据范围
写完T2后只剩不到35分钟了
速度读完T3,敲了20分
看了一眼T4,然后敲了20分
然后就到时间了
但是T4 10分没开int128(这谁能想到,要是还有时间,应当自己本地测一下
于是230,rk1(好多平分的)
赛后
赛后kh嘲讽了一番,理论上来讲,T3可拿60,T4可拿40
但是赛后也想了,都没太能想出来
T3,40分
考虑区间很小,复杂度瓶颈在于每一次询问枚举区间,所以对于每一个x,枚举所有能贡献区间的情况
T3,60分
相当于是在说 \(l_i<=\sqrt n\)
还是要用一种方式预处理区间
做法:当 \(l_i=1\) 时,预处理右端点序列上的前缀和,然后查询就查 \([x1,x2),[x3~x4) \dots\) 即可
空间可能会炸,发现随左端点的增大,右端点减少 \(1/n+2/(n/2)+3/(n/3)=n\log n\)
T3,100分
有一种思路,就是根号分治m
当 \(m<=\sqrt n\) 时,不太好处理
因为 m 很小么,所以可以用x将区间划分为m个段,发现区间端点在同一个段内的答案都是相同的
所以枚举 l 所在段,和 r 所在段,然后二维数点,单次询问 \(O(m^2)\) 的
又因为 \(m<=\sqrt n\) ,所以 \(O(m^2)=O(m\times \sqrt n)\)
总复杂度为 \(O(\sum m\times \sqrt n)\)
T4,40分
枚举一条线段,判断会被多少个三角形统计到,注意gcd要预处理
还有可以把 long long变成int或short(hd)卡常
还有就是枚举顺序需要考虑
只补了T3 40分,和T4 40分
T3没时间写完了
模拟赛