转载

$Luogu$ $P4792$ $[BalticOI 2018]$ 火星人的 $DNA$

链接

背景

\(Baltic\) \(Olympiad\) \(in\) \(Informatics\) \(2018\) \(Day1\) \(T2\)\(Luogu\) \(P3524/LOJ2775\) (原题面暂时无法打开)

题意

给定一个长为 \(n\) 的字符串,字符集大小为 \(k\) ,有 \(p\) 个形如 \(a\) \(b\) 的要求,代表 \(a\) 字符出现的次数不能少于 \(b\) 。求满足所有要求的最短字串长度。

解法

双指针法。设定左右端点,每次不满足所有要求时扩展右端点,更新满足所有要求还需要某种字符多少个。满足所有要求后,更新答案。若右端点到第 \(n\) 个字符时未能满足所有要求,则退出。更新完答案后,为了防止多找字符,将左端点向右扩展,更新满足所有要求还需要某种字符多少个。
这种方法保证了每个字符只会被经过不超过 \(2\) 次,总时间复杂度为 \(O(n)\)

细节

\(1.\) 如所有字符均扫描完后未能更新答案,则判定无解。

代码

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,k,q,x,y,l=1,r,s[200005],cnt[200005],ans=1e9+7; inline void add(int x) { cnt[x]--; if(!cnt[x]) q--; } inline void del(int x) { cnt[x]++; if(cnt[x]==1) q++; } int main() { n=read(); k=read(); q=read(); for(register int i=1;i<=n;i++) s[i]=read(); for(register int i=1;i<=q;i++) { x=read(); y=read(); cnt[x]=y; } while(1) { while(r<=n&&q) add(s[++r]); if(n<r) break; ans=min(ans,r-l+1); del(s[l++]); } if(ans<1e9+7) printf("%d\n",ans); else printf("impossible\n"); return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11348939.html

正文到此结束
本文目录