文章

算法 回文自动机其实挺简单的，我就尽量简 (tou) 单 (lan) 地讲了 首先回文自动机是用来维护一个字符串的所有回文子串的 回文自动机的每个节点代表一种回文子串 例如 abcaaa 中就有如下节点： a, b, c, aa, aaa 也就是出现位置不同但本质相同的回文子串会被归在一个节点内 然 阅读更多…

题目分析 Topcoder 的题太神奇了，要是不写题解，估计下一次遇见就不会做了…… 假设我已经随意地点亮了一些格子，那么现在我只要用两个矩形能够盖住所有点亮的格子，就说明方案合法。 用所有亮格子中最左，最右，最上，最下的四个格子确定一个矩形区域，那么这两个矩形用（一个放左上角一个放右下角）（一个放 阅读更多…

题目分析 $x=1$只能贡献一个 $1$，将它扔掉。 什么情况下会出现 $x_1^{y_1}=x_2^{y_2}$呢？ 当 $x_1=r^{y_2}$，$x_2=r^{y_1}$时。 于是我们可以将所有大于等于 $2$小于等于 $A$数分组，第 $i$组是所有 $i$的幂（$i$不能被表示为其他数的 阅读更多…

1. 题面 题目描述 AK 完了 IOI，CGZ 又向着 AK IBO 的目标出发。毕竟不是生竞选手，CGZ 被一道题难住了。 这道题是说，你若想编辑出一个基因 S（只含小写字符），第一步可以先去买下别人编辑好的 S 的一个前缀，若前缀长度为 L，则要花 $x*L$万元。然后，你可以做以下两个操作： 阅读更多…

题目链接 扩展 KMP 原来这么好写 强烈推荐 boshi 写的教程：戳我戳我！ 这题的话就是枚举旋转次数 旋转完的字符串就是一段后缀+一段前缀 那么判断大小关系就是要找到一个不相同的位置 所以就先找到那段后缀与原串的最长公共前缀（LCP）如果 LCP 长度是小于这段后缀的长度的，说明不同的字符在 阅读更多…

题目分析 题意转化为，有 $n$个数的序列，每个数你可以让它为一个 $[1,m]$之间的取值，问任意连续 $K$个数都线性无关的序列总数。 设 $m+1=2^c$ 那么若 $K>c$，因为若 $K$个数线性相关，那么它们一定可以通过异或的方式生成 $2^K$个不同的数，所以这种情况下任意 $K$个连 阅读更多…

题目链接_(:зゝ∠)_ 似乎还是比较简单的 首先用后缀数组求出 $Height$数组 由于两个后缀的 $lcp$是 $Height$的一段连续区间最小值，因此如果区间中有某处 $Height$值 $< k$，那么它就会把区间分成两段，左边一段和右边一段之间是不能构成 $k$相 阅读更多…

思路 设牛 $i$的叫声串长度为 $l_i$。假设时刻 $X$时，牛 $i$所处在它的叫声串中的位置为 $a_i$，那么时刻 $X$一定满足若干形如 $X \equiv a_i \pmod{l_i}$的方程。 若所有 $l_i$是互质的，根据 CRT，$X$在 $[0,lcm(l_i))$中有唯一解 阅读更多…

题目分析 称可以放置障碍的点为障碍点，假设 1 号点是一个不可防止障碍的障碍点。 将原图拓扑排序，拓扑序前一半障碍点和后一半障碍点分开考虑，那么一条路径一定是： 0号点->后一半障碍点中的某一个（并且它是第一个遇到的后一半障碍点）->1 号点 分开考虑后，前一半和后一半障碍点可以分别枚举它们放置障碍 阅读更多…

题目链接_(:з」∠)_ 这是 NOI 2016 D1T1 首先设 $a _ i$为以位置 $i$为左端点的形如 AA 串的个数 设 $b _ i$为以位置 $i$为右端点的形如 AA 串的个数 那么答案就等于： $$\sum _ {i = 1} ^ {n – 1} a 阅读更多…