题目链接 题意 给n个区间的集合S，求一个区间集合A属于S，且集合A的每个区间的长度和最大，每个点最多可以选k次。 思路 首先每个点可以重复k次，可以用流量来限制，用最大费用最大流来做。 将所有区间离散化，源点在最左边，汇点在最右边，每一个点都向右边相邻的点连一条容量为INF，费用为0的边，对于每个区间，左端点到右端点连一条容量为1费用为r-l的边，容量为1是因为一个区间只能取一次。然后跑最大费用最大流。 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int N = 5e3 + ...

题目链接 题意 一个有n*m个方格的迷宫，相邻的方格之间可能是墙，也可能是连通的，也可能是门，门有多种类型，需要对应类型的钥匙才可以通过，某些方格里存放着钥匙，问从左上角（1,1）到（n,m）最短的时间。 思路 分层图，以携带的钥匙为层数，用二进制法存，按题意建图后跑spfa。 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int maxn = 2e2 + 7; const int maxm = 5e3 + 7; typedef long long ll; int key[max...

题目链接 题意 一张航空图，从西向东，1-n个城市，城市之间有若干条航线，航线可以往返，求从1到n再从n到1最多经过多少个不同的城市，1和n可以经过两次，其他城市都只能经过一次。 思路 经过次数，显然要想到拆点和流量控制，将每个城市点拆成入点和出点i和i+n，1与1+n之间的容量是2，费用是0，n与n+n之间的容量是2，费用是0，其他的入点与出点之间的容量是1，费用是0，这样就限制了1和n可以经过两次，其它点只能经过一次；因为求的是经过的最多城市，用最大费用最大流，建立源点S，汇点T，S连1容量为2,费用为0，n+n连T容量为2费用为0，航线连通的两个城市i,j，加边i+n与j容量为1，费用为...

题目链接 题意 P*Q的网格中，给出每条边的收益，若干个机器人的起始位置和目的地。机器人只能往东或北走，每条边可以走多次，但只能算一次收益，求最优机器人移动方案下的最大收益。 思路 有机器人数量，边的收益，这种问题显然优先考虑最大费用最大流。一条边的收益只能记一次，连一条容量为1费用为权值的边；然后每条边收益只记一次，但多个机器人可以走同一条路，所以对于每条边，加一条容量为INF，费用为0的边。建立超级源点S和超级汇点T，S连所有点起始位置点，容量为机器人数量，费用为0，所有目的地点连T，容量为机器人数量费用为0。然后跑最大费用最大流，这里的模板是最小费用最大流，但把所有边的费用改为负值就可以...

题目链接 题意 x0y平面上n条开线段，求一个线段子集，使得它的线段长度和最长，且对于每条垂直于x轴的线段都不超过k条线段与之相交。 思路 类似最长k可重区间集问题，因为只对x轴上的点有限制，一样的，离散化后建边，跑最大费用最大流，需要注意的是这里是开线段，有个神奇的处理就是把l改为l * 2+1，r改为r * 2。先对x离散化，处理出费用，也就是线段的长度，对于每个相邻的点连上容量为INF，费用为0的边，对于每一条线段，左端点与右端点连上容量为1,，费用为线段长度的边，源点连第一个节点，最后一个节点连汇点。然后跑最大费用最大流。 #include <bits/stdc++.h> ...

poj1625 题意 给一个含n个字符的字符集，p个字符串，问长度为m的字符串有多少种不包含任意一个字符串pi。 题解 首先这题应该想到dp，dp[i][j]表示长度为i的字符串以节点j（节点j表示一个AC自动机上的一个状态节点）结尾的满足条件的字符串种类。以p个字符串建立AC自动机，标记危险节点。想像一个这样的问题：假设当前在u节点，u节点就表示当前长度为x的字符串，从u经过状态转移到其他节点，那么字符串的长度就变为x+1，遍历每个节点，如果该节点不是危险节点，则dp[i][j] = dp[i][j] + dp[i - 1][u]，(j是u的一个子节点)，这样从根结点（空串）转移m次到达的合...

hdu3341 题意 给m个模式串和一个母串（字符串都是由ATCG组成），求这个母串重组后最多包含多少个模式串，可以重叠。 思路 看题目数据范围很小，首先暴力的思想，把母串的所有可能的排列方式都求一遍，取最大值。建立模式串的AC自动机，dp[i][x1][x2][x3][x4]表示i状态下有x1个A，x2个T，x3个C，x4个G。状态转移：dp[j][相应字母加一]=max(dp[j][相应字母加一],dp[i][x1][x2][x3][x4]+tag[trie[i][j]])，然后对于每个状态取字符个数和为n的最大值就可以了；但是！40404040500超内存，所以不行，考虑状态压缩：字符串...

题目链接 题意 直角坐标系中n个点，限制一些走过的路径的顶点顺序，要求从1到n最短的距离。如：不能经过1 -> 2 -> 3，那么就要求走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。 思路 求1到n的最短路问题，把所有限制的路建立AC自动机，这里用dp解最短路问题，dp[i][j]表示从1到i的j状态的最短距离。如果tag[trie[j][k]] 为0，则表示不是危险节点，用dp[k][trie[j][k]] = min(dp[k][trie[j][k]], dp[i][j] + m...

题意 给A,B两个串，求有多少个A的不同的子串t，t中没有B这个子串。 思路 定义一个数组num，num[i]表示A字符串从i开始的A的子串能延伸到最右边的不包含B串的长度，其实就是从i开始向右的字符串不包含B的有多少个。 所以sigma(num[i])就是答案的一部分了，又因为这样算出来的可能会有重复，要用后缀数组height数组去重，所以答案就是sigma（num[sa[i]] - min(height[i], num[sa[i]])）。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 1...

Genes in DNA 题意 给一个文本串和一个模式串，求模式串的所有前缀与后缀的组合在文本串里出现次数和。 当我觉得我懂KMP的时候，KMP给了我一巴掌：不，你不懂！ 思路 这题朴素的算法就是把模式串的前缀和后缀组合列出来，跑KMP求出现次数和。显然数据范围不允许，那考虑求贡献的方法，对于文本串中第i个字符，把所有模式串中以这个字符为结尾的前缀 的个数求出来，记为ans1[i]，注意，这里的以第i个字符结尾的前缀不是真的 以字符t[i]结尾的前缀，而是类似文本串与模式串kmp匹配时与t[i]匹配，假设某个前缀的长度为len，也就是s[0]…s[len-1]与t[i - len + 1]…t...

传送门 题意 给一个字符串，求它有多少个不同的子串。 思路 后缀数组当然是能做的，每个sa[i] - height[i]的和就是答案了。 后缀自动机也可以做，后缀自动机上从起点到任意状态就是一个子串，每条路径表示的子串都不同，所以只要求出后缀自动机上从起点到其它点的路径条数就是不同子串的个数。 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 7, M = 26; typedef long long ll; char s[maxn]; int head[maxn], to[maxn], nex[...

题目链接 题意 n个元素的数组A，从A数组中所有长度大于等于k的区间中取出第k大放入B数组中，求B数组的第m大。 思路 这题正常想很难搞，看了题解才懂。mark一下。 考虑二分的做法，问题是求B数组第m大的是谁，假设为ans，考虑一个值x，求B数组里大于等于x的值是否大于m个，这个问题具有单调性，即求A数组里区间第k大的数大于等于x的区间是否多于m个。然而这个问题也不好解，神犇的做法来了，将数组A里大于等于x的值赋为1，否则为0，只要一个区间的和大于等于k，那么这个区间第k大的数就大于等于x，然后就是求有多少个区间和大于等于k了，考虑固定了区间右端点j，当左端点为i，[i,j]的和大于等于k时...

涉及：大量数据的第k小，几何斜率，圆形尺取，离散化，差分约束，前缀和，模拟。 A 第K小数 题意 给n个数，求第k小的元素。（n<=5e6） 思路 直接sort超时。 可以利用快排的思想，每次选一个基准元素，把小的元素放左边，大的元素放右边，如果左边的元素个数>=k，那么只需要从左边找第k小，右边就可以不管了；如果这个基准正好是第k小的位置，那就直接输出这个数；否则第k小就在右边，从右边找第（k-左边元素个数）小就可以了，左边的可以直接放弃，不需要进行排序。时间复杂度O(logn)。 #include <bits/stdc++.h> using namespace st...

题目链接 题意 n点m条边的无向图，每个点的点权是ai，没经过一次点，点权增加bi，即第k次经过i点权值为ai + (k - 1) * bi，现给出q个xi和q个yi，每次从中选出一组xi,yi，统计从xi到yi的代价和（代价为从xi到yi经过的所有点的点权和），每个点只能选一次，q次后（也就是全选完），求最小代价。 思路 考虑最小费用最大流。 重点解决几个问题： ①点权改边权。拆点，一个点拆成一个入点和一个出点，点权就改为了从入点到出点的边权。 ②每经过一次点，权值增加。在网络流里，可以用拆点，入点和出点间的容量为1来限制该点只能走一次，那么如果要限制走q次，可以从入点到出点连q条边，容量为...