Fizzmy

分类

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章（共123篇）

Codeforces 631D Messenger-字符串匹配

传送门题意：给出两个分别为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...

2021-08-18

0 365

Codeforces 149E Martian Strings-字符串匹配

传送门题意：给出一个长度为n的文本串和m个模式串，求有多少个模式串可以拆成两半，使得这两半按顺序匹配 (n<=2e5,m<=100) Solution：先正着跑一遍KMP,pos[i]表示模式串中最早能匹配到第i个字符的位置然后把文本串和模式串都取反，再跑一遍KMP，...

2021-08-18

0 456

学习笔记——z-box算法

简介 z-box算法可用于普通KMP、扩展KMP，国外非常流行但是国内却几乎没有人用，这种算法在解决许多字符串问题时都比KMP要直观许多。算法详解对于一个字符串s,设它的长度为len z[i]所表示的是s[i…len-1]与s[0…len-1]的最长公共前缀如何求出z[i]数组？ ...

2021-08-18

0 409

Codeforces gym 100792B Banana Brain's Bracelet - z-box算法

传送门题意：给一个循环串A，和一个字符串C，求一个最长的A的子串B，使得将B首尾相接成一个循环串后，C是B的子串。 Solution：我们把A翻倍拼接，就可以消掉”A是循环串”z这个限制，发现C可以拆成一个前缀和一个后缀我们可以求出翻转前的z数组z1以及翻转后的z数组z2，分别表示...

2021-08-18

0 484

ARC58 E 和風いろはちゃん / Iroha and Haiku-状压DP

传送门题意：给出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 求合法序列个数...

2021-08-18

0 587

Codeforces 356E Xenia and String Problem-倍增+贡献法

题意：定义一种字符串gray串满足： 1.长度为奇数 2.正中间的字母只出现一次 3.左右两端相同，左右两端也是gray串一个gray串的贡献为这个串长度的平方现给你一个长为n的字符串，你可以修改至多一个字母，使得总贡献值最大 (n<=1e5) Solution: 可以...

2021-08-18

0 389

ARC58F 文字列大好きいろはちゃん / Iroha Loves Strings-暴力+剪枝

传送门题意：给出n个字符串，要求按给出的顺序选择一些字符串，使得这些字符串按顺序拼起来后长度为k且字典序最小 Solution: 正解目前还不会…先写一波学来的暴力算法： can[i][j] c a n [ i ] [ j ] 表示后i个是否可以组成长度为j的字符串先加入初始能...

2021-08-18

0 422

Codeforces 30E Tricky and Clever Password-字符串匹配

传送门题意：密码是一个长度为奇数的回文串，现在我们对这个密码进行加密：把密码分成 3 段，最前面的 X 个字符为一段，最后面的 X 个字符为一段，剩余的字符为一段。这三段依次称之为 prefix, suffix, middle 。middle 的长度为一个大于 0 的奇数， prefix 、...

2021-08-18

0 324

ZOJ3494 BCD Code-AC自动机+数位DP

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 先...

2021-08-18

0 305

Codeforces217E Alien DNA -线段树+逆向思考

传送门题意：给你一个字符串，n个操作 [li,ri] [ l i , r i ] ,每次操作把区间内的字符串复制一遍并打乱接在后面，打乱的规则为： s1s2s3...sn−>s2s4s6...s1s3s5... s 1 s 2 s 3 . . . s n − > s 2 ...

2021-08-18

0 358