HDU 4125 2011福州现场赛E题 KMP+笛卡尔树
题意就不描述了。 主要说一下我的构造第一个串的过程
对给出的序列，比如5 1 3 2 7 8 4 6
给每个数按输入的顺序对应一个编号
5 1 3 2 7 8 4 6
1 2 3 4 5 6 7 8
然后我们手动建这颗二叉搜索树。观察它，可以发现，每个结点的编号是满足堆的性质。
也就是如果把这个编号当做每个结点的第二个关键字，这就是一个笛卡尔树了
而建立笛卡尔树的方法，如果以前做过POJ 2201的话，应该明白
首先按照第一个关键字排序
变为
第一关键字：1 2 3 4 5 6 7 8
第二关键字：2 4 3 7 1 8 5 6
然后我们找到那个第二关键字最小的结点，上面的例子的话就是第一关键字为5的结点
那么我们首先经过的就是5.
然后看5的左孩子区间[1,4]，同理找最小，就是第一关键字为1的结点，此时要经过的就是1.然后发现1没有左孩子
就进入右孩子[2,4]去找，找到第一关键字为3的点，那么经过的就是3了，再找左孩子，经过了2，此时要退回去，又经过了3，然后找3的右孩子
经过了4，再退回去，又经过了3，再往回退，然后经过3的父亲就是1，再退回去就经过了5，同理处理5的右孩子区间
就这样，记录经过的结点，串就构造出来了，然后KMP就行了
加完输入优化后，这种方法用线段树实现后的速度是1900ms+
当然，必须自己手写堆栈 很蛋疼
当然此题可以用RMQ,但对于此题来讲，RMQ有点卡空间 毕竟60W*log(60W) 不小，不过我写了一遍后发现，竟然卡着空间过了，不过竟然比线段树还慢，而且是我预处理log的情况下，真是神奇了。
下面代码中的solve函数是我刚开始写的递归，只不过爆栈了，改成手写堆栈后，起到的作用也就是看起来容易明白
#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <cstdlib>#include <algorithm>#define lch(x) x<<1#define rch(x) x<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int inf = 111111111;const int maxn = 1009;const double esp = 1e-6;const int N = 600009;int n;int st[N];int now[N];struct point{ int a, b; int id;} pp[N];struct node{ int x, id;} p[N];int hash[N];bool cmp(node x, node y){ return x.x < y.x;}int mi[4*N];void build(int l, int r, int rt){ if(l == r) { mi[rt] = p[l].id; return ; } int m = (l + r) >> 1; build(lson); build(rson); mi[rt] = min(mi[lch(rt)], mi[rch(rt)]);}int query(int L, int R, int l, int r, int rt){ if(L <= l && R >= r) return mi[rt]; int ret = inf; int m = (l + r) >> 1; if(L <= m) ret = min(ret, query(L, R, lson)); if(R > m) ret = min(ret, query(L, R, rson)); return ret;}int len;char s1[1888888], s2[7777];int solve(int s, int t){ if(s > t) return 0; int id = query(s, t, 1, n, 1); int k = hash[id] % 2; s1[len++] = k + '0'; if(solve(s, hash[id] - 1)) { s1[len++] =k + '0'; } if(solve(hash[id] + 1, t)) { s1[len++] =k + '0'; } return 1;}int next[11111];void get_next(char *str){ int i = 0, j = -1, l = strlen (str); next[0] = j; while(i < l) { if(j == -1 || str[j] == str[i]) { i++, j++; next[i]= j; } else j = next[j]; }}int KMP(char *str1, char *str2){ int ans = 0; int i = -1, j = -1, l1 = strlen(str1), l2 = strlen(str2); while(i < l1) { if(j == -1 || str1[i] == str2[j]) { i++, j++; } else j = next[j]; if(j == l2) ans++; } return ans;}int in(){ char ch; int a = 0; while((ch = getchar()) == ' ' || ch == '\n'); a += ch - '0'; while((ch = getchar()) != ' ' && ch != '\n') { a *= 10; a += ch - '0'; } return a;}int main(){ int ca, tt=0; scanf("%d", &ca); while(ca--) { scanf("%d", &n); for(int i = 1; i <= n; i++) p[i].x = in(), p[i].id = i; sort(p + 1 ,p + n + 1, cmp); for(int i = 1; i <= n; i++) hash[p[i].id] = i; build(1, n, 1); len = 0; //solve(1, n); memset(now, 0, sizeof(now)); pp[0].a = 1; pp[0].b = n; pp[0].id = 1; st[0] = 0; int top = 0; //模拟栈st的坐标 len = 0; //串长 int cnt = 0; //栈里存的结构体point的坐标 while(top>=0) { int num = st[top]; int a = pp[num].a; int b = pp[num].b; int id = pp[num].id; char k = hash[id] % 2+'0'; //s1[len++] = k; if(now[num]==0) //第一次 { if(hash[id]>a) //有左孩子 { pp[++cnt].a = a; pp[cnt].b = hash[id]-1; pp[cnt].id = query(a, hash[id]-1, 1, n, 1); st[++top] = cnt; s1[len++] = k; } now[num] = 1; } else if(now[num]==1) //第二次，处理完左孩子了 { if(hash[id]<b) //有右孩子 { pp[++cnt].a = hash[id]+1; pp[cnt].b = b; pp[cnt].id = query(hash[id]+1, b, 1, n, 1); st[++top] = cnt; s1[len++] = k; } now[num] = 2; } else if(now[num]==2) //第三次，两个孩子都处理完了 { s1[len++] = k; --top; } } s1[len] = '\0'; // cout<<s1<<endl; scanf("%s", s2); get_next(s2); printf("Case #%d: %d\n", ++tt, KMP(s1, s2)); } return 0;}