题解 | 牛客周赛 Round 76 CDEF Java题解

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

C 小红的gcd

可以证明，最终状态一定是数组的数字全部相等，因为假设有俩数字不同，必定可以继续取它俩gcd变得更小，因此最小值一定是全部变成数组的gcd，时间复杂度O(nlogC)，其中C==1e9

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int ans=0,n=sc.nextInt();
        for(int i=0;i<n;i++){
            ans=gcd(ans,sc.nextInt());
        }
        System.out.println((long)n*ans);
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

D 奇偶调整

略

E 幂次进近

由于指数爆炸，因此k很大的时候，答案可以定为1，当k较小（65以内）时，可二分答案（注意不能double直接计算，相对精度不够）,找到k次方正好不小于和正好不大于n的两数，分别比较，时间复杂度O(tClogn)，其中C==65

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++){
            long n=sc.nextLong(),k=sc.nextLong();
            if(k>=65){
                System.out.println("1");
            }
            else{
                long l=1,r=n;
                while(l<r){
                    long mid=(l+r)>>1;
                    if(pow(mid,k)<=n){
                        l=mid;
                    }
                    else{
                        r=mid-1;
                    }
                    if(l==r-1){
                        if(pow(r,k)<=n){
                            l=r;
                        }
                        break;
                    }
                }
                System.out.println(n*2<=pow(l,k)+pow(l+1,k)?l:l+1);
            }
        }
    }
    static long pow(long a,long b){
        long ans=1;
        for(int i=0;i<b;i++){
            if(3e18/ans<a){
                return (long)3e18;
            }
            ans*=a;
        }
        return ans;
    }
}

F 同位序列

把数字按照比特数分组，组内去重排序，依次找到最长序列即可，时间复杂度O(nlogn(logC)^2)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        TreeSet<Integer> set[]=new TreeSet[33];
        for(int i=0;i<33;i++){
            set[i]=new TreeSet<>();
        }
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            set[Integer.bitCount(a)].add(a);
        }
        List<Integer> ans=new ArrayList<>();
        for(TreeSet<Integer> s:set){
            int pre=-1;
            List<Integer> list=new ArrayList<>();
            for(int a:s){
                if(pre==-1||a==g(pre)){
                    list.add(a);
                }
                else{
                    if(ans.size()<list.size()){
                        ans=list;
                    }
                    list=new ArrayList<>();
                    list.add(a);
                }
                pre=a;
            }
            if(ans.size()<list.size()){
                ans=list;
            }
        }
        System.out.println(ans.size());
        for(int a:ans){
            System.out.print(a+" ");
        }
    }
    static int g(int a){
        int bit[]=new int[30],ans=0;
        for(int i=0;i<30;i++){
            bit[29-i]=a>>i&1;
        }
        for(int i=28;i>=0;i--){
            if(bit[i]<bit[i+1]){
                bit[i]=1;
                bit[i+1]=0;
                Arrays.sort(bit,i+2,30);
                break;
            }
        }
        for(int b:bit){
            ans=ans<<1|b;
        }
        return ans;
    }
}