题解 | 牛客小白月赛103 CDEF题解

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

C 冰冰的异或

通过打表1-100时的答案，可以找到规律：答案即为不小于n的最小2的整数次幂，其中n<=2的情况特判一，时间复杂度O(T)

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();
            System.out.println(n<=2?"1":1L<<(int)(Math.log(n-1)/Math.log(2)+1));
        }
    }
}

D 冰冰的分界线

联立所有不同的两点，可以得到直线方程，保证系数是最简形式，且第一个非0数是正数，再用字符串的形式去重存储，时间复杂度O(Tn^2log(xy))

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(),p[][]=new int[n][2];
            for(int j=0;j<2;j++){
                for(int k=0;k<n;k++){
                    p[k][j]=sc.nextInt();
                }
            }
            Set<String> set=new HashSet<>();
            for(int j=0;j<n;j++){
                for(int k=j+1;k<n;k++){
                    set.add(find(p[j],p[k]));
                }
            }
            System.out.println(set.size());
        }
    }
    static String find(int pos1[],int pos2[]){
        long a=pos1[0]-pos2[0],b=pos1[1]-pos2[1],c=(long)pos1[0]*pos1[0]+(long)pos1[1]*pos1[1]-(long)pos2[0]*pos2[0]-(long)pos2[1]*pos2[1],gcd=gcd(Math.abs(a),gcd(Math.abs(b),Math.abs(c)));
        a/=gcd;
        b/=gcd;
        c/=gcd;
        if(a<0||a==0&&(b<0||b==0&&c<0)){
            a=-a;
            b=-b;
            c=-c;
        }
        return a+" "+b+" "+c;
    }
    static long gcd(long a,long b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

E 冰冰的 GCD

分别预处理求得f和g，首先处理f也就是b，需要质数筛存储每个数字的质因子，然后倒序处理b得到f，对于g，类似筛的方法，判断倍数的存在性，时间复杂度O(nlogn+m)，由于本题输入输出总量达到了4e5，因此需要快读快写

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]),a[]=new int[n+5],b[]=new int[n+5],c[]=new int[n+5],f[]=new int[n+5],g[]=new int[n+5],last[]=new int[n+5];
        List<Integer> primeFac[]=new List[n+5];
        arr=bf.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(arr[i-1]);
            primeFac[i]=new ArrayList<>();
        }
        arr=bf.readLine().split(" ");
        for(int i=1;i<=n;i++){
            b[i]=Integer.parseInt(arr[i-1]);
            if(i>1&&primeFac[i].size()==0){
                for(int j=i;j<=n;j+=i){
                    primeFac[j].add(i);
                }
            }
        }
        arr=bf.readLine().split(" ");
        for(int i=n;i>0;i--){
            c[Integer.parseInt(arr[n-i])]=n+1-i;
            int idx=n+1;
            for(int p:primeFac[b[i]]){
                if(last[p]!=0){
                    idx=Math.min(idx,last[p]);
                }
                last[p]=i;
            }
            f[i]=idx>n?b[i]:gcd(b[i],b[idx]);
        }
        boolean has[]=new boolean[n+5];
        for(int i=n;i>0;i--){
            has[a[i]]=true;
            for(int j=c[i];j<=n;j+=c[i]){
                if(has[j]){
                    g[c[i]]++;
                }
            }
        }
        for(int i=0;i<m;i++){
            bw.write(g[f[Integer.parseInt(bf.readLine())]]+"\n");
        }
        bw.flush();
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

F 冰冰的列车

略，目前假题