下一页 »Current position : 首页 >> 字符串
PKU2019数据结构与算法实习作业 11~21
题目来源：http://dapractise.openjudge.cn/2019hwall/多模式串字符串匹配模板题AC自动机模板题[crayon-5f28467937be6010286379/]POJ3987ComputerVirusonPlanetPandora[crayon-5f28467937bf6823273324/]躲不开的病毒找自动机上的环[crayon-5f28467937c02094432856/]POJ3691DNArepairDP，考虑前i个字符且停留在trie树上编号为j的节点时，字符串所修改的最小次数[crayon-5f28467937c0a948095989/]POJ3450Corpor...
PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-5f2846793925c318737399/]POJ1860CurrencyExchange最短路模板[crayon-5f28467939268544418520/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
「CF1280X」Codeforces Round #607 (Div. 1)
A.CutandPaste长度在x范围内，直接模拟字符串合成，达到x范围外直接通过计数得到答案[crayon-5f28467939923185829754/]B.Beingawesomeism首先答案不超过4，分类讨论一下123的情况，其中2有两种情况：有角上的点，有整行/列的点[crayon-5f2846793992c175207900/]C.JeremyBearimy考虑一条边，如果一侧有奇数个点，这条边至少计入结果一次一条边计入结果的最大次数是两侧点个数的较小值，为什么所有边都能达到这个较小值？假设...
2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-5f2846793a5f3710409859/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-5f2846793a5fd814860532/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
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把一个文本...
《数据结构与算法》作业 —— KMP
英文好难，我好菜QAQ你们这里洋文好的人多得很哪求神犇指点
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次...
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-5f2846793babc751624536/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-5f2846793bac5100038189/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-5f2846793bacb698699419/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-5...
「小奇模拟赛」小奇的自动机
「题目背景」小奇在研究后缀自动机时遇到了一个难题。「问题描述」定义：如果字符串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。「输出格式」输出...
「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组询问：不存在...
「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-5f284679526c5324888709/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-5f284679526cd804012768/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-5f2846795...
近期评论