UOJ Logo zx2003的博客

博客

请问能否开放uoj357的hack?

2020-06-23 18:41:39 By zx2003

我发现对于一些数据,很多ac程序的输出是不等的.

UOJ#446 交互库有锅

2020-01-27 20:54:47 By zx2003

关于 UOJ#484 的一些疑问

2020-01-27 17:06:51 By zx2003

这份提交 WA在extra test9了。

但是我能构造一组得到85的方案:

{20,18,15,8,8,8} $\rightarrow$ {22,22,22,22,22,22} $\rightarrow$ {22,22,22,0,0,0} $\rightarrow$ {31,30,30,30,0,0} $\rightarrow$ {30,0,0,0,0,0} $\rightarrow$ {85,0,0,0,0,0}

当我去找当时的hack记录的时候,它显示"expected: '87'",然后我手玩了很久也没玩出来。

直到我偶然点进原始提交记录的时候,突然发现原始提交是AC的。。。捂脸熊

所以到底发生了什么呢?

NOI2019D2T1的 O(n logn) 算法

2019-09-18 20:21:11 By zx2003

感觉也不是很难,不过先前没听人提过。

显然题意可以转化为给定二维平面上的若干个点和若干个矩形,然后需要按某个特定的顺序取出矩形中的所有点。

一个简单的做法是对 $x$ 这一维建线段树,对线段树的每个节点维护一个set,每次需要取出点的时候就在set里通过lower_bound逐个找到需要的点。

这样复杂度是 $O(n\log^2n)$ 。

更优秀的做法是把所有点的 $y$ 坐标和询问矩形的下边界排个序,从小到大进行扫描线,同时维护出每个矩形在线段树的每个节点上lower_bound的结果。

取出点的时候,在线段树的每个节点上我们需要执行的操作是1.找到某个位置往后第一个没被删除的点;2.删除某个点。

显然这可以使用并查集做到线性,链接在这里

代码在这里

为了方便实现以及实践效率,该代码中并没有使用线性并查集。

由于数据太水,运行时间被kdtree吊打。

反正数据结构的技能点不是技能点,打表的技能点才是技能点,随便出个T1数据乱造就好了对吧。

关于 [JSOI2019]节日庆典 的一个线性做法

2019-06-01 20:48:08 By zx2003

题目链接

很久以前我想过这个问题,但当时没有什么好的办法。

昨天去做了下江苏省选二轮的题,发现居然被出出来了。

看到问题后一个自然的想法是求出每个前缀的lyndon word分解(模板题在此)。

但是博主只知道Duval算法(可以看鏼爷论文),然后该算法需要在字符串结尾补$ - \infty $字符,如果要求出每个前缀的lyndon word分解,原来的均摊分析就失效了。

回忆一下Duval算法的过程,前缀$i$做完之后是(若干已经做好的)+(某个串s)重复t遍+s的某个前缀u。

可以证明,已经做好的部分对答案没有影响,(某个串s)重复t遍对答案有影响的部分只有第一次出现的位置,而$u$整个串都可能对答案有影响。

怎么办?

一个想法是,那就同时维护出串$u$,在执行Duval算法后的状态。

但是串$u$执行完Duval算法后会得到一个串u',我们需要递归执行前述的过程。

容易发现$|u| \le |s| \le \frac{i}{2}$,所以这个“递归”只会有 $logn$ 层。

具体实现可以参考这份代码

让我们思考一些可能的优化。

首先一个想法是,在Duval算法运行过程中,既然串$u$在之前已经出现过了,那么是不是可以复用之前的运算结果?

记串u第一次出现的位置的结尾处为$x$

也就是说,我们猜想$ans_i=min(串s第一次出现的位置的开头,ans_x)$,注意这里的$ans_i$可以认为是$i$-题目要求输出的真实的答案。

如果这样不对,那么必然存在两个位置$p$和$q$使得前缀$x$从$p$开始和从$q$开始的循环移位都是相等的。

否则这两个位置开始的循环移位在$x$之前已经比出大小,从$x$扩展到$i$不会对大小比较产生影响。

从而前缀$x$构成的串存在非平凡整循环节$y$。

同理可以证明$y$也存在非平凡整循环节.

如此递归下去,可以得到串$x$字符全部相等,此时我们可以平凡地验证结论的正确性。

有了这个结论,配合线性SA和$O(n)-O(1)$RMQ,我们可以获得本题的一个线性算法。

不过线性SA和$O(n)-O(1)$RMQ太难写了,博主写不动。

由于lyndon word的性质和Duval算法的正确性,在处理前缀$i$的答案时,$ans_x$所对应的后缀必然大于等于串s的等长前缀。

所以我们只需使用字符串哈希判定子串相等,之后便转化为了一个子串和原串比较大小,这可以通过exkmp来线性实现。

最后提交在这里,好像比$O(nlogn)$还慢。

如果本文论述出现了漏洞,欢迎读者指出。

PS: 听说16年有篇论文提出了关于子串最小循环的$O(n)-O(1)$算法,感觉本文可能只在OI中有用。

zx2003 Avatar