Uoj练习

Published: by Creative Commons Licence

  • Tags:

UOJ002

题意

http://uoj.ac/problem/2

题解

每个二进制位单独处理,最后用数位DP解决。

UOJ003

题意

http://uoj.ac/problem/3

题解

定义$f(x)$表示当我们带$x$只A精灵,至少需要带多少只B精灵。很显然这个函数是递减函数,因此我们可以通过计算$f$得到所有的结果。

现在考虑假如我们知道$f(i)$,如果获得$f(i+1)$。由于$f(i+1)\leq f(i)$,因此我们可以从$f(i)$开始枚举直到$0$。很显然上面的过程总和最多发生$O(n+m)$次。

现在考虑在带$a$只A精灵以及$b$只B精灵的时候二者是否连通。可以用并查集判断,但是这样的时间复杂度为$O(n)$。总的时间复杂度就上升到了$O(n(n+m))$。

其实判断连通,我们可以用两种方法。

第一种就是用Euler Tour Tree在线判连通的方法,增加边和删除边的时间复杂度为$O((\log_2n)^2)$,判连通的时间复杂度为$O(\log_2n)$。这样时间复杂度就为$O(m(\log_2n)^2)$。

还有一种就是用Link Cut Tree离线判连通,所有操作摊还复杂度为$O(\log_2n)$,总的时间复杂度为$O(m\log_2n)$。

UOJ005

题意

http://uoj.ac/problem/5

题解

很容易想到kmp,但是会发现kmp适用于求最大border,但是没法求要求不能重叠的border。

跳过kmp,我们考虑z函数,会发现z函数很适合求满足奇奇怪怪条件的border总数。

对于$z(i)$,我们将$[i,i+\min(z(i),i))$(这里起始下标为$0$)范围内的border数全部加$1$。这是区间操作,但是会发现查询发生在所有修改后,因此可以用脏标记(维护一个新的数组tag,修改对应于在tag[i]上$+1$,在tag[i+min(z(i),i)]上$-1$),最后$O(n)$一次性处理掉所有脏标记。

每个样例的时间复杂度都是$O(n)$。