青竹qingzhu

分类

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

TA的专栏 2篇文章 0人订阅

2篇文章 648人学习

全部文章（共51篇）

#6014. 「网络流 24 题」最长 k 可重区间集

题目链接题意给n个区间的集合S，求一个区间集合A属于S，且集合A的每个区间的长度和最大，每个点最多可以选k次。思路首先每个点可以重复k次，可以用流量来限制，用最大费用最大流来做。将所有区间离散化，源点在最左边，汇点在最右边，每一个点都向右边相邻的点连一条容量为INF，费用为0的边，对于每个...

2020-07-13

0 622

#6121. 「网络流 24 题」孤岛营救问题迷宫分层图

题目链接题意一个有n*m个方格的迷宫，相邻的方格之间可能是墙，也可能是连通的，也可能是门，门有多种类型，需要对应类型的钥匙才可以通过，某些方格里存放着钥匙，问从左上角（1,1）到（n,m）最短的时间。思路分层图，以携带的钥匙为层数，用二进制法存，按题意建图后跑spfa。 #include ...

2020-07-13

0 485

#6122. 「网络流 24 题」航空路线问题输出路径

题目链接题意一张航空图，从西向东，1-n个城市，城市之间有若干条航线，航线可以往返，求从1到n再从n到1最多经过多少个不同的城市，1和n可以经过两次，其他城市都只能经过一次。思路经过次数，显然要想到拆点和流量控制，将每个城市点拆成入点和出点i和i+n，1与1+n之间的容量是2，费用是0，n与...

2020-07-13

0 509

#6224. 「网络流 24 题」深海机器人问题收益记一次可走多次

题目链接题意 P*Q的网格中，给出每条边的收益，若干个机器人的起始位置和目的地。机器人只能往东或北走，每条边可以走多次，但只能算一次收益，求最优机器人移动方案下的最大收益。思路有机器人数量，边的收益，这种问题显然优先考虑最大费用最大流。一条边的收益只能记一次，连一条容量为1费用为权值的边；然后...

2020-07-13

0 510

#6227. 「网络流 24 题」最长 k 可重线段集问题

题目链接题意 x0y平面上n条开线段，求一个线段子集，使得它的线段长度和最长，且对于每条垂直于x轴的线段都不超过k条线段与之相交。思路类似最长k可重区间集问题，因为只对x轴上的点有限制，一样的，离散化后建边，跑最大费用最大流，需要注意的是这里是开线段，有个神奇的处理就是把l改为l * 2+1，...

2020-07-13

0 496

Poj1625 AC自动机+大数+DP

poj1625 题意给一个含n个字符的字符集，p个字符串，问长度为m的字符串有多少种不包含任意一个字符串pi。题解首先这题应该想到dp，dp[i][j]表示长度为i的字符串以节点j（节点j表示一个AC自动机上的一个状态节点）结尾的满足条件的字符串种类。以p个字符串建立AC自动机，标记危险节点。...

2020-07-13

0 612

hdu3341AC自动机+变进制状压dp

hdu3341 题意给m个模式串和一个母串（字符串都是由ATCG组成），求这个母串重组后最多包含多少个模式串，可以重叠。思路看题目数据范围很小，首先暴力的思想，把母串的所有可能的排列方式都求一遍，取最大值。建立模式串的AC自动机，dp[i][x1][x2][x3][x4]表示i状态下有x1个A...

2020-07-13

0 437

hdu4511 AC自动机+最短路dp

题目链接题意直角坐标系中n个点，限制一些走过的路径的顶点顺序，要求从1到n最短的距离。如：不能经过1 -> 2 -> 3，那么就要求走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。思路...

2020-07-13

0 451

LightOJ - 1428Melody Comparison KMP+后缀数组

题意给A,B两个串，求有多少个A的不同的子串t，t中没有B这个子串。思路定义一个数组num，num[i]表示A字符串从i开始的A的子串能延伸到最右边的不包含B串的长度，其实就是从i开始向右的字符串不包含B的有多少个。所以sigma(num[i])就是答案的一部分了，又因为这样算出来的可能会有...

2020-07-13

0 457

LightOJ - 1334 Genes in DNA KMP 求贡献思想

Genes in DNA 题意给一个文本串和一个模式串，求模式串的所有前缀与后缀的组合在文本串里出现次数和。当我觉得我懂KMP的时候，KMP给了我一巴掌：不，你不懂！思路这题朴素的算法就是把模式串的前缀和后缀组合列出来，跑KMP求出现次数和。显然数据范围不允许，那考虑求贡献的方法，对于文本...

2020-07-13

0 403