题解 | 牛客练习赛135 Java题解

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

A 小柒的数字

由于y至少是x的2倍，因此n/x和n/y只有在同时为0的时候才成立，时间复杂度O(T)

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 x=sc.nextInt(),y=sc.nextInt(),n=sc.nextInt();
            System.out.println(Math.min(n,x-1));
        }
    }
}

B 小柒的逆序对(一)

分情况讨论：首先交换的下标相同，等于没有交换，逆序对儿奇偶性不变；否则逆序对儿数量只与两个下标之间的数字与两个下标的数字大小关系有关，根据贡献的计算，可发现每交换一次，m的奇偶改变一次，时间复杂度O(n+q)

import java.util.*;
public class Main{
    static String s[]={"even","odd"};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=(int)(sc.nextLong()&1),q=sc.nextInt();
        for(int i=0;i<n;i++){
            sc.nextInt();
        }
        for(int i=0;i<q;i++){
            if(sc.nextInt()!=sc.nextInt()){
                m^=1;
            }
            System.out.println(s[m]);
        }
    }
}

C 小柒的逆序对(2)

先遍历字符串，预处理每两种字母逆序关系的贡献，再根据每种所给的字母表按照贡献累计即可，时间复杂度O((n+c)*qC),C==26

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),q=sc.nextInt();
        long count[][]=new long[26][26];
        String s=sc.next();
        for(int i=0;i<26;i++){
            int pre=0;
            for(int j=0;j<n;j++){
                if(s.charAt(j)-'a'==i){
                    pre++;
                }
                else{
                    count[i][s.charAt(j)-'a']+=pre;
                }
            }
        }
        for(int i=0;i<q;i++){
            s=sc.next();
            long ans=0;
            for(int j=0;j<26;j++){
                for(int k=j+1;k<26;k++){
                    ans+=count[s.charAt(k)-'a'][s.charAt(j)-'a'];
                }
            }
            System.out.println(ans);
        }
    }
}

D 小柒分糖果

对于每种糖果，可以对每种取出的糖果数量进行“隔板法”，而又因为sigma(C(k,b),b∈[p,q])==C(q+1,b+1)-C(p,b+1)，可简化运算，时间复杂度O(nlog(mod)),mod==1e9+7

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,fac[]=new long[200005];
    static{
        fac[0]=1;
        for(int i=1;i<=200000;i++){
            fac[i]=fac[i-1]*i%mod;
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        long ans=1;
        for(int i=0;i<n;i++){
            //sigma(C(k+m-1,m-1),k+m∈[m,a+m] == C(a+m,m))
            ans=ans*comb(sc.nextInt()+m,m)%mod;
        }
        System.out.println(ans);
    }
    static long comb(int a,int b){
        return a<b?0:fac[a]*pow(fac[a-b]*fac[b]%mod,mod-2)%mod;
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}

E 小柒的神器

参考了出题人的解答思路，虽然不太理解为啥正确。。。。时间复杂度O(((α(n)+q)logC),C==18

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),q=sc.nextInt(),a[]=new int[n+5],p[][]=new int[n*2+5][18],group[]=new int[n*2+5],cost[][]=new int[n*2+5][18],level[]=new int[n*2+5],max[][]=new int[n+5][18],idx=n;
        List<Integer> path[]=new List[n*2+5];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            group[i*2]=i*2;
            group[i*2-1]=i*2-1;
            path[i*2]=new ArrayList<>();
            path[i*2-1]=new ArrayList<>();
            cost[i*2][0]=cost[i*2-1][0]=(int)2e9+10;
        }
        Queue<int[]> queue=new PriorityQueue<>((a1,a2)->a1[2]-a2[2]);
        for(int i=0;i<m;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            queue.add(new int[]{u,v,a[u]+a[v]});
        }
        //重构树：
        while(!queue.isEmpty()){
            int b[]=queue.poll(),p1=find(b[0],group),p2=find(b[1],group);
            if(p1!=p2){
                idx++;
                p[p1][0]=p[p2][0]=idx;
                cost[p1][0]=cost[p2][0]=b[2];
                path[idx].add(p1);
                path[idx].add(p2);
                union(idx,p1,group);
                union(idx,p2,group);
            }
        }
        //树节点分层：
        for(int i=1;i<n*2;i++){
            if(p[i][0]==0){
                findLevel(i,path,level);
            }
        }
        for(int i=1;i<18;i++){
            for(int j=1;j<n*2;j++){
                p[j][i]=p[p[j][i-1]][i-1];
                cost[j][i]=Math.max(cost[j][i-1],cost[p[j][i-1]][i-1]);
            }
        }
        for(int i=1;i<n;i++){
            max[i][0]=find(i,i+1,level,p,cost);
        }
        for(int i=1;i<18;i++){
            for(int j=1;j<n;j++){
                if(j+(1<<i)<=n){
                    max[j][i]=Math.max(max[j][i-1],max[j+(1<<(i-1))][i-1]);
                }
            }
        }
        for(int i=0;i<q;i++){
            int l=sc.nextInt(),r=sc.nextInt(),ans=0;
            for(int j=17;j>=0;j--){
                if(r-l>=(1<<j)){
                    ans=Math.max(ans,max[l][j]);
                    l+=1<<j;
                }
            }
            System.out.println(ans<=2e9?ans:-1);
        }
    }
    static int find(int a,int b,int level[],int p[][],int cost[][]){
        if(level[a]<level[b]){
            return find(b,a,level,p,cost);
        }
        int ans=0;
        for(int i=17;i>=0;i--){
            if(level[a]-level[b]>=(1<<i)){
                ans=Math.max(ans,cost[a][i]);
                a=p[a][i];
            }
        }
        for(int i=17;i>=0;i--){
            if(p[a][i]!=p[b][i]){
                ans=Math.max(ans,Math.max(cost[a][i],cost[b][i]));
                a=p[a][i];
                b=p[b][i];
            }
        }
        if(a!=b){
            ans=Math.max(ans,Math.max(cost[a][0],cost[b][0]));
        }
        return ans;
    }
    static void union(int a,int b,int group[]){
        group[find(b,group)]=find(a,group);
    }
    static int find(int a,int group[]){
        return a==group[a]?a:(group[a]=find(group[a],group));
    }
    static void findLevel(int k,List<Integer> path[],int level[]){
        for(int a:path[k]){
            level[a]=1+level[k];
            findLevel(a,path,level);
        }
    }
}

