acm 竞赛题知识点总结

滚动数组（转）版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明http:/jingtianzi.blogbus.com/logs/43281794.html利用在数组长度N很大的情况下能达到压缩存储的作用。一般还是用在DP 题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的 解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减 少内存开支。用法：#include <iostream>using namespace std;int d3;int main()(d0 = 1;d1 = 1;for( int i = 2; i < 100; i+)di % 3 = d(i - 1) % 3 + d(i - 2 % 3;cout << d99 % 3 << endl; / Fibonacci. return 0;int i,j,d2100;/比 d100100省多了for(i=1;i<100;i+)for(j=0;j<100;j+)di%2j=d(i-1)%2j+di%2j-1;/ DP 滚动数组举个简单的例子: int i,d100;d0=1;d1 = 1;for(i=2;i<100;i+)di=di-1+di-2;printf("%d",d99);上面这个循环di只需要解集中的前2个解di-1和di-2;为了节约空间用滚动数组的方法 int d3;d0=1;d1 = 1;for(i=2;i<100;i+)di%3=d(i-1)%3+d(i-2)%3;printf("%d",d99%3);注意上面的运算，我们只留了最近的3个解，数组好象在“滚动 一样，所 以叫滚动数组对于二维数组也可以用这种方法 例如：int i,j,d100100;for(i=1;i<100;i+)for(j=0;j<100;j+)dij=di-1j+dij-1;上 的 dij忪便赖于 di-1j,dij-1;迥用滚动数组int i,j,d2100;for(i=1;i<100;i+)for(j=0;j<100;j+)di%2j=d(i-1)%2j+di%2j-1;滚动数组实际是一种节约空间的办法，时间上没什么优势，多用于DP中， 举个例子先：一个。?，平常如果需要1000X1000的空间，其实根据DP的特点，能以 2X1000的空间解决问题，并且通过滚动，获得和1000X1000 一样的效 果。背包问题这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问 题定义状态：即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最 大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所 以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问 题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入 容量为v的背包中”，价值为fi-1v；如果放第i件物品，那么问题就转化为 “前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最大价值就是fi-1v-ci再加上通过放入第i件物品获得的价值wi。优化空间复杂度以上方法的时间和空间复杂度均为O（VN），其中时间复杂度应该已经不能再优化 了，但空间复杂度却可以优化到0。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1.N，每次算出来二 维数组fi0.V 的所有值。那么，如果只用一个数组f0.V，能不能保证第i 次循环结束后fv中表示的就是我们定义的状态fiv 呢？ fiv 是由fi- 1v 和fi-1v-ci两个子问题递推而来，能否保证在推fiv时（也即在 第i次主循环中推fv时）能够得到fi-1v和fi-1v-ci的值呢？事实 上，这要求在每次主循环中我们以v=V.0的顺序推fv，这样才能保证推fv 时 fv-ci保存的是状态fi-1v-ci的值。伪代码如下：for i=1.Nfor v=V.0fv=max（fv,fv-ci+wi）;其中的fv=maxfv,fv-ci） 一句恰就相当于我们的转移方程fiv=maxfi-1v,fi-1v-ci，因为现在的 fv-ci就相当于原来 的fi-1v-ci。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成 了 fiv由fiv-ci推知，与本题意不符，但它却是另一个重要的背包问题 P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。AC自动机首先简要介绍一下AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是 著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文 章，让你找出有多少个单词在文章里出现过。要搞懂AC自动机，先得有模式树（字典树）Trie和 KMP模式匹配算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模 式匹配过程。如果你对KMP算法和了解的话，应该知道KMP算法中的next函数（shift函数或者fail函数） 是干什么用的。KMP中我们用两个指针i和j分别表示，Ai-j+ 1.i与B1.j完全相等。也就是 说，i是不断增加的，随着i的增加j相应地变化，且j满足以Ai结尾的长度为j的字符串正好匹 配B串的前j个字符，当Ai+1手Bj+1KMP的策略是调整j的位置（减小j值）使得Ai-j+1.i 与B1.j保持匹配且新的Bj+1恰好与Ai+1匹配，而next函数恰恰记录了这个j应该调整到的位 置。同样AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Tire上进行匹配时， 如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进 行匹配。看下面这个例子：给定5个单词：say she shr he her，然后给定一个字符串yasherhs。问一共有 多少单词在这个字符串中出现过。我们先规定一下AC自动机所需要的一些数据结构，方便接下去 的编程。1 const int kind = 26;2 struct node3 node *fail;失败指针4 node *nextkind; /Tire每个节点的个子节点(最多个字母)5 int count;是否为该单词的最后一个节点6 node()构造函数初始化7 fail = NULL;8 count=0;9 memset(next,NULL,sizeof(next);10 11 *q500001;队列，方便用于bfs构造失败指针12 char keyword51; 输入的单词13 char str1000001;/模式串14 int head,tail; 队列的头尾指针有了这些数据结构之后，就可以开始编程了：首先，将这5个单词构造成一棵Tire，如图-1所示。1 void insert(char *str,node *root)2 node *p=root;3 int i = 0,index;4 while(stri)5 index=stri-'a'6 if(p->nextindex = = NULL) p->nextindex=new node();7 p=p->nextindex;8 i+ + ;10p->count+;在单词的最后一个节点count+1,代表一个单词11 在构造完这棵Tire之后，接下去的工作就是构造下失败指针。构造失败指针的过程概括起来就 一句话：设这个节点上的字母为C,沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也 有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了 root 都没找到，那就把失败指针指向root。具体操作起来只需要：先把root加入队列(root的失败指针 指向自己或者NULL)，这以后我们每处理一个点，就把它的所有儿子加入队列，队列为空。1 void build_ac_automation(node *root)2 int i;3 root->fail = NULL;4 qhead + = root;5 while(head!=tail)6 node *temp=qtail+;7 node *p=NULL;8 for(i = 0;i<26;i+)9 if(temp->nexti! = NULL)10 if(temp= = root) temp->nexti->fail = root;11 else12 p=temp->fail;13 while(p! = NULL)14 if(p->nexti! = NULL)15 temp->nexti->fail = p->nexti;171816 break;p=p->fail;1920if(p= = NULL) temp->nexti->fail = root;2122 qhead +=temp->nexti;23 24 25 26 从代码观察下构造失败指针的流程：对照图-2来看，首先root的fail指针指向NULL,然后 root入队，进入循环。第1次循环的时候，我们需要处理2个节点：root->next'h-'a（节点h） 和root->next's-'a（节点s）。把这2个节点的失败指针指向root，并且先后进入队列，失败 指针的指向对应图-2中的（1），（2）两条虚线；第2次进入循环后，从队列中先弹出h，接下来p 指向h节点的fail指针指向的节点，也就是root；进入第13行的循环后，p=p->fail也就是 p=NULL，这时退出循环，并把节点e的fail指针指向root，对应图-2中的（3），然后节点e进 入队列；第3次循环时，弹出的第一个节点a的操作与上一步操作的节点e相同，把a的fail指 针指向root，对应图-2中的（4），并入队；第4次进入循环时，弹出节点h（图中左边那个），这时 操作略有不同。在程序运行到14行时，由于p->nexti! = NULL（root有h这个儿子节点，图中 右边那个），这样便把左边那个h节点的失败指针指向右边那个root的儿子节点h，对应图-2中 的（5），然后h入队。以此类推：在循环结束后，所有的失败指针就是图-2中的这种形式。最后，我们便可以在AC自动机上查找模式串中出现过哪些单词了。匹配过程分两种情况：(1)当 前字符匹配，表示从当前