本文主要是介绍JZOJ_7.19C组第四题 秀姿势,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
给出一个序列,我们可以进行k次操作,每次操作都能刷掉所有相同的数,求出这个序列中的连续子序列最长。
思路
这题我们可以用到队列。维护一个区间,使里面数的种类不超过k+1,那答案就为这些合法区间中的相同的数的数量的最大值。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define p 1000007
#define hash(x) x%p
using namespace std;
int n,k,a[100001],h[p],v[p],s,head,sum,ans,w1,w2;
int locate(int x)
{int f=hash(x);while (h[f]!=0&&h[f]!=x) f=(f+1)%p;return f;
}
int main()
{scanf("%d%d",&n,&k);k++;for (int i=1;i<=n;i++){scanf("%d",&a[i]);w1=locate(a[i]);if (!v[w1]) sum++;//如果新加一个没出现过的数,那么sum(区间里面数的种数)+1 v[w1]++;//v[i]代表i这个数的数量h[w1]=a[i];//存hash表 while(sum>k)//弹到种数<=k+1{w2=locate(a[head]);v[w2]--;if (!v[w2]){sum--;h[w2]=0;}head++;}ans=max(ans,v[w1]);//取最大值 }printf("%d",ans);
}
这篇关于JZOJ_7.19C组第四题 秀姿势的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!