ACM

http://www.spoj.com/problems/SUBLEX/en/ 题意： # 给一个字符串，每次询问字典序第k大的不重复子串。 思路： # 先做个拓扑dp，求出SAM上，一个状态到终态的路径数。

http://www.spoj.com/problems/NSUBSTR/en/ 题意： # f[i]指长度为i的串出现次数的最大值。这里的不同出现指，可以有重复串，只要起始位置不同就视为不同的出现。 求f[1]..f[lenth]。

http://poj.org/problem?id=1949 # 题意： # 有n个任务，第i个任务需要时间xi来完成，并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。

https://vjudge.net/problem/47450/origin 题意： # 有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？ 思路： # 想到了预处理每个数最左最右的，最远的互质的数的范围。。

http://poj.org/problem?id=3249 题意： # 给一个DAG，现要从一条入度为0的点到一个出度为0的点，问最大点权和。 思路： # 其实比较容易想到搜…不过复杂度会炸？

http://acm.hdu.edu.cn/showproblem.php?pid=6048 题意： # 有 n * m - 1 个数，每次选择第 1,p + 1,p * 2 + 1….. 的顺序选择数，先按左到右，再按从上到下的顺序填入n * m 的格子，空格子可以和相邻的数字交换位置，问最后能否在格子中形成 1~ n * m - 1的数按从左到右，从上到下的顺序。

http://acm.hdu.edu.cn/showproblem.php?pid=4782 题意： # 将格式混乱的html代码输出成标准格式。 思路： # 模拟。 说下细节： * 遇到open tag，先打印，后dep++ * 遇到close tag，先dep--，再打印 * 遇到空标签，直接在当前深度打印 * 遇到空白字符时，只有当前面出现了text以及后面也出现了text的时候才打印。**也就是说第一个string和最后一个string都是紧邻标签的。** 最坑的一点是…虽然题目给了数据组数，但是在所在行的同一行，可能出现下一组的开始

在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机 怕是老年人的最后一篇算法学习笔记了 心情不好，此文无限期tj 概述 # 主要讲解在我学习的过程中比较难理解的地方..并不保证全面

题意： # 给定一个循环字符串，问字典序最小的串的开始位置。 思路： # 之前用poj 1509 解题报告-字符串的最小表示法 A过

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意： # 给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。 思路： # 观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。

题意： # 给出2个字符串(2.5E5)，问最长公共子串的长度。 思路： # 拿一个串建SAM 由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了

题意： # 有这样一个有关最大公约数的函数： 函数 f(x, y): 1{ 2 c=0 3 当 y>0: 4 { 5 c +=1 6 t = x % y 7 x = y 8 y = t 9 } 10 返回 c * x * x 11} 给出三个正整数n,m,p，你需要计算：

http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意： # 给出两个序列 a 和 b ，求满足 f[i]= b_{f[a[i]]} 的函数个数。 思路： # 分别找两个序列的循环节，这一点是比较容易想到的。

http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意： # 有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0.

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 <= M <= 100,000)条指令， 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 它们表示起始开关和终止开关. 奶牛们只需要把从S_i到E_i之间的按钮都按一次， 就可以完成这个指令. 第2种指令(用1表示)同样包含两个数字S_i和E_i (1 <= S_i <= E_i <= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.

http://acm.hdu.edu.cn/showproblem.php?pid=6043 题意： # n双袜子标号1到n，初始在抽屉里，每天早晨穿一双标号最小的袜子，晚上把脏袜子放到盆里，如果放完之后喷子里已经有了n-1双脏袜子，那么就要洗，然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。

http://acm.hdu.edu.cn/showproblem.php?pid=6033 题意： # 问最大的x，满足 \[ 10^{x} \geq 2^{m}-1 \] 思路： # 看到指数的比较大小，直觉就是取下对数啦 其实直接可以把1忽略，因为2的幂次显然不会出现末尾是0，所以不会影响结果

1059: [ZJOI2007]矩阵游戏 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss] Description # 小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）；列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）。游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。

1191: [HNOI2006]超级英雄Hero # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss] Description # 现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

题目链接： 题目链接 题意： # 一段程序，最多5E5个操作，每个操作的格式为 <opt,x> ，opt表示位或，位异或，位与 三种位运算的一种，x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作，使得对于0..1023的输入，输出与该程序同样的结果。