BZOJ1212: [HNOI2004]L语言
传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=1212 Solution 注意到单词长度很小,用Trie树+DP可以水过,f[i]表示能否匹配到第i位,若f[i]==1,则从i+1位置继续匹配,因为单词长度≤10,暴力
BZOJ2081: [Poi2010]Beads
Description 给定一个长度为n的数字串,求所有的k满足当将这个数字串从左到右分成大小为k的块时不同的块数量最多(反转同构算同一种). Input 共有两行,第一行一个整数n(n≤200000)代表珠子的长度,第二行是由空格分开的颜色ai(1≤ai≤n). Outpu
BZOJ1452: [JSOI2009]Count
传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=1452 Solution 练习一下二维树状数组,其实只是多了一层循环QWQ.稍微注意一下容斥就过啦. Code 123456789101112131415161718
51nod1526 分配笔名
传送门: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1526 Solution 很裸的Trie树.先按真名建一棵Trie树,记下每个节点的数量.读入笔名时在Trie树里往下找,如果该节点数量大于0
BZOJ3670: [Noi2014]动物园
传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=3670 Solution 求next数组时可以顺便求出每个前缀的border的个数,记为cnt.统计答案的时候强制使匹配长度小于i/2就可以了. Code 123456
51nod1277 字符串中的最大值
传送门: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1277 Solution KMP中next数组可以求出每个前缀最长(小于本身)的border,显然一个前缀A出现的次数就是以A为最大(小于本身
BZOJ1954 Pku3764 The xor-longest Path
Description 给定一棵n个点的带权树,求树上最长的异或和路径. Input 第一行包含一个整数n(1≤n≤100000),下面的n-1行每行包含三个整数u(0≤u﹤n),v(0≤v﹤n),w(0≤w﹤n),表示节点u和v之间 的长度为w. Output 输出最长异或和
2017.3.15模拟赛T2
Description 不告诉 Solution 可以用O(N*M)的时间预处理处每位数对每个位置的贡献(系数),只需要O(1)的时间修改,查询的时候就只要O(n)求一遍和就可以了.注意中间过程int可能会爆,要用快速乘或开long long. Code不给看
2017.3.15模拟赛T1
Description 不告诉 Solution 很水的DP题,设f[i][j][k]表示当前i位,num1=j,num0=k时的方案数(第一维可以用滚动数组压掉).显然f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]+f[i-1][j][k-1]，
BZOJ1355 [Baltic2009]Radio Transmission
Description 给你一个字符串,它是由某个字符串不断自我连接形成的.但是这个字符串是不确定的,现在只想知道它的最短长度是多少. Input 第一行给出字符串的长度,1<L≤1000000. 第二行给出一个字符串,全由小写字母组成. Output 输出最短的长度. S
