您所在位置：网站首页 > 学术论文 > 其它学术论文acm 竞赛题知识点总结

acm 竞赛题知识点总结

12页

卖家[上传人]：s9****2

文档编号：458974572

上传时间：2023-11-07

文档格式：DOCX

文档大小：84.31KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 金贝

/ 12 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、滚动数组（转）版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明http:/ 题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减少内存开支。用法：#include 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;i100;i+)for(j=0;j100;j+)di%2j=d(i-1)%2j+di%2j-1;/ DP 滚动数组举个简单的例子: int i,d100;d0=1;d1 = 1;for(i=2;i100;i+)di=di-1+di-2;printf(%d,d99);上面这个循环di只需要解集中的前2个解di-1和di-2;为了节约空间用滚动数组的方法 i

2、nt d3;d0=1;d1 = 1;for(i=2;i100;i+)di%3=d(i-1)%3+d(i-2)%3;printf(%d,d99%3);注意上面的运算，我们只留了最近的3个解，数组好象在“滚动一样，所以叫滚动数组对于二维数组也可以用这种方法例如：int i,j,d100100;for(i=1;i100;i+)for(j=0;j100;j+)dij=di-1j+dij-1;上的 dij忪便赖于 di-1j,dij-1;迥用滚动数组int i,j,d2100;for(i=1;i100;i+)for(j=0;jnextindex = = NULL) p-nextindex=new node();7 p=p-nextindex;8 i+ + ;10p-count+;在单词的最后一个节点count+1,代表一个单词11 在构造完这棵Tire之后，接下去的工作就是构造下失败指针。构造失败指针的过程概括起来就一句话：设这个节点上的字母为C,沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了

3、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;inexti! = 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 从代码观察下

4、构造失败指针的流程：对照图-2来看，首先root的fail指针指向NULL,然后 root入队，进入循环。第1次循环的时候，我们需要处理2个节点：root-nexth-a（节点h）和root-nexts-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)当前字符匹配，表示从当前

《acm 竞赛题知识点总结》由会员s9****2分享，可在线阅读，更多相关《acm 竞赛题知识点总结》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源