题解 | 牛客小白月赛115 CDEFG Java题解

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

C 命运之弹（Easy Version） && G 命运之弹（Hard Version）

由于在最后一次攻击使用扭转乾坤比全程不使用扭转乾坤更优，因此本题解只考虑使用一次扭转乾坤的情况。。。。。对于固定位置使用扭转乾坤，后缀需要使用的转瞬即逝是固定的，因此考虑前缀需要的次数，那么可以发现，在v减小的过程中，原本不需要的某些前缀位置变得需要转瞬即逝了，因此可以考虑倒序v来计算需要的最小次数（更改某些“后缀的修改位置”），并用延迟标记线段树来维护区间最小次数，时间复杂度O((n+q)logn)

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));
        int n=Integer.parseInt(bf.readLine()),a[][]=new int[n][],p=1,count[]=new int[n+5],opCount[]=new int[n];
        TreeSet<Integer> set=new TreeSet<>();
        Map<Integer,Integer> map=new HashMap<>();
        StringTokenizer sto=new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            a[i]=new int[]{Integer.parseInt(sto.nextToken()),i};
            set.add(a[i][0]);
        }
        for(int b:set){
            map.put(b,p++);
        }
        for(int i=n-1;i>=0;i--){
            for(int j=map.get(a[i][0]);j!=0;j-=j&-j){
                opCount[i]-=count[j];
            }
            opCount[i]+=n-i-1;
            for(int j=map.get(a[i][0]);j<=p;j+=j&-j){
                count[j]++;
            }
        }
        int q=Integer.parseInt(bf.readLine()),ans[][]=new int[q][];
        for(int i=0;i<q;i++){
            ans[i]=new int[]{Integer.parseInt(bf.readLine()),i};
        }
        Arrays.sort(a,(a1,a2)->Integer.compare(a2[0],a1[0]));
        Arrays.sort(ans,(a1,a2)->Integer.compare(a2[0],a1[0]));
        SegTree st=new SegTree(0,n-1);
        build(st,opCount);
        for(int i=0,j=0;i<q;i++){
            while(j<n&&a[j][0]>ans[i][0]){
                modify(st,a[j][1]+1,n-1);
                j++;
            }
            ans[i][0]=st.min;
        }
        Arrays.sort(ans,(a1,a2)->Integer.compare(a1[1],a2[1]));
        for(int b[]:ans){
            bw.write(b[0]+"\n");
        }
        bw.flush();
    }
    static void modify(SegTree st,int a,int b){
        if(a<=b){
            int l=st.l,r=st.r;
            if(l==a&&r==b){
                st.min++;
                st.inc++;
            }
            else{
                clear(st);
                int mid=(l+r)>>1;
                if(b<=mid){
                    modify(st.left,a,b);
                }
                else if(a>mid){
                    modify(st.right,a,b);
                }
                else{
                    modify(st.left,a,mid);
                    modify(st.right,mid+1,b);
                }
                st.min=Math.min(st.left.min,st.right.min);
            }
        }
    }
    static void clear(SegTree st){
        if(st.l<st.r&&st.inc!=0){
            st.left.inc+=st.inc;
            st.right.inc+=st.inc;
            st.left.min+=st.inc;
            st.right.min+=st.inc;
            st.inc=0;
        }
    }
    static void build(SegTree st,int opCount[]){
        int l=st.l,r=st.r;
        if(l==r){
            st.min=opCount[l];
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,opCount);
            build(st.right,opCount);
            st.min=Math.min(st.left.min,st.right.min);
        }
    }
}
class SegTree{
    int l,r,inc=0,min;
    SegTree left,right;
    SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

D 操作字符串

考虑“最大公约”字串，该字串模式下，记录每个位置最大的字符频率，剩下的就是该修改的，时间复杂度O(nlogL+26L)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),gcd=0,count[][]=new int[100005][26],ans=0;
        String s[]=new String[n];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
            gcd=gcd(gcd,s[i].length());
            ans+=s[i].length();
        }
        for(String t:s){
            for(int j=t.length()-1;j>=0;j--){
                count[j%gcd][t.charAt(j)-'a']++;
            }
        }
        for(int i=0;i<gcd;i++){
            int max=0;
            for(int c:count[i]){
                max=Math.max(max,c);
            }
            ans-=max;
        }
        System.out.println(ans);
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

E 魔法卷轴

贪心将数字变小，如果时间戳已过，则需要将数字变大，另外需要优先在时间戳下的已经准备二次打击的目标，时间复杂度O(tnlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            TreeSet<Integer> set=new TreeSet<>();
            Queue<Integer> q=new PriorityQueue<>();
            for(int j=0;j<n;j++){
                q.add(sc.nextInt());
            }
            boolean ok=true;
            for(int j=1;!q.isEmpty();j++){
                if(!set.isEmpty()&&set.first()-j==0){
                    set.remove(j);
                }
                else{
                    int a=q.poll();
                    if(j+1<=a-1&&!set.contains(a-1)){
                        set.add(a-1);
                    }
                    else if(j<=a&&!set.contains(a+1)){
                        set.add(a+1);
                    }
                    else{
                        ok=false;
                        break;
                    }
                }
            }
            System.out.println(ok?"YES":"NO");
        }
    }
}

F 游戏高手

每个角色克别人次数减去被克的次数就是贡献，因此每一轮都贪心选当前最大的即可，时间复杂度O(t(m+nlogn))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),count[]=new int[n+5],ans=0;
            for(int j=sc.nextInt();j!=0;j--){
                count[sc.nextInt()]++;
                count[sc.nextInt()]--;
            }
            Arrays.sort(count,1,n+1);
            for(int j=1;j<n;j+=2){
                ans-=count[n-j];
            }
            System.out.println(ans);
        }
    }
}

另有常规图论做法，还不会