A 斑羚飞渡
B 诡异的因数
暴力试除法,强力试除即可。
C 表单
由于数据的问题读入的操作可能不是1,2
D 分数的运算
E 希望
因为n到10^5所以要用线段树之类的东东优化塞入背包的这个过程,时间复杂度O(n lg n),因为k很小,所以跑背包的时间可以忽略不计
总时间O(n lg n)
F 跳跃的旋律
时间复杂度O(n sqrt n)
G ftos的测试
##题解
可以发现,只修改一个数,所以如果有解,这个数一定减少了的值,
又因为没有修改,所以我们可以在一开始预处理的值,然后我用的是分块,
对于这个差值我们进行块内排序处理,然后每次询问我可以块内二分upper和lower
然后在找到满足减少了的解的数量,对于边角料暴力就OK了
然后我们发现找到的这个数量有两种情况:
###情况一
这个数量=0,即无解
这好办,输出"Error"
###情况二
数量>0,有可能有唯一解,也有可能有多个解,如
因为比较小,所以我们桶排+块内二分判断头尾的是否相同。
如果做出来这些解的都是相同的输出"pass"
否则输出"INF"
这样做至少还有桶排清零的大常数,但是在内还是能卡过去的。
##关于数据
数据是随机的,但是为了不全是Error,我们手动修改了数据。
##其他解法
线段树应该也是可以的,我们维护和,然后方法与分块差不多,时间复杂度
但是线段树代码太长了,本人懒得打(逃
如果有更好的解法敬请指出。
H 数据结构题
分块,块内排序二分找相同。很经典的题了。
J 开挂
首先,我们发现
有没有觉得后面这个东西很熟?其实这个询问就是求区间的数两两相乘的和。
但是好像还是没法算啊!
我们再观察这个东西,又可以发现
其实就是区间和的平方减掉区间平方和的。
对于区间加,线段树维护一下和与平方和就好了,时间复杂度小到爆炸(实际的话因为数据随机,后面个点每个点标程跑的不到,开都是出题人良心了)。
这个公式的来源其实就是
然后移项一下,提个式子,分解一下就是这道题了。
全部评论
(9) 回帖