传送门 ##题意： 给你n个数w和一个数p，q个询问，每次询问一个区间[l,r],求 w l ( w l + 1 ( w l + 2 . . . w r ) ) m o d    p w_l^{(w_{l+1}^{(w_{l+2}...^{w_r})})}\mod p wl(wl+1(wl+2​...wr​)​)​modp ##Solution: 这道题类似于BZOJ3884 但是稍有一点不同： 根据扩展欧拉定理：  a b ≡ { a b % ϕ ( p )             g c d ( a , p ) = 1 a b                    g c d ( a , ...

传送门 题意： n个数a，q个操作，两种操作类型： 1.[l,r]区间中每个数替换为这个数的因数个数 2.区间求和  q,n<=3e5,ai<=1e6  q , n <= 3 e 5 , a i <= 1 e 6  Solution: 值为1或2的数是不需要再进行操作的 对于每个线段树节点所代表的区间，开一个布尔变量v表示这段区间是否全为1或2 可以证明每个数最多被替换log次 总复杂度 O(nlog2n)  O ( n l o g 2 n )  代码： #include<cstdio> #include<iostream> #include&l...

传送门 题意： 给出一个字符串，求不等于前后缀的最长的一段子串，使得这段子串即是前缀也是后缀 Solution: 这道题如果使用KMP解决并不这么直观 使用z算法可以轻松地解决（如果没有学过z算法请点击这里） 处理出z数组后，我们记录前i项的z的最大值 对于第i+1项，如果z[i+1]+i==len&&max[i]>=z[i+1],即从i+1开始能匹配到后缀,且前面存在一个相同的串，他所代表的串就是符合条件的 找到最大的即可 代码： #include<cstdio> #include<iostream> #include<cstring&gt...

传送门 题意： 给出文本串的长度n，给出模式串以及模式串在文本串中出现的位置，求有多少种文本串满足条件。 Solution: 在文本串中暴力加入模式串，最后判断匹配位置是否和给出的相符即可。 代码（z-box赛高！）： #include<cstdio> #include<iostream> #include<cstring> using namespace std; int z[2000010],n,m,r,l,p; char b[2000010],a[1000010]; int maxn=0,ar,x; int ans[1000010]; int wei;...

传送门 题意： 给出两个分别为n,m项的字符串 求第二个字符串在第一个中出现几次 字符串按照 (li,ci)  ( l i , c i ) 的形式给出 (如2-a 2-b 1-c 表示aabbc)  n,m<=2e5 l<=1e6  n , m <= 2 e 5   l <= 1 e 6  Solution: 直接匹配比较困难 观察发现去掉模式串的首尾两端 中间的串和文本串是完全匹配的，对于完全匹配问题，我们使用双关键字KMP/双关键词x-box即可 最后对于每个匹配位置判断一下头尾即可 注意需要合并连续的相等的c，特判m=1 代码： #include<cstdi...

传送门 题意： 给出一个长度为n的文本串和m个模式串，求有多少个模式串可以拆成两半，使得这两半按顺序匹配 (n<=2e5,m<=100) Solution： 先正着跑一遍KMP,pos[i]表示模式串中最早能匹配到第i个字符的位置 然后把文本串和模式串都取反，再跑一遍KMP，求出文本串的每个位置i所能匹配的最长的模式串长度z[i]，设模式串长为len,那么我们只需要比较i和pos[len-z[i]]的关系即可，具体推一推即可 注意特判len=1的情况 代码： #include<cstdio> #include<iostream> #include<cs...

