月份:2017年7月

<余姚集训> —— AC自动机

<余姚集训> —— AC自动机

这篇文章建立在这样一个问题上:
我们有一个字符串,我们要在其上查找分别出现过多少次已知词汇。
(设n为长度,m为个数)
&nbsp;

方法一:
O(n^2*nm)

方法二:
O(n^2*2n)
将O(m)比较改为trie树O(n)的优化查找

方法三:
我们将注意到方法一、二中有很多查找是部分重复的无用查找,所及我们要对j循环进行一定优化:
O(n^2)

方法四:
可以看出前面的方法是枚举前缀,那么我们就会想尝试一下“那枚举后缀”呢?

结果我们发现时间复杂度缩水回了O(n^3),所以我们就想对Trie树进行优化使得我可以在节点上找到他的后缀节点!
这样一来我们就实现了后缀的O(n^2),且如果某串的后缀是危险的,那么该串是危险的。所以对于判断一个串是否危险来说,只要看它的最长后缀是不是危险即可。
所以在实现中我们会面临补图这一问题,在记录每个节点的后缀节点时,还要将每个节点都补为字符集条边以便于后缀的查找,那么不存在的边怎么办?
该节点的某边等于其父亲节点的后缀节点的该边

最终无限优化后得到的就是神奇的AC自动机b了:
(hdu 2222 Key Search 模板题)

0
NOIP2008 传纸条

NOIP2008 传纸条

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用0表示),可以用一个0-100的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

题解:如果将题目简化为一个纸条从1,1到n,m,则dp[i][j]即可简单做出,所以类比可以想到四维的dp[i][j][k][h]表示i,j和k,h的纸条(因为从n,m到1,1等于从1,1到n,m,所以两个纸条可以都从1,1出发),那么我们就可以用O(n^4)的复杂度做出。我们还可以根据i+j=k+h将数组和时间复杂度简化到O(n^3)。
另外,我们都会注意到两个纸条是不能重合的,所以我们来看这样一个神奇的事情:

对于这个有相交的两条路径来说,他一定不是最优解,因为如下这样的路径保证优于相交,那么对于dp[i][j][i][j]来说,我们就不用管它了,只要保证他不会将该点好心值加了两遍或者遇到他取完max直接跳过都可以哦

所以在转移方程为:
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j][k-1],dp[i][j-1][k],dp[i][j-1][k-1])+w[i][j]+w[k][h];
并且if (i==k && j==h) dp[i][j][k]-=w[i][j]即可

AC代码:

0
<余姚集训> 网络流 Ⅰ草地排水

<余姚集训> 网络流 Ⅰ草地排水

Dinic棵版题

AC代码:

0
<余姚集训> 模拟

<余姚集训> 模拟

今天上午讲了网络流,神奇的口音与dfs bfs NOi相结合,摸摸唧唧的讲了最大流最小割定理(实际上记住结论就好了)

下午模拟,被一群初中大佬围攻,50分贼菜……小迪130,同样被各种巨佬压制,更有甚者,两个AK

T1 改造二叉树

小Y在学树论时看到了有关二叉树的介绍:在计算机科学中,二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。
什么是二叉搜索树呢?二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p,若其存在左孩子lch,则key[p]>key[lch];若其存在右孩子rch,则key[p]<key[rch];注意,本题中的二叉搜索树应满足对于所有结点,其左子树中的key小于当前结点的key,其右子树中的key大于当前结点的key。
小Y与他人讨论的内容则是,现在给定一棵二叉树,可以任意修改结点的数值。修改一个结点的数值算作一次修改,且这个结点不能再被修改。若要将其变成一棵二叉搜索树,且任意时刻结点的数值必须是整数(可以是负整数或0),所要的最少修改次数。
相信这一定难不倒你!请帮助小Y解决这个问题吧。

题解:
因为二叉搜索树的性质,所以可以简单想到中序遍历后,求最长上升子序列,然后因为节点的数值必须是整数,所以用一个神奇的处理来解决这个问题:

是不是炒鸡喵啊~,这样避免了两数中间不存在整数的情况下,求最长不下降子序列就好啦!

那么问题来了……,n^2复杂度不能AC啊,所以我们还要学习nlogn的最长不下降子序列
我们将可以构成最长&*&……的直接加到队伍末尾,然后对于剩下的数二分找到当前子序列中第一个比他大的数(因为替换掉队伍中间的数不会影响长度,而如果用一个较小的数代替最后一个数,显然是更好的选择)所以nlogn即可完成dp

AC代码:

T2 数字对

小H是个善于思考的学生,现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为n的序列{ai},她想找出一段区间[L, R](1 <= L <= R <= n)。
这个特殊区间满足,存在一个k(L <= k <= R),并且对于任意的i(L <= i <= R),ai都能被ak整除。这样的一个特殊区间 [L, R]价值为R – L。
小H想知道序列中所有特殊区间的最大价值是多少,而有多少个这样的区间呢?这些区间又分别是哪些呢?你能帮助她吧。

题解:
方法一:在预处理下进行大暴力,只要记得去重就好了
方法二:RMQ问题的解法,双st表解min,gcd,若某段min=gcd,则该区间为可以

AC代码:

0