#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #include<queue> #include<vector> using namespace std; const int maxn=100010; struct cyc{int num,ord,rank;}b[maxn]; int n,m,ss,tt,a[maxn],vis[maxn],nexts[maxn],ans,tot,T,ms; char cc; int read() { ss=0,tt=1; while(!isdigit(cc=getchar()))if(cc=='-')tt=-1; do{ss=ss*10+cc-'0';}while(isdigit(cc=getchar())); return ss*tt; } bool cmp(cyc a,cyc b) {return a.num<b.num;} int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(),b[i].num=a[i],b[i].ord=i; sort(b+1,b+n+1,cmp); tot=1;b[1].rank=1; for(int i=2;i<=n;i++)if(b[i].num!=b[i-1].num)b[i].rank=++tot;else b[i].rank=tot; for(int i=1;i<=n;i++)a[b[i].ord]=b[i].rank; // for(int i=1;i<=n;i++)printf("%d ",a[i]);printf(" "); memset(vis,0,(n+1)*4); memset(nexts,0x3f,(n+1)*4); for(int i=1;i<=n;i++)if(!vis[a[i]])vis[a[i]]=i;else nexts[vis[a[i]]]=i,vis[a[i]]=i; ans=0;ms=n+1; // for(int i=1;i<=n;i++)printf("%d ",nexts[i]);printf(" "); for(int i=1;i<=n;i++) { if(ms<=i)ans++,ms=n+1; ms=min(ms,nexts[i]); } printf("%d ",ans+1); } return 0; }
#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #include<queue> #include<vector> using namespace std; const int maxn=100010; int n,m,ss,tt,num1[maxn],num2[maxn],num0[maxn],a[maxn],T; char s[maxn]; char cc; int read() { ss=0,tt=1; while(!isdigit(cc=getchar()))if(cc=='-')tt=-1; do{ss=ss*10+cc-'0';}while(isdigit(cc=getchar())); return ss*tt; } int main() { T=read(); while(T--) { n=read(),m=read(); scanf("%s",s+1); for(int i=1;i<=n;i++)a[i]=s[i]-'0'; num0[n+1]=num1[n+1]=num2[n+1]=0; for(int i=n;i>=1;i--)num0[i]=num0[i+1]+(a[i]%3==0?1:0); for(int i=n;i>=1;i--)num1[i]=num1[i+1]+(a[i]%3==1?1:0); for(int i=n;i>=1;i--)num2[i]=num2[i+1]+(a[i]%3==2?1:0); bool flag=0; for(int i=1;i<=n;i++) if(a[i]!=0&&!flag&&m-i+1>=0) { int k=m-i+1; int b=(num1[i+1]*1+num2[i+1]*2)%3; b=(b+a[i])%3; if(k==0&&b==0){flag=1;continue;} for(int j=0;j<=2;j++)if(num1[i+1]>=j&&!flag) { int jj=(j-b+3)%3; if(num2[i+1]<jj)continue; int n1=num1[i+1]-j,n2=num2[i+1]-jj,kk=k-j-jj; if((n1/3)+(n2/3)>=(kk/3))if(num0[i+1]>=(kk-(kk/3)*3))flag=1; if((n1/3)+(n2/3)<(kk/3))if(num0[i+1]>=kk-(n1/3)*3-(n2/3)*3)flag=1; } } if(flag)printf("yes ");else printf("no "); } return 0; }