文章

题意：给定一个长度为 n 的序列，m 个询问 [a,b]，求 [a,b] 间最大子段和的开头和结尾。 思路：用线段树解答，每个节点保存对应段的最大前缀的结尾位置，最大后缀的开头位置，最大子段的开头结尾位置。询问时将 [a,b] 间的线段数中的区间从左到右依次取出，保存为约 log2(b-a) 个子段 阅读更多…

题目描述： Miracle Corporations has a number of system services running in a distributed computer system which is a prime target for hackers. The system is 阅读更多…

我应该要滚粗了，这么一道水题目都交了 3 遍才 A，发现是一个<=手误写成了<。我真的要滚粗了…. 因为注意到一句这样神奇的话：每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不 阅读更多…

题意：给定一组长度为 n 的不降序列，及 q 个询问 [l,r]。求 [l,r] 中出现最多的数出现了几次。 分析：把相同的数（肯定是连续的）分组，记录每组有几个数、结尾的数字是原数组第几位、每组包括的数是什么。在同时记录下原数组的每个数对应第几组。这些工作在 O(N) 的时间内完成。然后通过预处理 阅读更多…

我现在要抨击一下 boshi 大神的做法，真是不够优美…… 一份优美的代码应该是短，便于看懂而且能够 AC 的，所以说….. 干嘛啊。 寻找循环节，其实跑一遍 kmp 就够了，如果存在循环节的话，肯定是 n-next[n] 这个长度的前缀。 比如说 ababab， 阅读更多…

题意：给定一个 k*k 的矩阵，要求你每行选一个数，把他们相加得到 kk 个和。输出最小的 k 个和。(k<=750, 多组数据) 分析: 首先我们从一个简单的问题入手。如果只有 2 行，每行 k 个数，最小的 k 个和怎么求？ 先将这两行的数字升序排序, 设第一行为数组 A，第二行为 B，构 阅读更多…

这是一道水题 给定几个特征串和几个字符串，求每个字符串中有那几个特征码 思路： 把每个特征串放到 TRIE 树里（上），用 AC 机挂着每个串跑一遍即可。但是会出现一种情况：若 B 串为 A 串子串，则可能出现没有匹配到 B 串的情况。比如 ABCD 和 BC，如果用不加修饰的 AC 机跑，会直接把 阅读更多…

给定一个字符串，求它最多由几个循环节构成。 思路：很自然地想到要求这个字符串最少后移几位后与自己匹配 #include <cstdio> #include <cstring> #define MX 10000001 using namespace std; char src[ 阅读更多…

niconiconi，本人 ZYF，是一个妮可厨，这篇博客的主人 XZY 不在，所以暂时由我来打理，我不会用 markdown，所以写出来的文章很难看，大家可以将就着看一下。上面两篇写得很奇怪的博客就是我写的，我自己的博客在：http://cnblogs.com/1-1-1-1 欢迎各位大佬参观。

概率 01 背包