意甲冠军：
特定n，
下面是一个1-n该装置。
下面的二进制字符串。
按给定的建立二叉树安排。
然后遍历树（根->左子树->根->右子树->根）
当遍历节点 如果右值为奇数入栈一个1，若为偶数入栈一个0
得到一个母串。
问母串中出现了几次子串。
思路：
先是建树得到母串。然后求子串个数就是裸的KMP。
建树就是找个规律，然后用线段树维护一下输入的排列
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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|1
template <class T>
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 <class T>
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;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。