题解 | 牛客周赛 Round 66 DEFG Java题解

D~G Java题解，代码已去除冗余

D 小苯的蓄水池（easy） && E 小苯的蓄水池（hard）

本质上就是一个区间合并，为保证可以查询修改某个不大于端点的值，选用有序映射来表示区间，每个区间端点最多插入或者删除一次，时间复杂度O(nlogn+m)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),m=Integer.parseInt(arr[1]);
        arr=bf.readLine().split(" ");
        double pre[]=new double[n+1];
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+Integer.parseInt(arr[i-1]);
            map.put(i,i);
        }
        for(int i=0;i<m;i++){
            arr=bf.readLine().split(" ");
            if(arr[0].equals("1")){
                int l=map.floorKey(Integer.parseInt(arr[1])),r=map.get(map.floorKey(Integer.parseInt(arr[2])));
                map.put(l,r);
                while(map.higherKey(l)!=null){
                    int p=map.higherKey(l);
                    if(p>r){
                        break;
                    }
                    map.remove(p);
                }
            }
            else{
                int idx1=map.floorKey(Integer.parseInt(arr[1])),idx2=map.get(idx1);
                bw.write((pre[idx2]-pre[idx1-1])/(idx2-idx1+1)+"\n");
            }
        }
        bw.flush();
    }
}

F 小苯的字符提前

参考资料--->首先确定答案的首字母是哪一个，这个很简单，，，，接着就是判断同种字母被提前后的字典序，对于不在连续组内的两个字母提前方式，位置较前的字母，需要判断它后边的第一个不同字母的相对字典序，时间复杂度'O(Tn)'

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),k=sc.nextInt(),next[]=new int[n],start=0;
            List<Integer> idx[]=new List[26];
            for(int j=0;j<26;j++){
                idx[j]=new ArrayList<>();
            }
            Arrays.fill(next,-1);
            String s=sc.next();
            for(int j=n-1;j>=0;j--){
                if(j<n-1){
                    next[j]=s.charAt(j)==s.charAt(j+1)?next[j+1]:j+1;
                }
                idx[s.charAt(j)-'a'].add(j);
            }
            for(;idx[start].size()<k;k-=idx[start].size(),start++){

            }
            Deque<Integer> deque=new ArrayDeque<>();
            for(int a:idx[start]){
                if(next[a]==-1||s.charAt(a)<s.charAt(next[a])){
                    deque.addLast(a);
                }
                else{
                    deque.addFirst(a);
                }
            }
            for(int j=0;j<k-1;j++){
                deque.removeFirst();
            }
            int ans=deque.removeFirst();
            System.out.println(s.charAt(ans)+s.substring(0,ans)+s.substring(ans+1));
        }
    }
}

G 小苯的数位MEX

数位动态规划，需要预处理10位以下的，以每种数字开头且数字出现情况mask的数组数量，再按位计算，时间复杂度O(10^3*2^10+Tlog(n)*100*2^10)

import java.util.*;
public class Main{
    static int count[][][]=new int[10][10][1024],mex[]=new int[1024],pre[][]=new int[10][12];
    static{
        for(int j=1;j<1024;j++){
            for(int i=0;;i++){
                if(((j+1)>>i&1)==1){
                    mex[j]=i;
                    break;
                }
            }
        }
        count[0][0][0]=1;
        for(int i=1;i<10;i++){
            for(int j=0;j<10;j++){
                for(int k=0;k<1024;k++){
                    for(int p=0;p<10;p++){
                        count[i][j][k|(1<<j)]+=count[i-1][p][k];
                    }
                }
            }
        }
        for(int i=1;i<10;i++){
            pre[i]=pre[i-1].clone();
            for(int j=0;j<1024;j++){
                for(int k=1;k<10;k++){
                    pre[i][mex[j]]+=count[i][k][j];
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int x=sc.nextInt(),k=sc.nextInt(),ans1[]=find(x+k),ans2[]=find(x-1);
            for(int j=10;;j--){
                if(ans1[j]!=ans2[j]){
                    System.out.println(j+" "+(ans1[j]-ans2[j]));
                    break;
                }
            }
        }
    }
    static int[] find(int k){
        if(k==0){
            return new int[12];
        }
        List<Integer> list=new ArrayList<>();
        while(k!=0){
            list.add(k%10);
            k/=10;
        }
        int size=list.size(),ans[]=pre[size-1].clone(),mask=0;
        for(int i=size-1;i>=0;i--){
            int a=list.get(i);
            for(int j=(i==size-1?1:0);j<a;j++){
                int curMask=mask|(1<<j);
                //还剩下i位
                for(int p=0;p<10;p++){
                    for(int w=0;w<1024;w++){
                        ans[mex[curMask|w]]+=count[i][p][w];
                    }
                }
            }
            mask|=1<<a;
            if(i==0){
                ans[mex[mask]]++;
            }
        }
        return ans;
    }
}