hdu的服务器有点问题,体验比较差感觉打的中规中矩,不过能排到前50还是比较惊讶,估计受题目风格以及服务器问题的影响。(看来大部分队伍受网络的影响挺大的,而且听说有多道疑似原题,要重赛了,不过也无所谓)
¶1001
简单的分类讨论,解不等式即可
¶1002
队友过的,暴力
¶1006
构造题,发现$x^2+(x+3)^2-(x+1)^2-(x+2)^2=4$后,根据模4的值分别构造即可
¶1007
枚举$g(x)$,转成二次函数,剩下的就是二分加取整的琐碎问题
¶1008
我先想了一个看上去很可行的解法,不过最后统计答案复杂度会炸最后队友给出正解,考虑求解$v(l,r)\leqx$的区间个数,从大到小枚举gcd,然后抠出所有gcd的倍数,考虑相邻两个数形成的区间$[L,R]$,则以$[1,L]$中的点为左端点时,右端点必须满足小于R,才有可能使得$v(l,r)\lex$,然后就是一个前缀取min,整体求sum的segment beats了。(事实上由于维护的序列是单调的,也可以二分+区间覆盖来做,然而我写T了 ,可能是我写挂了,也可能是卡了3log,而sgbt更趋近于单个log,看了题解,直接在线段树上二分就行了,我在外面套个二分是该t)
¶1009
前缀和+map 类似于求多少个子区间的和为0,只不过扩展成二维的了
¶1011
队友过的,没参与
¶1012
考虑dp来求解,当求解完$dp_x$,枚举所有$p \midx$,让$[dp_{x+1},dp_{x+p-1}]$与$dp_x+1$取min即可。容易发现只要对每个x,考虑在质数集中最大的x的因子即可,又容易发现这个$dp$是单增的,所以不断维护当前覆盖到的最大右端点即可