# [Nowcoder]2020牛客暑期多校训练营（第六场）K

k-bag的定义是指：

1 2 3 3 2 1

check这段序列只需要check 第三个位置向前是否可行，第6个位置向前是否可行

Note几个坑：

1.当有大于m的数时,NO！

2.本身就是k-bag，NO！

3.不要忘记check保留的数！！保留的数有重复的必然不可以！

4.map处理超时了，手写了哈希散列~

Code：
``````/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include bits/stdc++.h
#define debug(x) cout#x":"xendl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =1e6+10;
const int mod= 1e9+7;
const int Mod = 1e6+7;
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'(in'0'||in'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in='0'in='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll a[maxn];

ll ncnt = 0;
struct Hash{
int e,next,w;
}H[maxn];
void Insert(ll x,ll wt){
ll temp=x%Mod;
if(H[i].e==x){
H[i].w += wt;
return;
}
}
}
ll Find(ll x){
ll temp=x%Mod;
if(H[i].e==x) return H[i].w;
}
return 0;
}

ll cnt = 0;
void del(ll x){
Insert(x,-1);
if(Find(x)==0) cnt--;
}
Insert(x,1);
if(Find(x) == 1) cnt++;
}

int f[maxn];
int pre[maxn],cur[maxn];
int judge(int x){
int k = x+m;
for(;k=n;k+=m) if(!f[k]) return 0;
if(!pre[x]) return 0;
if(!cur[k-m+1]) return 0;
return 1;
}
int work(){
if(n%m!=0) return 0;
for(int i=m;i=n;i+=m) if(!f[i]) return 0;
return 1;
}
int main()
{
int T;scanf("%d",T);
while(T--){
cnt = 0;
for(int i=1;i=n;i++) f[i] = pre[i] = cur[i] = 0;

///1
int ff = 0;
for(int i=1;i=n;i++)
if(a[i]m) ff = 1;
if(ff){
printf("NO\n");
continue;
}
///1

///2
ncnt = 0;
if(cnt == m) f[m] = 1;
for(int i=m+1;i=n;i++){
del(a[i-m]);
if(cnt == m) f[i] = 1;
}
///2

///3
ff = work();
if(ff){
printf("NO\n");
continue;
}
///3
///4
pre[0] = 1;
ncnt = 0;
for(int i=1;i=min(m-1,n);i++){
if(Find(a[i])) pre[i] = 0;
else pre[i] = pre[i-1];
Insert(a[i],1);
}

cur[n+1] = 1;
ncnt = 0;
for(int i=n;i=max(n-m+1,0ll);i--){
if(Find(a[i])) cur[i] = 0;
else cur[i] = cur[i+1];
Insert(a[i],1);
}
///4

///5
int res = 0;
for(int i=0;i=min(m-1,n);i++){
int flag = judge(i);
if(flag){
res = 1;
break;
}
}
if(res) printf("YES\n");
else printf("NO\n");
///5
}
return 0;
}
/**
1000

**/
``````

• 英雄联盟