UOJ Logo kczno1的博客

博客

51nod 算法马拉松34 暴力AK记

2018-04-02 07:51:44 By kczno1

可能是省选退役前的最后一次$51nod$了

前两题水的吧

后面四题我貌似都跟题解不一样。。

$C$

首先让点$x$为随便一个端点

让点$y$使$x,y$将多边形长度分成两半

然后一直旋转,每次让距离下一个端点比较近的点移动到下一个端点

令$S$为指定的某一侧的面积

感觉它说不定可以二分

如果一次移动使$S$从小于一半变成大于一半就二分找出答案。

如果能做到两边$S$都会大于一半,但中间$S$小于一半我就错了。不知道能不能卡

复杂度$O(n+log)$

$D$

特判$2$

剩下的质数都是奇数

枚举右端点,枚举区间长度,发现左端点是隔着一个的连续的

就是说把点按奇偶分类后左端点是一个连续的区间

维护前缀和$O(1)$算

$O(n^2/logn)$

卡卡常就过了

$E$

考虑询问时枚举比较小的集合,在大的集合里$O(1)$找到前驱后继

那么如果对大于根号的集合两两求出答案,询问就是根号的

对于合并集合操作

如果合并后大于根号的话是要更新跟所有大于根号的集合的答案的

此时如果原来就大于根号的话是可以直接用原来信息的

如果原来小于根号的话就暴力枚举,$O(1)$找前驱后继

复杂度还是$n$根号

现在问题就是支持合并两个集合,$O(1)$询问某个集合中某个数的前驱后继

考虑用类似线段树合并的方法合并值域分块

就是把分块看成三层线段树的话,第二层暴力合并,叶子只有在两个都非空的时候合并

复杂度$n$根号

可能因为常数比标算大,卡常后才能过。

$F$

后缀数组水题

假如是一个字符串的话

枚举每个后缀

设长度为$len$,跟所有未枚举后缀的$lcp$长度为$mx$

它的贡献就是长度在$[mx+1,len]$的前缀

小于$k$的暴力

大于$k$的是一个区间,$O(1)$算

多个串是类似的

复杂度为$O(构建后缀数组)+O(n*k)$

$upd$

$C$正解性好像能证。。

其实就是跟题解一个证法

就是存在$f(x1)>0,f(x2)<0$的话,一定存在$f(x+1)>0,f(x)<0$

($f(x)$只是表达个大概的意思)

评论

WrongAnswer
E题我只会n*sqrt(n)*log(n)的启发式合并,卡了50多发OJ才过…… 想到预处理大集合到所有集合的答案,也想到多叉线段树,但觉得都会被卡空间就没继续想下去…… 另外F题统计有多少个hash值在区间内怎么做到和k无关?
JOHNKRAM
后缀数组都可以不用了……二分+hash就可以排序+LCP了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。