F 小柒的颜色

回滚莫队计算每个询问，时间复杂度(n^1.5+1)

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));
        StringTokenizer st=new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(st.nextToken()),nsq=(int)Math.sqrt(n),q=Integer.parseInt(st.nextToken()),a[]=new int[n+5];
        long ans[][]=new long[q][];
        List<int[]> query[]=new List[nsq+5];
        for(int i=0;i<nsq+5;i++){
            query[i]=new ArrayList<>();
        }
        st=new StringTokenizer(bf.readLine());
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<q;i++){
            st=new StringTokenizer(bf.readLine());
            int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken());
            query[l/nsq].add(new int[]{l,r,i});
        }
        for(int j=0;j<nsq+5;j++){
            List<int[]> list=query[j];
            if(list.size()==0){
                continue;
            }
            Collections.sort(list,(a1,a2)->a1[1]-a2[1]);
            //回滚莫队：
            int count[]=new int[n+5],maxNum=n+2,r=(j+1)*nsq-1;
            long sum=0,maxSum=0;
            for(int b[]:list){
                //在同一个块儿内，暴力：
                if(b[1]/nsq==j){
                    long curSum=0,curNum=n+2,curMax=0;
                    for(int i=b[0];i<=b[1];i++){
                        curSum+=(long)a[i]*count[a[i]];
                        count[a[i]]++;
                        long s=(long)a[i]*count[a[i]]*(count[a[i]]-1)/2;
                        if(s>curMax||s==curMax&&a[i]<curNum){
                            curNum=a[i];
                            curMax=s;
                        }
                    }
                    ans[b[2]]=new long[]{curSum,curNum};
                    for(int i=b[0];i<=b[1];i++){
                        count[a[i]]--;
                    }
                }
                else{
                    //先移动右端点：
                    while(r<b[1]){
                        r++;
                        sum+=(long)a[r]*count[a[r]];
                        count[a[r]]++;
                        long curSum=(long)a[r]*count[a[r]]*(count[a[r]]-1)/2;
                        if(curSum>maxSum||curSum==maxSum&&a[r]<maxNum){
                            maxNum=a[r];
                            maxSum=curSum;
                        }
                    }
                    //移动左端点：
                    long curMaxSum=maxSum,curSum=sum;
                    int curMaxNum=maxNum;
                    for(int i=(j+1)*nsq-1;i>=b[0];i--){
                        curSum+=(long)a[i]*count[a[i]];
                        count[a[i]]++;
                        long s=(long)a[i]*count[a[i]]*(count[a[i]]-1)/2;
                        if(s>curMaxSum||s==curMaxSum&&a[i]<curMaxNum){
                            curMaxNum=a[i];
                            curMaxSum=s;
                        }
                    }
                    ans[b[2]]=new long[]{curSum,curMaxNum};
                    for(int i=(j+1)*nsq-1;i>=b[0];i--){
                        count[a[i]]--;
                    }
                }
            }
        }
        for(long b[]:ans){
            bw.write(b[0]+" "+b[1]+"\n");
        }
        bw.flush();
    }
}