ac自动机学习笔记

hdu 2203 题目链接 题意：给定字符串A（一个环），和字符串B，问B是否在A中出现过。

。。。重新编译一次就可以了。。。orz

终于忍不了因为没办法科学上网而不能做什么事的感觉了。。。 买了班瓦工 20刀/年。。。搭了ss。。然后全平台（ios/androd/fedora/win）的上网问题就全解决了。。。

树，一种十分优美的数据结构，因为它本身就具有的递归性，所以它和子树见能相互传递很多信息，还因为它作为被限制的图在上面可进行的操作更多，所以各种用于不同地方的树都出现了，二叉树、三叉树、静态搜索树、AVL树，线段树、SPLAY树，后缀树等等.. 枚举那么多种数据结构只是想说树方面的内容相当多，本专辑只针对在树上的动态规划，即树形DP.做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作，从子节点或子树中返回信息层层往上更新至根节点。这里面的关键就是返回的信息部分，这个也没一般性的东西可讲，因为每道题目要求做的事都不尽相同。

1#include <iostream> 2#include <vector> 3#include <cstring> 4#include <set> 5#include <algorithm> 6#include <cstdio> 7 8using namespace std; 9const int N=1E4+7; 10int n,k,Q; 11int siz; 12int pos[N]; 13int sum[N]; 14int dis[N]; 15bool vis[N]; 16vector < pair<int,int> > edge[N]; 17 18struct node 19{ 20 int l,r; 21 int id; 22 23 bool operator < (node b)const 24 { 25 if (pos[l]==pos[b.l]) return r<b.r; 26 return pos[l]<pos[b.l]; 27 } 28 29 30}q[N]; 31 32 33void dfs( int u,int val) 34{ 35 vis[u] = true; 36 dis[u+1] = val; 37 38 int Siz = edge[u].size(); 39 for ( int i = 0 ; i < Siz ; i ++) 40 { 41 int v = edge[u][i].first; 42 43 if (!vis[v]) 44 { 45 dfs(v,val+edge[u][i].second); 46 } 47 } 48} 49int main() 50{ 51 52 freopen("in.txt","r",stdin); 53 siz = 100; 54 for ( int i = 0 ; i < 10000 ; i++) pos[i] = i/siz; 55 while (scanf("%d %d %d",&n,&k,&Q)!=EOF) 56 { 57 memset(vis,false,sizeof(vis)); 58 memset(dis,0,sizeof(dis)); 59 memset(sum,0,sizeof(sum)); 60 for ( int i = 1 ;i < n ; i++) 61 { 62 int u = i; 63 int v = i/k; 64 edge[u].push_back(make_pair(v,i)); 65 edge[v].push_back(make_pair(u,i)); 66 } 67 68 for ( int i = 1 ;i <= Q ; i++) 69 { 70 scanf("%d %d",&q[i].l,&q[i].r); 71 q[i].id = i; 72 } 73 74 sort(q+1,q+Q+1); 75 76 dfs(0,0); 77 for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1]+dis[i]; 78 } 79}