简介 z-box算法可用于普通KMP、扩展KMP，国外非常流行但是国内却几乎没有人用，这种算法在解决许多字符串问题时都比KMP要直观许多。 算法详解 对于一个字符串s,设它的长度为len z[i]所表示的是s[i…len-1]与s[0…len-1]的最长公共前缀 如何求出z[i]数组？ 递推即可 对于一个新的i,我们把i前面的所有z[j]看成一个区间[j,z[j]],记录右端点最大的区间[l,r],如果i>r,那么我们暴力和s[1..len]进行匹配，代码如下（注意下标从0开始）: if (i>r) { int t=i,bg=0; while (b[t]==b[bg]) t++,b...

传送门 题意： 给一个循环串A，和一个字符串C，求一个最长的A的子串B，使得将B首尾相接成一个循环串后，C是B的子串。 Solution： 我们把A翻倍拼接，就可以消掉”A是循环串”z这个限制，发现C可以拆成一个前缀和一个后缀 我们可以求出翻转前的z数组z1以及翻转后的z数组z2，分别表示了C在每个位置可以匹配到的前缀和后缀 设C的长度为len，对于每个长度为i的前缀，我们对于长度>=len-i的后缀存一个set，然后在set中寻找距离他最远的满足要求的后缀的位置，这样就能找到关于这个前缀的最长B串 思路想起来很容易但是细节很多，容易推错（对于各种+1-1，实在想不明白可以通过举例子的方...

传送门 题意： 给出N,X,Y,Z,定义一个合法的序列为长度为N,每个元素的取值为[1,10]的整数序列,序列满足其有四个下标x,y,z,w  使得a[x]+a[x+1]..a[y-1]=X,a[y]+a[y+1]+..a[z-1]=Y,a[z]+a[z+1]+.a[w]=Z 求合法序列个数(3≦N≦40,1≦X≦5,1≦Y≦7,1≦Z≦5) Solution: 这道题从正面思考的话会发现方案数会算重复，难以去重，尝试从反面考虑这件事：总方案数减去不合法的方案。 如何求不合法方案数呢？ 注意到数字都非常小，我们可以把每个数转化成一个01串，例如1=‘1’,2=’10’,5=’10000’ 这样...

题意： 定义一种字符串gray串满足： 1.长度为奇数 2.正中间的字母只出现一次 3.左右两端相同，左右两端也是gray串 一个gray串的贡献为这个串长度的平方 现给你一个长为n的字符串，你可以修改至多一个字母，使得总贡献值最大 (n<=1e5) Solution: 可以发现gray串的长度是倍增的，所以最多有log种不同长度的gray串，这样的话我们可以考虑串中每个位置的贡献，这种贡献可以类似倍增预处理求出，然后我们再处理 val[i][j]  v a l [ i ] [ j ] 表示如果第i位为j会产生多少贡献，最后把修改后贡献和初始贡献相减即为可能的变化贡献 可能val数组不好...

传送门 题意： 给出n个字符串，要求按给出的顺序选择一些字符串，使得这些字符串按顺序拼起来后长度为k且字典序最小 Solution: 正解目前还不会…先写一波学来的暴力算法：  can[i][j]  c a n [ i ] [ j ] 表示后i个是否可以组成长度为j的字符串 先加入初始能加入的串，存入一个数组中 然后顺序枚举答案串的每一位，对于每一位贪心找出最小字典序，对于最优状态向后转移，转移分为两种： 1.当前这个串未到末尾，这种情况直接向后转移即可 2.当前这个串到末尾，这种情况只需记录最早的到末尾的串，枚举他后面的串是否符合条件即可 注意预处理需要使用bitset优化 复杂度O(能过)...

传送门 题意： 密码是一个长度为奇数的回文串，现在我们对这个密码进行加密：把密码分成 3 段，最前面的 X 个字符为一段，最后面的 X 个字符为一段，剩余的字符为一段。这三段依次称之为 prefix, suffix, middle 。middle 的长度为一个大于 0 的奇数， prefix 、 suffix 的长度相等。加密后的密码即为 A + prefix + B + middle + C + suffix ，其中 A 、 B 、 C 是三个字符串，且都有可能为空， + 表示字符串相连。 先给出加密后的长度为n的字符串，求最长可能的密码串。 (n<=1e5) Solution： 第一...

vjudge传送门 题意： 每一位数对应一种BCD编码： Decimal:  0 1 2 3 4 5 6 7 8 9 BCD:  0000 0001 0010 0011 0100 0101 0110 0111 1000 1001r 如127对应的BCD编码是0001 0010 0111 先给出n个不合法的BCD编码串，求[A,B]中转化成BCD编码后不包含这n个编码串中的任意一个的数的个数  0<A≤B<10200  0 < A ≤ B < 10 200  n<=100,字符串长<=20 Solution: 一眼AC自动机+数位dp  f[i][j][0/1...

传送门 题意： 给你一个字符串，n个操作 [li,ri]  [ l i , r i ] ,每次操作把区间内的字符串复制一遍并打乱接在后面，打乱的规则为：  s1s2s3...sn−>s2s4s6...s1s3s5...  s 1 s 2 s 3 . . . s n − > s 2 s 4 s 6 . . . s 1 s 3 s 5 . . . ,求n次操作后结果的前k个字符 Solution: 这道题正着去考虑不是很好想，我们尝试反着来思考：假设现在得到了结果串，我们把它进行还原，显然还原的时候字符串长度会越来越短，所以我们只需考虑前k个即可，每次还原的时候，我们可以确定复制区间 ...