HihoCoder – 1449 后缀自动机三·重复旋律6 后缀自动机、递推、DFS
后缀自动机三·重复旋律6 后缀自动机、递推、DFS Source HihoCoder - 1449 My Solution 题意：求一个字符串中，所有长度为K的子串出现次数最多的子串的出现次数，但是K不是固定的，求所有的K的答案。 …
HihoCoder – 1174 拓扑排序·一 拓扑排序、BFS
拓扑排序·一 拓扑排序、BFS Source HihoCoder - 1174 My Solution 拓扑排序基础题，判断图中是否有环。 拓扑排序、BFS 每次把入度为0的点删除后入队，进行BFS，最后如果有剩余没有删除的点，则存在环，否则…
HihoCoder – 1445 后缀自动机二·重复旋律5 后缀自动机
后缀自动机二·重复旋律5 Source HihoCoder - 1445 My Solution 题意：统计字符串中不同子串的个数。 后缀自动机 这题是后缀自动机基础题，直接使用SAM上的pre树， sigma{val[np] - val[pre[np]]} 复…
Gym – 101102B B. The Little Match Girl 贪心、数论、分步
B. The Little Match Girl 贪心、数论、分步 Source 2016 ACM Amman Collegiate Programming Contest UESTC 2017 Winter Training #1 Gym - 101102B My Solution 题意：给一串由火柴构成的数字，可以移…
UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造
去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造 Source 2017 UESTC Training for Graph Theory UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞 My Solution 题意：给出一个大小为n的集合S，集…
Codeforces Round #409 (Div. 2) C. Voltage Keepsake 二分
C. Voltage Keepsake 二分 My Solution 题意：每个设备初始电量为bi，每秒消耗ai，然后充电器每秒可以给一个设备充电p，问所有设备同时工作的最长时长。 二分 很显然的要用二分来做，然后check函数该怎么…
URAL – 1158 Censored! AC自动机+dp
Censored! AC自动机+dp Source URAL - 1158 ACM ICPC 2001. Northeastern European Region, Northern Subregion My Solution 题意：给出n个不同的字符，用这n个字符构成长度为m的字符串，要求每个串的子串都不出现…
Codeforces Round #352 (Div. 2) A. Summer Camp __ water problem
A. Summer Camp water problem My Solutions Use stringstream to build the line , then cout the str[n-1] #include #include #include #include using namespace std; int main() { int n; …
UVALive – 3703 Billing Tables Tire、字典树
Billing Tables Tire、字典树 Source UVALive - 3703, UVA - 1385, POJ - 3149 NEERC 2006 My Solution 题意：对于11位数字串(电话号码)，按优先级给定n个区间，每个区间有一个标记。若一个电话号码在某个区间内(…
Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) C. Felicity is Coming!组合学+集合
C. Felicity is Coming! 组合学+集合 My Solution 题意：给出n组数，每组gi个数，每个数属于1~m，每个数可以变化但变化前相同的数变化后依然相同，变化前不同的速变化后依然不同，且可能不变，但经过变化后每组的…
Codeforces Round #403 (Div. 2) B. The Meeting Place Cannot Be Changed 三分
B. The Meeting Place Cannot Be Changed 三分 My Solution 题意：n个人每个人在xi位置且运行速度为vi，问他们相聚在一点的最短时间。 三分 打那次cf 的时候，三分还没有学，没办法。 这里直接对[minx, ma…
Codeforces Round #403 (Div. 2) C. Andryusha and Colored Balloons DFS
C. Andryusha and Colored Balloons DFS My Solution 题意：给出一颗无根树，要求如果a-b相连 b-c相连，则要求abc涂上不同的颜色，要求用最少的颜色给这颗树上色且求具体涂色。 DFS 首先这个最少的颜色数…
SGU – 465 Fire Station Building floyd+三分
Fire Station Building floyd+三分 Source SGU - 465 Gym - 100206B My Solution 题意：有n个城市m条双向边，计划在一条道路上建立一个消防局，并且它离城市的距离不能小于R，每个城市i有一个发生火灾的概率pi，要…
Codeforces Round #394 (Div. 2) A. Dasha and Stairs 易错
A. Dasha and Stairs 易错 My Solution 易错 对于 0 0 这组数据要进行特殊的判断，比赛的时候用这组数据hack了十几个人， 当时这个有趣的题忘了记录下来了，现在补上，^_^ #include #include #include…
Codeforces Round #404 (Div. 2) D. Anton and School – 2 前缀的后缀、 范德蒙恒等式、容斥
D. Anton and School - 2 前缀的后缀、 范德蒙恒等式、容斥 My Solution 题意：给出一个只有"("和“)"的字符串，为有多少个子序列，它的长度为len，则左边len/2个字符为”("右边len/2个字符为")"，问这样的子序列有…
HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置
Substring 后缀自动机+二分 Source HDU - 5769 My Solution 题意：每次给出一个字母ch和一个字符串s，求s中有多少个不同的子串含有字母ch。 后缀自动机+二分、新增distinct子串的个数和位置 首先这里要用到后缀自…
Codeforces 17E Palisection 回文自动机+邻接表
E. Palisection 回文自动机+邻接表 My Solution 题意：给出一个字符串要求找出多少对有相交部分的回文子串。 回文自动机+邻接表 首先，直接求这个问题比较麻烦，故可以转化为总的回文子串的对数减掉不相交…
URAL – 1960 Palindromes and Super Abilities 回文自动机
Palindromes and Super Abilities 回文自动机 Source URAL - 1960 My Solution 题意：逐个字符的添加一个字符串，问每添加一个字符显存的字符串的总不同的回文子串的个数。 回文树自动机 首先推荐篇比较好的讲回文…
HDU – 4622 Reincarnation 后缀自动机
Reincarnation 后缀自动机 Source HDU - 4622 My Solution 题意：给出一个长度<=2000的字符串，然后给出q<=10000个询问，为s[l,r]内有多少个不同的子串。 后缀自动机 首先n <= 2000，故可以用O(n^2)的算…
SPOJ – LCS Longest Common Substring 后缀自动机
Longest Common Substring 后缀自动机 Source SPOJ - LCS My Solution 题意：求两个字符串的最长公共子串。 后缀自动机 看了很久 WJMZBMR 讲后缀自动机的ppt才大致把后缀自动机搞懂^_^, 此外附上两个比较好的…
