意甲冠军：
特定n，
下面是一个1-n该装置。
下面的二进制字符串。
按给定的建立二叉树安排。
然后遍历树（根->左子树->根->右子树->根）
当遍历节点 如果右值为奇数入栈一个1，若为偶数入栈一个0
得到一个母串。
问母串中出现了几次子串。
思路：
先是建树得到母串。然后求子串个数就是裸的KMP。
建树就是找个规律，然后用线段树维护一下输入的排列
#include#include #include #include using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long ll;#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1template inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1;}template inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0');}//const int N = 600000+5;const int M = 70000+5;int mi[N<<2], pos[N];inline void up(int& fa, int& ls, int& rs) { if (ls>rs) fa = rs; else fa = ls;}void build(int l, int r, int rt) { if (l == r) { mi[rt] = pos[l]; } else { int mid = (l+r)>>1; build(lson); build(rson); up(mi[rt], mi[rt<<1], mi[rt<<1|1]); }}int query(int L, int R, int l, int r, int rt) { if (L<= l && r<=R) { return mi[rt]; } else { int mid = (l+r)>>1; if (L>mid) return query(L, R, rson); else if (R<=mid) return query(L, R, lson); else return min(query(L, mid, lson), query(mid+1, R, rson)); }}void update(int p, int v, int l, int r, int rt) { if (l == r) { mi[rt] = v; } else { int mid = (l+r)>>1; if (p <= mid) update(p, v, lson); else update(p, v, rson); up(mi[rt], mi[rt<<1], mi[rt<<1|1]); }}int T = 0, n, a[N], L[N], R[N];char s[M], ch[N*3];int nex[M], top;void dfs(int u, int l, int r) { update(u, n+1, 1, n, 1); int v = query(l, u, 1, n, 1); if (v != n+1) { L[u] = a[v]; dfs(a[v], l, u); } v = query(u, r, 1, n, 1); if (v != n+1) { R[u] = a[v]; dfs(a[v], u, r); }}void f(int u) { char c; if (u&1) c = '1'; else c = '0'; ch[top++] = c; if (L[u] != -1) { f(L[u]); ch[top++] = c; } if (R[u] != -1) { f(R[u]); ch[top++] = c; }}void work() { int v, len, idx, ans = 0; rd(n); for (int i = 1; i <= n; ++i) { rd(a[i]); pos[a[i]] = i; } build(1, n, 1); memset(L, -1, sizeof L); memset(R, -1, sizeof R); dfs(a[1], 1, n); // scanf("%s", s); len = strlen(s); nex[0] = nex[1] = 0; for (int i = 1; i < len; ++i) { int j = nex[i]; while (j && s[j] != s[i]) j = nex[j]; if (s[i] == s[j]) nex[i+1] = j+1; else nex[i+1] = 0; } // top = 0; f(a[1]); idx = 0; for (int i = 0; i < top; ++i) { while (idx && s[idx] != ch[i]) idx = nex[idx]; if (s[idx] == ch[i]) ++ idx; if (idx == len) { ++ ans; idx = nex[idx]; } } printf("Case #%d: %d\n", ++T, ans);}int main() { int cas; scanf("%d", &cas); while (cas-->0) work(); return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。