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

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

C 76选数

首先确认答案的上限，二进制最高位一定不高于n的最高位，再考虑这样的最大数能否构成，显然可以，只需把一些列单比特数字提取出来异或即可，时间复杂度O(1)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        System.out.println((1L<<(1+(int)(Math.log(sc.nextLong())/Math.log(2))))-1);
    }
}

D 76构造

容易想到，每个数字都是自身的二进制最低位所代表的数字的倍数，因此将m的二进制位分组后，将1-n的按照哪一组（位）的倍数分好组，找不到分组的时候直接返回-1；；组内的gcd一定就是组所代表的二进制数字，最后需要验证非空组的按位或与m相同，时间复杂度O(17n)

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(),pre=0,mask=0;
        List<Integer> list[]=new List[17];
        for(int i=0;i<17;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=1;i<=n;i++){
            boolean found=false;
            for(int j=16;j>=0;j--){
                if((m>>j&1)==1&&i%(1<<j)==0){
                    mask|=1<<j;
                    list[j].add(i);
                    found=true;
                    break;
                }
            }
            if(!found){
                System.out.println(-1);
                return;
            }
        }
        if(mask!=m){
            System.out.println(-1);
        }
        else{
            for(List<Integer> cur:list){
                for(int a:cur){
                    System.out.print(a+" ");
                }
            }
            System.out.println("\n"+Integer.bitCount(mask));
            for(List<Integer> cur:list){
                if(cur.size()!=0){
                    System.out.println(pre+1+" "+(pre+cur.size()));
                    pre+=cur.size();
                }
            }
        }
    }
}

E qcjj寄快递

由于每组距离计算是独立的，因袭可以分别计算，令f(x)=2(x+2^(-x)),则f'(x)=2(1-2^(-x)ln(2))，求出导函数的零点带入原函数即可，但需要注意，零点若求出位负数，需要修改为0，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double ans=0,p[]=null;
        for(int i=0;i<n;i++){
            double cur[]=new double[]{sc.nextDouble(),sc.nextDouble()};
            if(i>0){
                ans+=find(cur,p);
            }
            p=cur;
        }
        System.out.println(ans);
    }
    static double find(double p1[],double p2[]){
        double d=Math.sqrt(Math.pow(p1[0]-p2[0],2)+Math.pow(p1[1]-p2[1],2)),x=Math.max(0,Math.log(d*Math.log(2))/Math.log(2));
        return (x+d*Math.pow(2,-x))*2;
    }
}

F 幂中幂plus

容易推测，c数列一定存在一个周期不大于mod的循环节，找到即可，时间复杂度O(q+modlog(mod)+log(c0))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long base=sc.nextLong(),c0=sc.nextLong(),mod=sc.nextLong(),pre[]=new long[(int)1e6+5];
        int idx[]=new int[(int)1e6+5],l=-1,r=-1;
        base%=mod;
        for(int i=1;;i++){
            c0=pow(base,c0,mod);
            pre[i]=pre[i-1]+c0;
            if(idx[(int)c0]==0){
                idx[(int)c0]=i;
            }
            else{
                r=i;
                l=idx[(int)c0];
                break;
            }
        }
        for(int i=sc.nextInt();i!=0;i--){
            long x=sc.nextLong();
            System.out.println(x<=l?pre[(int)x]%mod:(pre[l]+(x-l)/(r-l)%mod*(pre[r]-pre[l])+pre[l+(int)((x-l)%(r-l))]-pre[l])%mod);
        }
    }
    static long pow(long a,long b,long mod){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}