文章

FFT [TPLY] 题目链接 https://www.luogu.org/problemnew/show/1919 https://www.luogu.org/problemnew/show/3803 资料推荐 orz 大佬博客 http://www.cnblogs.com/cjoieryl/p/ 阅读更多…

1. 引言 今天考试遇到一个提交答案题，已经给出了答案检验器（已经编译了的，没有源码），但是手动输命令检验答案文件效率很低，我们最好是让检验器本来输出到屏幕的东西输出到文件，方便我们写程序自动检验。 但是我们没有检验器源码，没法 freopen 怎么办呢 QvQ 其实是 kb 提出了这个问题啦，下面 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 因为把字符串接成了一个环，所以我们把字符串复制一遍以后接在原字符串后面。（比如 abc 变成 abcabc）接着我们求出复制后的字符串的后缀数组 $SA$。 最后依次输出 $str[SA[1,n]]$就行了。 这里要注意一下：$str$指的是复制后的字符 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 求出后缀数组和（排名为 $i$的后缀与排名为 $i-1$的后缀的最长公共前缀）即可。 具体参加 KBの【算法】后缀三兄弟之二——后缀数组　　——litble（在文章尾部有讲 QvQ，Thanks KB%%%% 代码： #include <bits/st 阅读更多…

动态区间第 k 大的一种 $O(nlog^2n)$的树套树解法 题意： 给定一个序列，有 “将一个数修改为另一个” 的操作，和询问 “[l,r] 区间内的第 k 小值是几” 的询问。要求在 1s 内对一个长 $10^4$的序列完成 $10^4$组修改和询问。 思路： 1. 我最先想到的树套树的思路是 阅读更多…

What is 后缀自动机？ 我们先来看一下字符串 abbb 的后缀自动机，接下来你可以通过这幅图来参考后缀自动机的概念。 后缀自动机是一个可以处理一个字符串的有向无环图，它存在一个起始点，由很多个节点和很多条边组成，这些节点叫做状态，这些边叫做转移。 后缀自动机每条边上都写有一个字母，那么我从起始 阅读更多…

原题戳我 坡机裸提 题目描述： Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinat 阅读更多…

0. 引言 之前一堆神犇压榨廉价劳动力让我帮他们（或她们）的 Ubuntu 安装 QQ，然后他们（或她们，下文省略）又对 wineqq 很不爽（老崩溃），所以我只能再发一篇文章讲一下在 Ubuntu 下如何用 CrossOver 安装兼容性比较好的 QQ（或 TIM）吧。 1. 安装 CrossOv 阅读更多…

什么是后缀数组? 假设我们现在有一个字符串”ababa” 我们知道这个数组有一些后缀，分别是（以下后缀 i 指以 i 为开头的后缀）1 2 3 4 5 ababa baba aba ba a 现在我们按照字典序将它们排序，得到:5 3 1 4 2，那么我们令 $SA_1=5 阅读更多…

1. 题目 传送门=￣ω￣= 题意：给定从左到右 $n$个矩形，已知这此矩形的宽度都为 1，分别给出它们的高度。这些矩形排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形 矩形个数<=100000，有多组数据 2. 题解 其实我一开始是在 CCF 资格认证考试题里看到这题的 但那里数据范 阅读更多…