题意： 给出2个字符串(2.5E5)，问最长公共子串的长度。 思路： 拿一个串建SAM 由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了 20171110UPdate:我好像说得太简略了。。 参考clj的冬令营讲稿： * 给两个长度小于100000的字符串A和B，求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM * 对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代表的是结束位置在r的，长度在[Min(s),Max(s)]之间的所有子串。 * 我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹配的最大长度L，那么min(L,Max(s))就可以更 …

题意： 有这样一个有关最大公约数的函数: 函数 f(x, y): { c=0 当 y>0: { c +=1 t = x % y x = y y = t } 返回 c * x * x } 给出三个正整数n,m,p，你需要计算: $$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$ n <= 666,666,666, m <= 666, p <= 666,666,666。 思路： 打表找规律。 但是找规律也要按照基本法 观察到m比较小，对于固定的j,容易看出f(i,j)和f(i+j*k,k)是等价 …

http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意： 给出两个序列 a 和 b ，求满足 f[i]= b_{f[a[i]]} 的函数个数。 思路： 分别找两个序列的循环节，这一点是比较容易想到的。 由于点都在0..n-1 或者0..m-1，因此没必要建图跑dfs找循环节，直接while就可以了。 然后发现一个循环节如果符合条件，那么对答案的贡献是循环节长度。 但是没有想清楚，什么才是符合条件的循环节。 结论是，b的循环节长度当且近当是A的循环节的长度的因子时，b的这个循环节会对答案贡献其长度的大小。 对于A的每个循环节，都是互不影响的。 而且我们只关心循环节的长度。 因此O（n） …

http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意： 有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0. 思路： 贪心。看哪个字母的权值最大。 可以用类似高精度加法的方式处理。 对于前导0的部分，用一个bool标记首位（如果字符串长度为1就不标记） 对于26个高精度数的排序，可以用交换id的技巧。 以及，如果排序之后，发现权值最小的数被对应到数字0，但是又在某个长度大于1的字符串的首字母位置出现过。 我初始想当然得，把该字母和最小的可以出现在首位的字 …

1230: [Usaco2008 Nov]lites 开关灯 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1676 Solved: 874 [Submit][Status][Discuss] Description Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= …

http://acm.hdu.edu.cn/showproblem.php?pid=6043 题意： n双袜子标号1到n，初始在抽屉里，每天早晨穿一双标号最小的袜子，晚上把脏袜子放到盆里，如果放完之后喷子里已经有了n-1双脏袜子，那么就要洗，然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。 思路： 手写了几个发现对于n双袜子,标号出现的情况是: 1,2,3...n,1,2,3...n-2,n-1,1,2,3...n-2,n 所以特判k<=n的情况然后算循环的次数即可。 /* *********************************************** Author :111qqz Created …

http://acm.hdu.edu.cn/showproblem.php?pid=6033 题意： 问最大的x,满足 $$ 10^{x} \geq 2^{m}-1 $$ 思路： 看到指数的比较大小，直觉就是取下对数啦 其实直接可以把1忽略，因为2的幂次显然不会出现末尾是0，所以不会影响结果 两边对10取对数得到 $$ x\leq \log_{10} 2^{m} $$ 右边用换底公式就是 $$ \frac{m}{\log_{2}10 } $$ 代码： /* *********************************************** Author :111qqz Created Time :2017年10月31日 …

1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss] Description 　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择 矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换 对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的 …

1191: [HNOI2006]超级英雄Hero Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss] Description 现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设 …

题目链接： 题目链接 题意： 一段程序，最多5E5个操作，每个操作的格式为 <opt,x> ，opt表示位或，位异或，位与 三种位运算的一种，x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作，使得对于0..1023的输入，输出与该程序同样的结果。 思路 ： 关键在于想起，位运算还是按照二进制位的运算。我们考虑每位即可。 如果初始是0，现在变成了1，那么实际上我们并不确定，这个操作是xor 1 还是 or 1 因此我们需要两个初始的数，一个所有二进制位上都是0，另一个所有二进制位上都是1. 也就是0和1023 对于某个二进制位 如果初始的 （0，1）变成了 （1，1），那么说明这个位置上的位运算是or 如 …