题目简介：
给一个长度为N(N<600,000)的序列，让你按顺序插入静态二叉树。然后DFS出一个序列，问某个模式串在这个序列中出现了几次？
吐槽：
被KMP卡了一个晚上是什么水平？ 数组开小了WA了一下午是什么水平？
算法分析：
比较难想的是如何实现这个静态二叉树，因为要一个DFS序列，所以组织静态二叉树是不可逃避的了。
这里用到一个结论，就是新插入的数的父亲，要么是比它大的最小的那个元素，要么是比它小的最大的那个元素。
然后套一个KMP就水过了。。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cassert>
5 using namespace std;
6 const int N = 600005;
7 template <typename T> inline void chkmin(T &a,T b){if(a>b) a=b;}
8 template <typename T> inline void chkmax(T &a,T b){if(a<b) a=b;}
9 bool ch[N<<2];
10 char parten[10000];
11 int nxt[N],seg[N<<2][2], stk[N], vis[N], hash[N];
12 const int inf = ~0u>>2;
13 struct tree{
14 int l,r,v;
15 tree(){}
16 tree(int _l,int _r,int _v) : l(_l), r(_r), v(_v) {}
17 } num[N];
18 int n,len;
19 int main(){
20 int test,M;
21 cin >> test;
22 for(int _=1;_<=test;_++){
23 cin >> n;
24 int v,val;
25 for(int i=30;i>=0;i--) if((1<<i)>=n) M = 1<<i;
26 for(int i=0;i<2*M;i++) seg[i][1] = -1, seg[i][0] = inf;
27 for(int i=0;i<n;i++){
28 scanf("%d",&v);
29 val = v;
30 hash[val] = i;
31 if(i==0) {
32 num[0] = tree(-1,-1,v);
33 v += M-1;
34 while(v){seg[v][0] = seg[v][1] = val;v>>=1;}
35 continue;
36 }
37 num[i] = tree(-1,-1,v);
38 int mn = -1, mx = inf;
39 for(v += M-1; v; v>>=1){
40 chkmin(seg[v][0],val);
41 chkmax(seg[v][1],val);
42 if(v&1) chkmax(mn,seg[v^1][1]);
43 else chkmin(mx, seg[v^1][0]);
44 }
45 //cout<<val<<" "<<mn<<" "<<mx<<endl;
46 if(mn == -1 || num[hash[mn]].r !=-1){
47 num[hash[mx]].l = i;
48 } else num[hash[mn]].r = i;
49 }
50 len = 0;
51
52 for(int i=0;i<n;i++) vis[i] = 0;
53 int tp = 0,u;stk[0] =0;
54 while(!vis[0]) {
55 u = stk[tp];
56 ch[len++] = num[u].v & 1;
57 v = num[u].l;
58 if(v!=-1 && !vis[v]) {stk[++tp] = v; continue;}
59 v = num[u].r;
60 if(v!=-1 && !vis[v]) {stk[++tp] = v; continue;}
61 tp--;
62 vis[u] = 1;
63 }
64 // for(int i=0;i<len;i++) cout<<ch[i]<<" ";cout<<endl;
65
66 scanf("%s",parten);
67 nxt[0] = -1; int m = strlen(parten);
68 int j = -1;
69 for(int i=0;i<m;i++) parten[i] -='0';
70 for(int i=1;i<m;i++){
71 while(j>=0 && parten[i]!=parten[j+1])
72 j=nxt[j];
73 if(parten[i]==parten[j+1]) j++;
74 nxt[i] = j;
75 }
76 // for(int i=0;i<m;i++) cout<<nxt[i]<<" "; cout<<endl;
77 int ans = 0; j = -1;
78 for(int i=0;i<len;i++){
79 // cout<<j<<" ";
80 while(j>=0 && parten[j+1]!=ch[i]) j = nxt[j];
81 if(parten[j+1]==ch[i])
82 j++;
83 if(j == m-1) {
84 ans++;
85 j = nxt[j];
86 }
87 }
88 printf("Case #%d: %d\n",_,ans);
89 }
90 }
91
posted on 2012-07-02 15:14
西月弦 阅读(605)
评论(0) 编辑 收藏 引用