111qqz的小窝

老年咸鱼冲锋!

SPOJ SUBLEX Lexicographical Substring Search ( 后缀自动机)

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

spoj nsubstr Substrings (后缀自动机 模板题)

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

poj 1949 Chores (拓扑排序+dp)

http://poj.org/problem?id=1949 题意: 有n个任务,第i个任务需要时间xi来完成,并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。 给你任务信息,问你最短需要多少时

hdu 4777 Rabbit Kingdom (树状数组+预处理)

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

poj 3249 Test for Job (拓扑排序+dp)

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

hdu 6048 | 2017 Multi-University Training Contest - Team 2 D Puzzle (结论题)

http://acm.hdu.edu.cn/showproblem.php?pid=6048 题意: 有 n * m - 1 个数,每次选择第 1,p + 1,p * 2 + 1….. 的顺序选择数,先按左到右,再按从上到下的顺序填入n * m 的格子,空格子可以和相邻的数字

hdu 4782 | 2013 Asia Chengdu Regional Contest B (模拟)

http://acm.hdu.edu.cn/showproblem.php?pid=4782 题意: 将格式混乱的html代码输出成标准格式。 思路: 模拟。 说下细节: * 遇到open tag,先打印,后dep++ * 遇到close tag,先d

【施工中】SAM学习笔记

怕是老年人的最后一篇算法学习笔记了心情不好,此文无限期tj概述 主要讲解在我学习的过程中比较难理解的地方..并不保证全面 首先,后缀自动机是一个

poj 1509 Glass Beads (后缀自动机求最小循环表示)

题意: 给定一个循环字符串,问字典序最小的串的开始位置。 思路: 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n

hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意: 给一个字符串,给出若干询问,每组询问给一个区间[l,r],问区间中本质不同的字符串的个数。 思路: 观察发现,有10000组查询,字符串

SPOJ LCS Longest Common Substring (后缀自动机模板题)

题意: 给出2个字符串(2.5E5),问最长公共子串的长度。 思路: 拿一个串建SAM 由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿

HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)

题意: 有这样一个有关最大公约数的函数: 函数 f(x, y): { c=0 当 y>0: { c +=1 t = x % y x = y y = t } 返回 c * x * x } 给出三个正整数n,m,p,你需要计算: $$

hdu 6038 | 2017 Multi-University Training Contest - Team 1 E Function (置换群找循环节)

http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意: 给出两个序列 a 和 b ,求满足 f[i]= b_{f[a[i]]} 的函数个数。 思路: 分别找两个序列的循环节,这一点是比较容易想到的。 由于点都在0..n-1 或者0..m-

hdu 6034 2017 Multi-University Training Contest - Team 1 B Balala Power! (贪心)

http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意: 有一个仅由小写字母组成的字符串,要求将a..z的字母,对应到0..25,每个数字只能被一个字母对应,得到一个26进制的数,现在问这个

BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改,区间查询)

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

hdu 6043 | 2017 Multi-University Training Contest - Team 1 K KazaQ's Socks (循环节)

http://acm.hdu.edu.cn/showproblem.php?pid=6043 题意: n双袜子标号1到n,初始在抽屉里,每天早晨穿一双标号最小的袜子,晚上把脏袜子放到盆里,如果放完之后喷子里已经有了n-1双脏袜子,那么

hdu 6033 | 2017 Multi-University Training Contest - Team 1 A Add More Zero

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

bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5251 Solved: 2512 [Submit][Status][Discuss] Description 小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。

BZOJ 1191: [HNOI2006]超级英雄Hero (匈牙利)

1191: [HNOI2006]超级英雄Hero Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss] Description 现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的

codeforces div 1 443 A. Short Program (位运算的理解)

题目链接: 题目链接 题意: 一段程序,最多5E5个操作,每个操作的格式为 <opt,x> ,opt表示位或,位异或,位与 三种位运算的一种,x表示范围0..102