题目链接: http://poj.org/problem?id=1200
题目大意: 给出两个数字N和NC,一行字符串
这行字符串最多出现NC个字符
寻找长度为N的不同子串个数
解题思路: 字符串的长度最长为1600万,用strcmp()函数判断次数太多,肯定会TLE
开始用了BKDRHask,和ELFHask都WA,说明有些字串的hash值相等
为了避免这种情况我用链表来处理冲突,但是爆...
阅读全文
题目链接: zoj 2588
题目大意: 在无向连通图中找桥,并且按序号输出
解题思路: Tarjan查找割边
数据中可能会出现重边,需要判断是否是重边
每次加入新的边,则枚举此顶点之前加入的边中是否存在另一点
low[vv]>dnf[u]是桥,low[vv]>=dnf[u]是割点
代码:
//Final Tarjan 找桥(割边)
#include <stdio.h>
#include <string.h>
#include <std...
阅读全文
题目链接:
zoj 1654
题目大意: 给出NxM的地图,地图上有空地,草地和墙
要在空地上放置机器人,机器人可向上下左右四个方向发射激光
且防止的机器人不会被其他机器人的激光射到,机器人可以穿过草地但不能穿墙
问可以放置机器人的最大数目
解题思路: 先把同一行的空地和草地构成块(中间无墙),若中间有墙则可以构成多个块
再把列按同样的方式...
阅读全文
题目链接: poj 1961
题目大意: 给定字符串,找出他所有的前缀的最小循环节的长度
解题思路: 思路与2406一样
Tlen%(Tlen-next[Tlen])==0则Tlen-next[Tlen]是最小循环节
证明过程参考2406的解题报告
这里需要多次查询处理
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000010
int next[MAX],Tlen;
char ch[...
阅读全文
题目链接: hdu
1269
题目大意: 给定n个字符串,找出最长的公共子串,不存在输出 no significant commonalities
解题思路: 选出长度最短的字符串,枚举它的子串
把它的子串分别与其余的n-1个字符串匹配
字符串长度越短它的子串就越少,枚举量越少
枚举子串的顺序从大到小,能够匹配就退出输出答案
如果从小到大枚举则需要枚举所有符合情况的子...
阅读全文
题目链接: poj 3041
题目大意: 给出NxN的矩阵,有M个点是障碍
每次只能删除一行或者一列,最少删除多少次才能清除障碍
解题思路: 行作为X集合,列作为Y集合,障碍就是两集合间的连线
问题转化为如何使得选取最少的点,覆盖掉所有的直线
由König定理可得
最小点集覆盖==最大匹配数,匈牙利求最大匹配
代码:
#include <stdio.h>
#include <string.h>...
阅读全文
题目链接: poj 1274
题目大意: 给出N头奶牛,和M个牛棚
每头奶牛只在自己喜欢的牛棚产奶,问最大的产牛量
解题思路: 把N头奶牛作为X集合,M个牛棚作为Y集合
奶牛和牛棚的关系就是集合X和集合Y的关系
问题转化为 X集合和Y集合的最大匹配数
匈牙利DFS增广路求解
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string...
阅读全文
题目链接: poj 1273
题目大意: 有N个点和M条边,每条边最大的流量为c,初始流量为0
1为源点,n为汇点求最大流
解题思路: 最短增广路算法比一般增广路算法每次增广大范围小,因为每次增广都在残留网络进行
但是最短增广路每次还是要回到源点继续增广,而连续最短增广路算法则利用深搜的思想
一次遍历就能把残留网络增广完毕
PS:用邻接表时要注...
阅读全文
题目链接: poj 1689
题目大意: 有个人想拍n部电影,每部电影限定每周哪几天可以拍
并且必须在第ki周之前把这部电影拍完,问能否拍完n部电影
解题思路: 把每部电影当作一个顶点,源点指向这些顶点,容量为该电影需要拍多少天
然后把每一天都当作顶点,某个工作可以在这天完成就连容量为1大边
每天的顶点指向汇点,容量也为1
最后求出最大流,满...
阅读全文
题目链接: poj 2195
题目大意: 给出NxM的地图,'.'表示可以走的,'H'表示家,'m'表示人,H和m的数目相同
求把所有人移动到H的最小步数
解题思路: 建立超级源点,分别连接每个m,容量为1,费用0
建立超级汇点,分别把每个H连接到汇点,容量为1,费用为0
再把每个m分别指向H,容量为1,费用为该m到H的横纵左边之差的绝对值的和,|X1-X2|+|Y1-Y2|
...
阅读全文