后缀自动机

后缀自动机(SAM)是一个神奇的算法,它可以在O(n)的时间内搞出长度为n的字符串的所有子串。

花了一个晚上时间和杨主力一起讨论出来了。。。

窝们先看了CLJ的讲稿,然后发现完全搞不懂QAQ(一定是窝们的理解能力太差)

然后翻了下百度文库,发现《后缀自动机学习》写的很好,窝很能理解

于是就愉快地看懂啦!

然后再回头看CLJ的讲稿发现恍然大悟Orrrrrz

但是目前本蒟蒻只会SAM的板子。。。只能拿O(n)求子串来搞暴力


最后贴个板子上来吧。。。具体步骤看百度文库里的《后缀自动机学习》。

下一篇是SAM的应用0.0


#include <iostream>...

BZOJ 2257 【JSOI2009】 瓶子和燃料

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2257

【题意】

从n个瓶子中选出k个,让它们通过3种不同的操作后得到最多的燃料。


【题解】

稍微想一下就会发现3种操作只能倒出给定k个瓶子的容量的最大公约数的燃料

所以问题就变成了从n个数中选k个,使它们的最大公约数最大。

暴力搞出所有数的所有约数,然后找出最大的出现次数≥k次的约数。


【代码】

#include <iostream>

#include <cstdio>

#include <cmath>...

BZOJ 1054 【HAOI2008】 移动玩具

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1054

【题意】

给定一个4*4的01矩阵和4*4的01目标矩阵,求原矩阵中的1经历多少次上下左右移动达到目标状态。


【题解】

傻*题,BFS+哈希判重就行了。


【代码】

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;


int dir[4][2]={1,0,0,1,-1,0,0,-1};...

BZOJ 1082 【SCOI2005】 栅栏

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1082

【题意】

见题面


【题解】

把已有木棒和目标木板都排成递增序,再二分答案,DFS判定。

两个剪枝:

1.如果当前剩下的可用木板已不可能锯出尚没处理的目标木板,则直接判断为不行

2.如果下一块目标木板和当前目标木板等长,则从当前的已有木板开始搜索


【代码】

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace...

BZOJ 1055 【HAOI2008】 玩具取名

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1055

【题意】

四个字母'W' 'I' 'N' 'G',每个都可以转换成另两个字母(都是由'W' 'I' 'N' 'G'构成)。

现给定一个由'W' 'I' 'N' 'G'构成的字符串,问最开始可能由哪些字母变形得到。按'W' 'I' 'N' 'G'的优先级输出。


【题解】

区间DP,我居然看了半天不会做。。。找了篇题解才搞懂 (果然还是太弱了QAQ...

BZOJ 1072 【SCOI2007】 排列perm

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1072

【题意】

给定字符串s,问s有多少种不同的排练能被d整除。


【题解】

状压DP

dp[i][j]表示选了s中哪几个位置上的数,除以d余数为j的方案数。

然后就不用讲了。。。


【代码】

#include <string>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;...

BZOJ 1067 【SCOI2007】 降雨量

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1067

【题意】

给定一些年份和当年的降雨量,判定“X年是自Y年以来降水量最大的一年”这句话是真的,假的还是可能的。


【题解】

RMQ之后分类讨论。

WA得连北是哪边都不认识了


【代码】

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

#include <algorithm...

BZOJ 1057 【ZJOI2007】 棋盘制作

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1057

【题意】

给定一个n*m的棋盘,求最大的01相间的矩形和正方形面积。


【题解】

在一个01相间的棋盘里,黑色格点的行列坐标奇偶性相同。

我们把行列坐标奇偶性相同的点颜色取反,然后计算新的棋盘上面积最大的相同颜色的矩形和正方形。

因为我写的是计算给定棋盘上面积最大的颜色为1的矩形和正方形,所以计算一次后还要把整个棋盘颜色反转再计算一遍。

计算最大面积,可以用dp和单调队列搞一搞。


【代码】

#include <iostream>

#include...

BZOJ 1076【SCOI2008】 奖励关

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1076

【题意】

见题面。。。orz


【题解】

状压DP,从后往前推就行了


【代码】

#include <cstdio>

#include <iostream>

using namespace std;

double dp[110][100000];

int n,m,t;

int v[50],cnt[50];

int main()

{

    int i,j,k;...


BZOJ 1143 【CTSC2008】 祭祀river

链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1143

【题意】

给一个n个点的有向无环图,要取最多的祭祀点,要求从一个祭祀点不能走到另外的祭祀点。


【题解】

最大独立集问题。如果在图中u能走到v,就在二分图的左边u点连一条边到右边v点

答案就是点数-二分图的最大匹配。


【代码】

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;


int...

1 / 2

© CodeDevil | Powered by LOFTER