Longest Subarray
题意: 给 n,c,k, 给 n 个数字, 已知数字都小于 c, 求一个合法连续数字串的最长长度, 合法串要求出现的数字要么出现 0 次要么就必须出现次数>=k.
思路: 从左到右枚举区间右端点, 与此同时用线段树维护满足条件的左端点, 线段树每个叶节点代表这个节点作为左端点时, 所拥有的满足条件的数字个数(如果为 C 证明这个左端点可取). 从左到右枚举右端点时, 判断每个新增的数字,
这个数字对前面的每个左端点拥有的合法数字个数有两点影响:
1. 设目前右端点枚举到第 i 位, 这个数字上一次出现的位置为 pos, 那么在 [pos+1,i-1] 这个区间内的点作为左端点时, i-1 作为右端点时, 是没有 a[i]这个数字, 而 i 作为右端点出现了 a[i], 所以 [pos+1,i-1] 合法个数需要 - 1.
2. 设目前右端点枚举到第 i 位, 这个数字这个数字目前出现记为第一次, 往前的第 k+1 位的位置记为 pos, 第 k 位位置记为 pos2, 需要注意, 在 [pos+1,pos2] 这个区间作为左端点, i-1 作为右端点时, a[i]出现了 K-1 次, 而枚举到右端点为 i, 新增了 a[i]后 [pos+1,i] 这个区间中 a[i]出现次数达到 k 次了, 区间内的合法个数需要 + 1.
对于每次枚举一个右端点, 线段树中叶子节点为 C 的位置就是合法的,[1,i]线性搜索太慢, 所以需要线段树记录叶子节点的最大值和最大值的位置, 在 query 时优先查询靠左边的同时满足最大值为 C 的位置. 用 vector 记录每个数字出现的位置.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e5+10;
- vector<int> v[maxn];
- int n,k,c;
- struct note
- {
- int left,right,maxx,lazy,ans;
- void up(int val)
- {
- maxx+=val;
- lazy+=val;
- }
- } tree[maxn*4];
- void pushup(int id)
- {
- tree[id].maxx=max(tree[id<<1].maxx,tree[id<<1|1].maxx);
- if(tree[id].maxx==tree[id<<1].maxx) tree[id].ans=tree[id<<1].ans;
- else tree[id].ans=tree[id<<1|1].ans;
- }
- void pushdown(int id)
- {
- if(tree[id].lazy)
- {
- tree[id<<1].up(tree[id].lazy);
- tree[id<<1|1].up(tree[id].lazy);
- tree[id].lazy=0;
- }
- }
- void build(int id,int l,int r)
- {
- tree[id].left=tree[id].ans=l;
- tree[id].right=r;
- tree[id].maxx=tree[id].lazy=0;
- if(l==r)
- return;
- int mid=(l+r)/2;
- build(id<<1,l,mid);
- build(id<<1|1,mid+1,r);
- pushup(id);
- }
- int query(int id,int l,int r)
- {
- if(tree[id].maxx!=c)
- return -1;
- if(l<=tree[id].left&&tree[id].right<=r)
- return tree[id].ans;
- pushdown(id);
- int mid=(tree[id].left+tree[id].right)/2;
- if(r<=mid) return query(id<<1,l,r);
- else if(l>mid) return query(id<<1|1,l,r);
- else
- {
- int tmp;
- tmp=query(id<<1,l,mid);
- if(tmp!=-1) return tmp;
- else return query(id<<1|1,mid+1,r);
- }
- }
- void update(int id,int l,int r,int val)
- {
- if(l<=tree[id].left&&tree[id].right<=r)
- {
- tree[id].up(val);
- return;
- }
- pushdown(id);
- int mid=(tree[id].left+tree[id].right)/2;
- if(l<=mid) update(id<<1,l,r,val);
- if(r>mid) update(id<<1|1,l,r,val);
- pushup(id);
- }
- int main()
- {
- while(~scanf("%d%d%d",&n,&c,&k))
- {
- for(int i=1; i<=c; i++)
- {
- v[i].clear();
- v[i].push_back(0);
- }
- build(1,1,n);
- int ans=0;
- for(int i=1; i<=n; i++)
- {
- int x;
- scanf("%d",&x);
- update(1,i,i,c-1);
- if(v[x].back()<i-1) update(1,v[x].back()+1,i-1,-1);
- v[x].push_back(i);
- if(v[x].size()>=k+1)
- {
- int pos=v[x].size()-k-1;
- update(1,v[x][pos]+1,v[x][pos+1],1);
- }
- int tmp=query(1,1,i);
- if(tmp!=-1)
- ans=max(ans,i-tmp+1);
- }
- printf("%d\n",ans);
- }
- }
- View Code
I Love Palindrome String 回文自动机, 哈希
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- const int maxn = 300005 ;
- const int N = 26 ;
- int nxt[maxn][N] ;//next 指针, next 指针和字典树类似, 指向的串为当前串两端加上同一个字符构成
- int fail[maxn] ;//fail 指针, 失配后跳转到 fail 指针指向的节点
- int cnt[maxn] ;
- int num[maxn] ;
- int len[maxn] ;//len[i]表示节点 i 表示的回文串的长度
- int S[maxn] ;// 存放添加的字符
- int last ;// 指向上一个字符所在的节点, 方便下一次 add
- int n ;// 字符数组指针
- int p ;// 节点指针
- char a[maxn];
- int id[maxn];
- const ull hash1=201320111;
- ull ha[maxn],pp[maxn];
- int ans[maxn];
- ull getha(int l,int r)
- {
- if(l==1) return ha[r];
- else return ha[r]-ha[l-1]*pp[r-l+1];
- }
- int check(int l,int r)
- {
- int mid=(l+r)/2;
- if((r-l+1)%2==0) return getha(l,mid)==getha(mid+1,r);
- return getha(l,mid)==getha(mid,r);
- }
- int newnode ( int l ) // 新建节点
- {
- for ( int i = 0 ; i <N ; ++ i ) nxt[p][i] = 0 ;
- cnt[p] = 0 ;
- num[p] = 0 ;
- len[p] = l ;
- return p ++ ;
- }
- void init () // 初始化
- {
- p = 0 ;
- newnode ( 0 ) ;
- newnode ( -1 ) ;
- last = 0 ;
- n = 0 ;
- S[n] = -1 ;// 开头放一个字符集中没有的字符, 减少特判
- fail[0] = 1 ;
- }
- int get_fail ( int x ) // 和 KMP 一样, 失配后找一个尽量最长的
- {
- while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
- return x ;
- }
- void add (int c )
- {
- c -= 'a' ;
- S[++ n] = c ;
- int cur = get_fail ( last ) ;// 通过上一个回文串找这个回文串的匹配位置
- if ( !nxt[cur][c] ) // 如果这个回文串没有出现过, 说明出现了一个新的本质不同的回文串
- {
- int now = newnode ( len[cur] + 2 ) ;// 新建节点
- fail[now] = nxt[get_fail (fail[cur])][c] ;// 和 AC 自动机一样建立 fail 指针, 以便失配后跳转
- nxt[cur][c] = now ;
- num[now] = num[fail[now]] + 1 ;
- }
- last = nxt[cur][c] ;
- cnt[last] ++ ;
- id[last]=n;
- }
- void count ()
- {
- for ( int i = p - 1 ; i>= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
- // 父亲累加儿子的 cnt, 因为如果 fail[v]=u, 则 u 一定是 v 的子回文串!
- for(int i=2; i<p; i++)
- {
- if(check(id[i]-len[i]+1,id[i]))
- ans[len[i]]+=cnt[i];
- // for(int j=id[i]-len[i]+1;j<=id[i];j++)
- // printf("%c",a[j]);
- // printf("%d \n",cnt[i]);
- }
- }
- int main()
- {
- pp[0]=1;
- for(int i=1; i<maxn; i++)
- pp[i]=pp[i-1]*hash1;
- while(~scanf("%s",a+1))
- {
- int len1=strlen(a+1);
- for(int i=1; i<=len1; i++)
- ans[i]=0;
- ha[0]=0;
- for(int i=1; i<=len1; i++)
- ha[i]=ha[i-1]*hash1+a[i];
- // printf("%d",check(1,7));
- init();
- for(int i=1; i<=len1; i++)
- add(a[i]);
- count();
- for(int i=1; i<=len1; i++)
- {
- if(i!=n) printf("%d",ans[i]);
- else printf("%d",ans[i]);
- }
- printf("\n");
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3213042.html