bzoj

最近都在做梦的感觉啊.这道题倒是mhy的博客一语点醒梦中人. 只会加正数,所以每个数只有至多一次会从负变非负. 链剖是肯定的.然后记录一下当前最大的负数是谁.如果大于等于0就改掉.所以还是O(n*log2n). 所以我还是太弱了.于是读入优化大法抢了一个rank1.

比较郁闷的题ovo拍了老久.最后还是找Po神要来了数据. 首先这个矩阵的基就是一个拟阵,所以可以贪心. 然后发现就是要O(n^2)判断是否线性无关. 其他人的做法是强行顺序.我觉得没辣么麻烦啊.先把原来消出来的东西备份一下.如果发现不行再备份回来就好了啊ovoovo 那么直接高消会有非常严重的精度问题(似乎是). 于是我想直接用整数搞.然后发现会有变成负数的问题和越界的问题,强行re+wa.非常不开心. 于是直接取模yeah.然后由于用了辗转相除之类的东西所以常数巨大.而且bzoj上开了O2比本机没开O2竟然慢了6倍.ovoovo

还比较有意思的一题. 考虑如果Alice选了某一个位置,那么Bob的策略一定是选使得Alice的和最小的一段.也就是对于所有位置,求包含它的所有区间中和最小的一个,再求个max. 这个东西先要展开一倍,然后可以比较方便地用单调队列搞定.

其实是一道没多大意思思的码农题TT然而这是我的第800题所以要mark一下. gcd序列可以用插分序列+第一个数来支持区间加.二维那就二维差分喽. 然后发现第一个数似乎没有办法维护啊.不能做了?! 询问的方式比较奇怪,有一个中心.那就建4个方向吧.这样似乎可做了yeah. 所以我还是太naive了啊. 是时候屯一波题了.

立杰的dp套dp.之前在hwadee培训的时候讲过的题啊. 考虑求lcs时候的f数组的一列,发现相邻两个数要么差1要么不差.于是15就是拿来状压这个东西的. 然后很愉快地写了一个然后很愉快地tle了.妈妈,剧本里没这一节啊. 仔细思考了一下发现每次在计数dp转移的时候去找lcs dp非常慢.而且只要给定状态和转移,目标是确定的.跑1000次浪费了.于是改成预处理转移.就好了.

业界毒瘤ioi开的坑.然后被强行看了一下于教授的代码.然后觉得也不太难嘛. 看了一下条件.只和同行或者同列有关?那就拿map套动态建树的线段树好了辣. 然后距离是欧式距离?那就把完全平方式展开,发现只需要在线段树里记录一下个数,和,平方和,搞定了辣! 然后alloc的时候–写成了++,查错良久,囧.

之前觉得不可做的一道题.然后昨天听mhy一句话瞬间懂:几何反演.然后mhy说这题用cdq?骗我读书少呢? html写公式好郁闷.把设圆心是(p,q),点是(x,y),那么点在圆内的条件是 (p-x)2+(q-y)2 ≤ p2+q2 转化一下变成 q ≥ -(x/y) * p + (x2+y2) / (y*2) 然后就可以把(p,q)看作一个点,每个询问就是询问之前的所有点是否都在这条直线的上方. 那么直接归并排序喽.处理出左边的凸壳再单调扫一遍右边的所有直线.这样复杂度是O(n*logn),又短又快yeah. 然后还听说有精度误差?我全程double没用eps也没出事啊hhh

最近整个人都被Sone1搞得头昏脑胀。不爽ing。 这个题其实就是线段树+维护的题。考虑给一个区间里每个数加C的时候的式子会变成什么样就好了。 然后要注意标记得随时下传，不能永久化。 然后感觉时间有点慢不过跑起来还将就。 然后我太弱了。

ioi好神啊,居然写搜索.我显然是不想写高精的啦于是用java于是花费了整整两节课TT 我的想法是dp.设答案为f[m],那么f[m]只与fd有关.设f[i][j]表示i为m的第i小的约数,且已经用了前j个素数的答案.然后就可以转移辣. 然后得二分一下用多大的素数可以卡过.毕竟java自带大常数.而且bzoj坑爹在不管有多少组数据都只多给2秒总时限ovo

这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.