大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
意甲冠军:
特定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; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117292.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...