字符串 - hzwer.com

2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
02017年3月7日3,971递推与动规,贪心,二分法,最大流,AC自动机,快速幂,拓扑排序,欧拉函数

2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-5d071dd1db3db178860936/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-5d071dd1db3e6518104600/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
02016年11月6日2,160递推与动规,模拟,贪心,KMP,构造,深度搜索,主席树,二分法
2016 ACM / ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
12016年10月8日3,461哈夫曼树,STL,最小割,dijkstra,深度搜索,二分法,欧拉图,AC自动机,记忆化搜索
《数据结构与算法》作业 —— KMP
英文好难，我好菜QAQ你们这里洋文好的人多得很哪求神犇指点
12016年10月8日2,607KMP
2016 Multi – University Training Contest 5
本场抱住卓神大腿最后过了7题。。。感觉把PKU的牌子砸了。。。我做了100110051011随便口胡几句。。。1010看起来像后缀数组。。。但是交wa了几发不知道什么情况1001ATMMechine这题似乎0元钱也要取1次1元的来确认一下，不然没法解释样例\(f(i,j)\)表示有i元以内的钱，j次warning的机会然后枚举询问点k，有t种可能warning，那么转移给\(f(t-1,j-1)\)有i-k+1种可能取钱，转移给\(f(i-t,t)\)边界j为1的情况，有k元钱需要询问k+1次...
12016年8月3日2,828递推与动规,回文自动机,概率与期望
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-5d071dd1dc957179826254/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-5d071dd1dc960446896425/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-5d071dd1dc979678983700/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-5...
42016年6月30日2,798递推与动规,KMP,后缀数组,最大流
「小奇模拟赛」小奇的自动机
「题目背景」小奇在研究后缀自动机时遇到了一个难题。「问题描述」定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。「输入格式」第1行1个整数n。接下来n行，第i+1行包括1个字符串Si。再接下来n行，第n+1+i行的整数表示Ki。「输出格式」输出...
02016年5月21日1,944字典树,线段树
「BZOJ3230」相似子串
DescriptionInput输入第1行，包含3个整数N，Q。Q代表询问组数。第2行是字符串S。接下来Q行，每行两个整数i和j。（1≤i≤j）。Output输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。SampleInput53ababa3559810SampleOutput1816-1HINT样例解释第1组询问：两个子串是“aba”,“ababa”。f=32+32=18。第2组询问：两个子串是“ababa”,“baba”。f=02+42=16。第3组询问：不存在...
12015年7月9日3,039后缀数组
「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-5d071dd1ddce6930369213/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-5d071dd1ddd02367363430/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-5d071dd1d...
02015年6月15日3,125深度搜索,广度搜索,后缀自动机,概率与期望,莫比乌斯反演
2015全国互测 1
计算给定n,m对于[1,n]不包含m作为其子串的数k求\(\sum_ke^{k/n}\)kmp预处理后数位dp。。。[crayon-5d071dd1de359257657955/]移动小x有n张卡片和n个卡槽，现在第i张卡片在ai卡槽中。小x每次可以把一个在a位置的卡片移动到b位置，消耗的代价为min(|a−b|,n−|a−b|)，每张卡片可以被移动多次。小x想使得每个卡槽有且仅有一张卡片，请你告诉他最少需要的代价是多少。环形分金币参加白书[crayon-5d071dd1de36e523876791/]分离小x喜欢分...
02015年5月17日1,469KMP,深度搜索,数位动规
「BZOJ3160」万径人踪灭
大爷题解传送门：http://blog.csdn.net/popoqqq/article/details/42193259[crayon-5d071dd1ef45a851367081/]
02015年5月1日4,809manacher,快速傅里叶变换
「BZOJ3926」[ZJOI2015] 诸神眷顾的幻想乡
陈老师语文水平高超陈老师的博客：http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/[crayon-5d071dd1ef8b4380981424/]
02015年5月1日4,427深度搜索,后缀自动机