十七届蓝桥杯模拟赛（一）
视频讲解
🎥 视频讲解
第一题
5分
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<202620262026/2;
return 0;
}
public class Main {
public static void main(String[] args){
System.out.println(202620262026L/2);
}
}
print(202620262026//2)
第二题
5分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int dp[5010][10];
int C(int a,int b){
if(a==b || b==0) return 1;
if(dp[a][b]) return dp[a][b];
return dp[a][b]=(C(a-1,b)+C(a-1,b-1))%mod;
}
int main(){
ll ans=(2*C(2026*2,3))%mod;
cout<<ans;
return 0;
}
import java.util.*;
public class Main {
static final int mod=1000000007;
static int[][] dp=new int[5010][10];
static int C(int a,int b){
if(a==b || b==0) return 1;
if(dp[a][b]!=0) return dp[a][b];
return dp[a][b]=(C(a-1,b)+C(a-1,b-1))%mod;
}
public static void main(String[] args){
long ans=(2L*C(2026*2,3))%mod;
System.out.println(ans);
}
}
import sys
sys.setrecursionlimit(200000)
mod=10**9+7
dp=[[0]*10 for _ in range(5010)]
def C(a,b):
if a==b or b==0:
return 1
if dp[a][b]:
return dp[a][b]
dp[a][b]=(C(a-1,b)+C(a-1,b-1))%mod
return dp[a][b]
ans=(2*C(2026*2,3))%mod
print(ans)
第三题
10分
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n;
int now=1,pre=-1;
int mcnt=0;
int ma=0;
int cnt[N];
int first[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(pre==a[i-1] || pre==-1){
}else{
now=ma;
}
cnt[a[i]]++;
if(cnt[a[i]]==1) first[a[i]]=i;
if(cnt[a[i]]>mcnt){
mcnt=cnt[a[i]];
ma=a[i];
}else if(cnt[a[i]]==mcnt && first[ma]<first[a[i]]){
ma=a[i];
}
if(now==a[i]) ans++;
pre=now;
}
cout<<ans;
return 0;
}
import java.util.*;
public class Main {
static final int N=1000010;
static int[] a=new int[N];
static int[] cnt=new int[N];
static int[] first=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=1;i<=n;i++) a[i]=sc.nextInt();
int now=1,pre=-1;
int mcnt=0,ma=0;
int ans=0;
for(int i=1;i<=n;i++){
if(pre==a[i-1] || pre==-1){
}else{
now=ma;
}
cnt[a[i]]++;
if(cnt[a[i]]==1) first[a[i]]=i;
if(cnt[a[i]]>mcnt){
mcnt=cnt[a[i]];
ma=a[i];
}else if(cnt[a[i]]==mcnt && first[ma]<first[a[i]]){
ma=a[i];
}
if(now==a[i]) ans++;
pre=now;
}
System.out.println(ans);
}
}
import sys
input=sys.stdin.readline
N=10**6+10
a=[0]*N
cnt=[0]*N
first=[0]*N
n=int(input())
arr=list(map(int,input().split()))
for i in range(1,n+1):
a[i]=arr[i-1]
now=1
pre=-1
mcnt=0
ma=0
ans=0
for i in range(1,n+1):
if pre==a[i-1] or pre==-1:
pass
else:
now=ma
cnt[a[i]]+=1
if cnt[a[i]]==1:
first[a[i]]=i
if cnt[a[i]]>mcnt:
mcnt=cnt[a[i]]
ma=a[i]
elif cnt[a[i]]==mcnt and first[ma]<first[a[i]]:
ma=a[i]
if now==a[i]:
ans+=1
pre=now
print(ans)
第四题
10分
#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
map<string,int> mp;
int main(){
cin>>n>>k;
cin>>s;
s=" "+s;
int ans=0;
for(int i=1;i+k-1<=n;i++){
string t=s.substr(i,k);
mp[t]++;
if(mp[t]==2) ans++;
}
cout<<ans;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
String s=sc.next();
s=" "+s;
HashMap<String,Integer> mp=new HashMap<>();
int ans=0;
for(int i=1;i+k-1<=n;i++){
String t=s.substring(i,i+k);
mp.put(t,mp.getOrDefault(t,0)+1);
if(mp.get(t)==2) ans++;
}
System.out.println(ans);
}
}
n,k=map(int,input().split())
s=input().strip()
s=" "+s
mp={}
ans=0
for i in range(1,n-k+2):
t=s[i:i+k]
mp[t]=mp.get(t,0)+1
if mp[t]==2:
ans+=1
print(ans)
第五题
12分
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,sum;
bool st[N];
int path[N];
int s[N][N];
void dfs(int u){
if(u==n+1){
for(int i=1;i<=n;i++){
s[1][i]=path[i];
}
for(int i=2;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
s[i][j]=s[i-1][j]+s[i-1][j+1];
}
}
if(sum==s[n][1]){
for(int i=1;i<=n;i++){
cout<<path[i]<<" ";
}
exit(0);
}
return;
}
for(int i=1;i<=n;i++){
if(st[i]) continue;
st[i]=true;
path[u]=i;
dfs(u+1);
st[i]=false;
}
}
int main(){
cin>>n>>sum;
dfs(1);
return 0;
}
import java.util.*;
public class Main {
static int n, sum;
static boolean[] st = new boolean[20];
static int[] path = new int[20];
static int[][] s = new int[20][20];
static void dfs(int u){
if(u==n+1){
for(int i=1;i<=n;i++) s[1][i]=path[i];
for(int i=2;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
s[i][j]=s[i-1][j]+s[i-1][j+1];
}
}
if(sum==s[n][1]){
for(int i=1;i<=n;i++) System.out.print(path[i]+" ");
System.exit(0);
}
return;
}
for(int i=1;i<=n;i++){
if(st[i]) continue;
st[i]=true;
path[u]=i;
dfs(u+1);
st[i]=false;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
sum=sc.nextInt();
dfs(1);
}
}
import sys
sys.setrecursionlimit(1000000)
n, sum_val = map(int, input().split())
st = [False]*(n+1)
path = [0]*(n+1)
s = [[0]*(n+1) for _ in range(n+1)]
def dfs(u):
if u==n+1:
for i in range(1,n+1):
s[1][i]=path[i]
for i in range(2,n+1):
for j in range(1,n-i+2):
s[i][j]=s[i-1][j]+s[i-1][j+1]
if sum_val==s[n][1]:
print(" ".join(map(str,path[1:])))
sys.exit(0)
return
for i in range(1,n+1):
if st[i]:
continue
st[i]=True
path[u]=i
dfs(u+1)
st[i]=False
dfs(1)
15分
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int path[N];
int sum,n;
bool st[N];
int dp[N][N];
void dfs(int u,int s){
if(s>sum) return;
if(u==n+1){
if(s==sum){
for(int i=1;i<=n;i++) cout<<path[i]<<" ";
exit(0);
}
return;
}
for(int i=1;i<=n;i++){
if(st[i]) continue;
st[i]=true;
path[u]=i;
dfs(u+1,s+i*dp[n-1][u-1]);
st[i]=false;
}
}
int main(){
for(int i=0;i<=15;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
}
cin>>n>>sum;
dfs(1,0);
return 0;
}
import java.util.*;
public class Main {
static final int N=20;
static int[] path=new int[N];
static boolean[] st=new boolean[N];
static int[][] dp=new int[N][N];
static int n,sum;
static void dfs(int u,int s){
if(s>sum) return;
if(u==n+1){
if(s==sum){
for(int i=1;i<=n;i++) System.out.print(path[i]+" ");
System.exit(0);
}
return;
}
for(int i=1;i<=n;i++){
if(st[i]) continue;
st[i]=true;
path[u]=i;
dfs(u+1,s+i*dp[n-1][u-1]);
st[i]=false;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
for(int i=0;i<=15;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
}
n=sc.nextInt();
sum=sc.nextInt();
dfs(1,0);
}
}
import sys
sys.setrecursionlimit(10**7)
N=20
path=[0]*N
st=[False]*N
dp=[[0]*N for _ in range(N)]
for i in range(16):
for j in range(i+1):
if j==0 or j==i:
dp[i][j]=1
else:
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
n,sum_val=map(int,input().split())
def dfs(u,s):
if s>sum_val:
return
if u==n+1:
if s==sum_val:
print(" ".join(map(str,path[1:n+1])))
sys.exit(0)
return
for i in range(1,n+1):
if st[i]:
continue
st[i]=True
path[u]=i
dfs(u+1,s+i*dp[n-1][u-1])
st[i]=False
dfs(1,0)
第六题
3分
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=m;j++) cin>>b[j];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,abs(a[i]-b[i]));
}
cout<<ans;
return 0;
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[] a=new int[n+1];
int[] b=new int[m+1];
for(int i=1;i<=n;i++) a[i]=sc.nextInt();
for(int i=1;i<=m;i++) b[i]=sc.nextInt();
Arrays.sort(a,1,n+1);
Arrays.sort(b,1,m+1);
int ans=0;
for(int i=1;i<=n;i++){
ans=Math.max(ans,Math.abs(a[i]-b[i]));
}
System.out.println(ans);
}
}
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
a[1:]=sorted(a[1:])
b[1:]=sorted(b[1:])
ans=0
for i in range(1,n+1):
ans=max(ans,abs(a[i]-b[i]))
print(ans)
15分
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],b[N];
void init(){
if(n>m){
for(int i=1;i<=n;i++){
swap(a[i],b[i]);
}
swap(n,m);
}
}
bool check(int x){
int i=1,j=1;
for(;i<=n && j<=m;j++){
if(abs(a[i]-b[j])<=x){
i++;
}
}
return i==n+1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
init();
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int l=0,r=1e9;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
import java.util.*;
public class Main {
static final int N=100010;
static int n,m;
static int[] a=new int[N];
static int[] b=new int[N];
static void init(){
if(n>m){
for(int i=1;i<=n;i++){
int t=a[i]; a[i]=b[i]; b[i]=t;
}
int t=n; n=m; m=t;
}
}
static boolean check(int x){
int i=1,j=1;
while(i<=n && j<=m){
if(Math.abs(a[i]-b[j])<=x) i++;
j++;
}
return i==n+1;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++) a[i]=sc.nextInt();
for(int i=1;i<=m;i++) b[i]=sc.nextInt();
init();
Arrays.sort(a,1,n+1);
Arrays.sort(b,1,m+1);
int l=0,r=1000000000;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
System.out.println(l);
}
}
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
if n>m:
a,b=b,a
n,m=m,n
a[1:]=sorted(a[1:])
b[1:]=sorted(b[1:])
def check(x):
i=1
for j in range(1,m+1):
if i<=n and abs(a[i]-b[j])<=x:
i+=1
return i==n+1
l,r=0,10**9
while l<r:
mid=(l+r)//2
if check(mid):
r=mid
else:
l=mid+1
print(l)
第七题
4分
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<-1<<"\n";
return 0;
}
public class Main {
public static void main(String[] args){
System.out.println(-1);
}
}
print(-1)
20分
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=300+10;
const int inf=1<<30;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin>>s;
int n=s.length();
s="#"+s;
vector<int> p0,p1,p2;
vector<vector<int>> pre(3,vector<int>(n+1,0));
for(int i=1;i<=n;i++){
if(s[i]=='0') p0.push_back(i);
if(s[i]=='1') p1.push_back(i);
if(s[i]=='2') p2.push_back(i);
pre[0][i]=pre[0][i-1]+(s[i]=='0');
pre[1][i]=pre[1][i-1]+(s[i]=='1');
pre[2][i]=pre[2][i-1]+(s[i]=='2');
}
int c0=p0.size(),c1=p1.size(),c2=p2.size();
vector dp(c0+1,vector(c1+1,vector(c2+1,vector<int>(3,inf))));
dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
auto f=[&](int i,int j,int k,int pos){
int x0=pre[0][pos]+(s[pos]=='0'?-1:0);
int x1=pre[1][pos]+(s[pos]=='1'?-1:0);
int x2=pre[2][pos]+(s[pos]=='2'?-1:0);
return max(x0-i,0)+max(x1-j,0)+max(x2-k,0);
};
for(int i=0;i<=c0;i++){
for(int j=0;j<=c1;j++){
for(int k=0;k<=c2;k++){
for(int t=0;t<3;t++){
if(dp[i][j][k][t]==inf) continue;
if(t==0){
if(j<c1) dp[i][j+1][k][1]=min(dp[i][j+1][k][1],dp[i][j][k][t]+f(i,j,k,p1[j]));
if(k<c2) dp[i][j][k+1][2]=min(dp[i][j][k+1][2],dp[i][j][k][t]+f(i,j,k,p2[k]));
}
if(t==1){
if(i<c0) dp[i+1][j][k][0]=min(dp[i+1][j][k][0],dp[i][j][k][t]+f(i,j,k,p0[i]));
if(k<c2) dp[i][j][k+1][2]=min(dp[i][j][k+1][2],dp[i][j][k][t]+f(i,j,k,p2[k]));
}
if(t==2){
if(i<c0) dp[i+1][j][k][0]=min(dp[i+1][j][k][0],dp[i][j][k][t]+f(i,j,k,p0[i]));
if(j<c1) dp[i][j+1][k][1]=min(dp[i][j+1][k][1],dp[i][j][k][t]+f(i,j,k,p1[j]));
}
}
}
}
}
int ans=min({dp[c0][c1][c2][0],dp[c0][c1][c2][1],dp[c0][c1][c2][2]});
cout<<(ans==inf?-1:ans)<<"\n";
return 0;
}
import java.util.*;
public class Main {
static final int INF = 1<<30;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length();
s=" "+s;
ArrayList<Integer> p0=new ArrayList<>();
ArrayList<Integer> p1=new ArrayList<>();
ArrayList<Integer> p2=new ArrayList<>();
int[][] pre=new int[3][n+1];
for(int i=1;i<=n;i++){
char c=s.charAt(i);
if(c=='0') p0.add(i);
if(c=='1') p1.add(i);
if(c=='2') p2.add(i);
for(int j=0;j<3;j++) pre[j][i]=pre[j][i-1];
if(c=='0') pre[0][i]++;
if(c=='1') pre[1][i]++;
if(c=='2') pre[2][i]++;
}
int c0=p0.size(),c1=p1.size(),c2=p2.size();
int[][][][] dp=new int[c0+1][c1+1][c2+1][3];
for(int i=0;i<=c0;i++)
for(int j=0;j<=c1;j++)
for(int k=0;k<=c2;k++)
Arrays.fill(dp[i][j][k],INF);
for(int t=0;t<3;t++) dp[0][0][0][t]=0;
for(int i=0;i<=c0;i++){
for(int j=0;j<=c1;j++){
for(int k=0;k<=c2;k++){
for(int t=0;t<3;t++){
if(dp[i][j][k][t]==INF) continue;
if(t==0){
if(j<c1){
int pos=p1.get(j);
dp[i][j+1][k][1]=Math.min(dp[i][j+1][k][1],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
if(k<c2){
int pos=p2.get(k);
dp[i][j][k+1][2]=Math.min(dp[i][j][k+1][2],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
}
if(t==1){
if(i<c0){
int pos=p0.get(i);
dp[i+1][j][k][0]=Math.min(dp[i+1][j][k][0],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
if(k<c2){
int pos=p2.get(k);
dp[i][j][k+1][2]=Math.min(dp[i][j][k+1][2],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
}
if(t==2){
if(i<c0){
int pos=p0.get(i);
dp[i+1][j][k][0]=Math.min(dp[i+1][j][k][0],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
if(j<c1){
int pos=p1.get(j);
dp[i][j+1][k][1]=Math.min(dp[i][j+1][k][1],
dp[i][j][k][t]+calc(pre,s,i,j,k,pos));
}
}
}
}
}
}
int ans=Math.min(dp[c0][c1][c2][0],
Math.min(dp[c0][c1][c2][1],dp[c0][c1][c2][2]));
System.out.println(ans==INF?-1:ans);
}
static int calc(int[][] pre,String s,int i,int j,int k,int pos){
int x0=pre[0][pos]+(s.charAt(pos)=='0'?-1:0);
int x1=pre[1][pos]+(s.charAt(pos)=='1'?-1:0);
int x2=pre[2][pos]+(s.charAt(pos)=='2'?-1:0);
return Math.max(x0-i,0)+Math.max(x1-j,0)+Math.max(x2-k,0);
}
}
import sys
input=sys.stdin.readline
INF=1<<30
s=input().strip()
n=len(s)
s=" "+s
p0,p1,p2=[],[],[]
pre=[[0]*(n+1) for _ in range(3)]
for i in range(1,n+1):
c=s[i]
if c=='0': p0.append(i)
if c=='1': p1.append(i)
if c=='2': p2.append(i)
for j in range(3):
pre[j][i]=pre[j][i-1]
if c=='0': pre[0][i]+=1
if c=='1': pre[1][i]+=1
if c=='2': pre[2][i]+=1
c0,c1,c2=len(p0),len(p1),len(p2)
dp=[[[[INF]*3 for _ in range(c2+1)] for _ in range(c1+1)] for _ in range(c0+1)]
for t in range(3):
dp[0][0][0][t]=0
def f(i,j,k,pos):
x0=pre[0][pos]+(-1 if s[pos]=='0' else 0)
x1=pre[1][pos]+(-1 if s[pos]=='1' else 0)
x2=pre[2][pos]+(-1 if s[pos]=='2' else 0)
return max(x0-i,0)+max(x1-j,0)+max(x2-k,0)
for i in range(c0+1):
for j in range(c1+1):
for k in range(c2+1):
for t in range(3):
if dp[i][j][k][t]==INF: continue
if t==0:
if j<c1:
dp[i][j+1][k][1]=min(dp[i][j+1][k][1],
dp[i][j][k][t]+f(i,j,k,p1[j]))
if k<c2:
dp[i][j][k+1][2]=min(dp[i][j][k+1][2],
dp[i][j][k][t]+f(i,j,k,p2[k]))
if t==1:
if i<c0:
dp[i+1][j][k][0]=min(dp[i+1][j][k][0],
dp[i][j][k][t]+f(i,j,k,p0[i]))
if k<c2:
dp[i][j][k+1][2]=min(dp[i][j][k+1][2],
dp[i][j][k][t]+f(i,j,k,p2[k]))
if t==2:
if i<c0:
dp[i+1][j][k][0]=min(dp[i+1][j][k][0],
dp[i][j][k][t]+f(i,j,k,p0[i]))
if j<c1:
dp[i][j+1][k][1]=min(dp[i][j+1][k][1],
dp[i][j][k][t]+f(i,j,k,p1[j]))
ans=min(dp[c0][c1][c2])
print(-1 if ans>=INF else ans)
第八题
10分
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],n,k,m;
void calc(){
map<int,int> mp;
int ans=0x3f3f3f3f;
for(int i=1,j=0;i<=n;i++){
while(j<n){
if(mp.size()==k){
ans=min(ans,j-i+1);
break;
}
j++;
mp[a[j]]++;
}
if(mp.size()==k) ans=min(ans,j-i+1);
mp[a[i]]--;
if(mp[a[i]]==0) mp.erase(a[i]);
}
if(ans==0x3f3f3f3f) ans=-1;
cout<<ans<<"\n";
}
int main(){
cin>>n>>k>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
int op;
cin>>op;
if(op==1){
int p,v;
cin>>p>>v;
a[p]=v;
}else{
calc();
}
}
return 0;
}
import java.util.*;
public class Main{
static int n,k,m;
static int[] a=new int[50010];
static void calc(){
Map<Integer,Integer> mp=new HashMap<>();
int ans=Integer.MAX_VALUE;
int j=0;
for(int i=1;i<=n;i++){
while(j<n){
if(mp.size()==k){
ans=Math.min(ans,j-i+1);
break;
}
j++;
mp.put(a[j],mp.getOrDefault(a[j],0)+1);
}
if(mp.size()==k) ans=Math.min(ans,j-i+1);
mp.put(a[i],mp.get(a[i])-1);
if(mp.get(a[i])==0) mp.remove(a[i]);
}
if(ans==Integer.MAX_VALUE) ans=-1;
System.out.println(ans);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
k=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++) a[i]=sc.nextInt();
for(int i=1;i<=m;i++){
int op=sc.nextInt();
if(op==1){
int p=sc.nextInt();
int v=sc.nextInt();
a[p]=v;
}else{
calc();
}
}
}
}
n,k,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
def calc():
mp={}
ans=float('inf')
j=0
for i in range(1,n+1):
while j<n:
if len(mp)==k:
ans=min(ans,j-i+1)
break
j+=1
mp[a[j]]=mp.get(a[j],0)+1
if len(mp)==k:
ans=min(ans,j-i+1)
mp[a[i]]-=1
if mp[a[i]]==0:
del mp[a[i]]
if ans==float('inf'):
ans=-1
print(ans)
for _ in range(m):
op,*rest=map(int,input().split())
if op==1:
p,v=rest
a[p]=v
else:
calc()
20分
#include<bits/stdc++.h>
using namespace std;
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
const int inf=1<<30;
struct SegTree{
struct Node{
int mn,sz;
vector<pair<int,int>> pre,suf;
Node():mn(inf),sz(0){}
};
int n,k,ok;
vector<Node> tr;
SegTree(int n,int k,vector<int>&a):n(n),k(k){
ok=(1<<k)-1;
tr.resize(4*n+5);
build(1,1,n,a);
}
void build(int x,int l,int r,vector<int>&a){
if(l==r){
tr[x].mn=(a[l]==ok?1:inf);
tr[x].pre={{a[l],1}};
tr[x].suf={{a[l],1}};
tr[x].sz=1;
return;
}
int mid=(l+r)>>1;
build(lc(x),l,mid,a);
build(rc(x),mid+1,r,a);
tr[x].sz=r-l+1;
pushup(x);
}
void pushup(int x){
auto &L=tr[lc(x)],&R=tr[rc(x)];
tr[x].mn=min(L.mn,R.mn);
tr[x].pre=L.pre;
for(auto &p:R.pre){
int v=L.pre.back().first|p.first;
if(tr[x].pre.back().first!=v){
tr[x].pre.push_back({v,L.sz+p.second});
if(v==ok) tr[x].mn=min(tr[x].mn,L.sz+p.second);
}
}
tr[x].suf=R.suf;
for(auto &p:L.suf){
int v=R.suf.back().first|p.first;
if(tr[x].suf.back().first!=v){
tr[x].suf.push_back({v,R.sz+p.second});
if(v==ok) tr[x].mn=min(tr[x].mn,R.sz+p.second);
}
}
for(int i=L.suf.size()-1,j=0;j<(int)R.pre.size();j++){
int v=L.suf[i].first|R.pre[j].first;
while(i-1>=0 && (L.suf[i-1].first|R.pre[j].first)==v) i--;
if(v==ok) tr[x].mn=min(tr[x].mn,L.suf[i].second+R.pre[j].second);
}
}
void modify(int x,int l,int r,int pos,int v){
if(l==r){
tr[x].pre={{v,1}};
tr[x].suf={{v,1}};
tr[x].mn=(v==ok?1:inf);
return;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(lc(x),l,mid,pos,v);
else modify(rc(x),mid+1,r,pos,v);
pushup(x);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,k,m;
cin>>n>>k>>m;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=1<<(a[i]-1);
}
SegTree seg(n,k,a);
while(m--){
int op; cin>>op;
if(op==1){
int p,v; cin>>p>>v;
a[p]=1<<(v-1);
seg.modify(1,1,n,p,a[p]);
}else{
int res=seg.tr[1].mn;
cout<<(res>=inf?-1:res)<<"\n";
}
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static final int INF = 1 << 30;
static class Node {
int mn, sz;
ArrayList<int[]> pre = new ArrayList<>();
ArrayList<int[]> suf = new ArrayList<>();
Node() { mn = INF; sz = 0; }
}
static class SegTree {
int n, k, ok;
Node[] tr;
SegTree(int n, int k, int[] a) {
this.n = n;
this.k = k;
ok = (1 << k) - 1;
tr = new Node[4 * n + 5];
for (int i = 0; i < tr.length; i++) tr[i] = new Node();
build(1, 1, n, a);
}
void build(int x, int l, int r, int[] a) {
if (l == r) {
tr[x].mn = (a[l] == ok ? 1 : INF);
tr[x].pre.add(new int[]{a[l], 1});
tr[x].suf.add(new int[]{a[l], 1});
tr[x].sz = 1;
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid, a);
build(x << 1 | 1, mid + 1, r, a);
tr[x].sz = r - l + 1;
pushup(x);
}
void pushup(int x) {
Node L = tr[x << 1], R = tr[x << 1 | 1];
Node cur = tr[x];
cur.mn = Math.min(L.mn, R.mn);
// pre
cur.pre = new ArrayList<>(L.pre);
for (int[] p : R.pre) {
int v = L.pre.get(L.pre.size() - 1)[0] | p[0];
if (cur.pre.get(cur.pre.size() - 1)[0] != v) {
cur.pre.add(new int[]{v, L.sz + p[1]});
if (v == ok) cur.mn = Math.min(cur.mn, L.sz + p[1]);
}
}
// suf
cur.suf = new ArrayList<>(R.suf);
for (int[] p : L.suf) {
int v = R.suf.get(R.suf.size() - 1)[0] | p[0];
if (cur.suf.get(cur.suf.size() - 1)[0] != v) {
cur.suf.add(new int[]{v, R.sz + p[1]});
if (v == ok) cur.mn = Math.min(cur.mn, R.sz + p[1]);
}
}
// cross
int i = L.suf.size() - 1;
for (int j = 0; j < R.pre.size(); j++) {
int v = L.suf.get(i)[0] | R.pre.get(j)[0];
while (i - 1 >= 0 && (L.suf.get(i - 1)[0] | R.pre.get(j)[0]) == v) i--;
if (v == ok) {
cur.mn = Math.min(cur.mn, L.suf.get(i)[1] + R.pre.get(j)[1]);
}
}
}
void modify(int x, int l, int r, int pos, int v) {
if (l == r) {
tr[x].pre.clear();
tr[x].suf.clear();
tr[x].pre.add(new int[]{v, 1});
tr[x].suf.add(new int[]{v, 1});
tr[x].mn = (v == ok ? 1 : INF);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) modify(x << 1, l, mid, pos, v);
else modify(x << 1 | 1, mid + 1, r, pos, v);
pushup(x);
}
}
static class FastScanner {
BufferedReader br;
StringTokenizer st;
FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); }
String next() throws IOException {
while (st == null || !st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return st.nextToken();
}
int nextInt() throws IOException { return Integer.parseInt(next()); }
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner();
int n = fs.nextInt(), k = fs.nextInt(), m = fs.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = 1 << (fs.nextInt() - 1);
}
SegTree seg = new SegTree(n, k, a);
StringBuilder out = new StringBuilder();
while (m-- > 0) {
int op = fs.nextInt();
if (op == 1) {
int p = fs.nextInt(), v = fs.nextInt();
a[p] = 1 << (v - 1);
seg.modify(1, 1, n, p, a[p]);
} else {
int res = seg.tr[1].mn;
out.append(res >= INF ? -1 : res).append('\n');
}
}
System.out.print(out);
}
}
import sys
sys.setrecursionlimit(1 << 25)
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
INF = 1 << 30
n = next(it)
k = next(it)
m = next(it)
ok = (1 << k) - 1
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = 1 << (next(it) - 1)
class Node:
__slots__ = ('mn', 'sz', 'pre', 'suf')
def __init__(self):
self.mn = INF
self.sz = 0
self.pre = []
self.suf = []
tr = [Node() for _ in range(4 * n + 5)]
def pushup(x):
L = tr[x << 1]
R = tr[x << 1 | 1]
t = tr[x]
t.mn = min(L.mn, R.mn)
t.pre = L.pre[:]
for v, c in R.pre:
nv = L.pre[-1][0] | v
if t.pre[-1][0] != nv:
t.pre.append((nv, L.sz + c))
if nv == ok:
t.mn = min(t.mn, L.sz + c)
t.suf = R.suf[:]
for v, c in L.suf:
nv = R.suf[-1][0] | v
if t.suf[-1][0] != nv:
t.suf.append((nv, R.sz + c))
if nv == ok:
t.mn = min(t.mn, R.sz + c)
i = len(L.suf) - 1
for j in range(len(R.pre)):
v = L.suf[i][0] | R.pre[j][0]
while i - 1 >= 0 and (L.suf[i - 1][0] | R.pre[j][0]) == v:
i -= 1
if v == ok:
t.mn = min(t.mn, L.suf[i][1] + R.pre[j][1])
def build(x, l, r):
if l == r:
tr[x].mn = 1 if a[l] == ok else INF
tr[x].pre = [(a[l], 1)]
tr[x].suf = [(a[l], 1)]
tr[x].sz = 1
return
mid = (l + r) >> 1
build(x << 1, l, mid)
build(x << 1 | 1, mid + 1, r)
tr[x].sz = r - l + 1
pushup(x)
def modify(x, l, r, pos, v):
if l == r:
tr[x].pre = [(v, 1)]
tr[x].suf = [(v, 1)]
tr[x].mn = 1 if v == ok else INF
return
mid = (l + r) >> 1
if pos <= mid:
modify(x << 1, l, mid, pos, v)
else:
modify(x << 1 | 1, mid + 1, r, pos, v)
pushup(x)
build(1, 1, n)
out = []
for _ in range(m):
op = next(it)
if op == 1:
p = next(it)
v = next(it)
a[p] = 1 << (v - 1)
modify(1, 1, n, p, a[p])
else:
res = tr[1].mn
out.append(str(-1 if res >= INF else res))
sys.stdout.write("\n".join(out))