题意是建一个二叉树，按值最小的次序遍历，每当遍历到的节点编号为奇数的得到一个字符1，否则得0。然后在比较给出的字符串在得到的字符串中出现的次数。但是由于这里的数据达到60W，所以不能直接模拟建树，会栈溢出。只能自己模拟栈。
#include<cstdlib> #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<queue> #include<stack> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define pb push_back #define mp make_pair #define ULL unsigned long long #define LL long long #define inf 0x7fffffff #define eps 1e-7 #define N 600009 using namespace std; int m,n,T,t,len; int s[N],next[7009]; bool vis[N]; char str[N*2]; char p[7009]; int v[N*2],last[N*2],head[N],top; void init() { memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); top=0; } void add(int x,int y)//用vector超内存！！ {//保证先大后小 v[top]=y; last[top]=head[x]; if(head[x]!=-1) { int sub=head[x]; if(y<v[sub]) { last[top]=-1; last[sub]=top; } else head[x]=top; } else head[x]=top; top++; } void getnext(char str[],int n) { int j=-1,i=0; next[0]=-1; while(i<n) { if(j==-1||str[i]==str[j]) { i++,j++; next[i]=j; } else j=next[j]; } } int KMP(char str[],int n,char s[],int ns) { int ans=0; int i=0,j=0; while(i<n) { if(j==-1||str[i]==s[j]) { i++,j++; if(j==ns) { ans++; j=next[j]; } } else j=next[j]; } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif int ncase=0; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); map<int,int>mp; map<int,int>::iterator it; map<int,int>::iterator jt; for(int i=1; i<=n; i++) { scanf("%d",&s[i]); it=mp.lower_bound(s[i]); if(it==mp.end()) { if(it!=mp.begin()) { it--; add(it->first,s[i]); } } else { if(it==mp.begin()) { add(it->first,s[i]); } else { jt=--it; it++; if((it->second)>(jt->second)) add(it->first,s[i]); else add(jt->first,s[i]); } } mp[s[i]]=i; } mp.clear();//c++不加的话超内存 stack<int>sk; sk.push(s[1]); int len=0; while(!sk.empty())//栈模拟！！！！！ { int cur=sk.top(); sk.pop(); if(vis[cur])/////////////////////// str[len++]=(cur&1)?'1':'0'; if(!vis[cur]) { sk.push(cur); for(int i=head[cur]; i!=-1; i=last[i]) { sk.push(v[i]); sk.push(cur); } vis[cur]=1; } } str[len]=' '; scanf("%s",p); int np=strlen(p); getnext(p,np); printf("Case #%d: %d ",++ncase,KMP(str,n*2-1,p,np)); } return 0; }