题解 | 牛客周赛 Round 49 DEF Java题解

DEF Java

D 嘤嘤不想求异或喵

不妨先求出1到l-1的异或和再求出1到r的异或和，二者再异或就是lr异或和，这里有需要计算每一个比特位的数量，或者更具体的，是奇数还是偶数，每个比特总是呈现周期出现的，1<<i这个比特会每隔1<<(i+1)出现1<<i次，而且是在周期后半部分出现，时间复杂度O(TC)，其中C==62

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 t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            String arr[]=bf.readLine().split(" ");
            bw.write((find(Long.parseLong(arr[0])-1)^find(Long.parseLong(arr[1])))+"\n");
        }
        bw.flush();
    }
    static long find(long a){
        long ans=0;
        for(int i=0;i<62;i++){
            ans|=(a/(1L<<(i+1))*(1L<<i)+Math.max(0,1+a%(1L<<(i+1))-(1L<<i)))%2*(1L<<i);
        }
        return ans;
    }
}

E 嘤嘤不想解方程喵

直接把二次方程带入到一次方程中，整理系数后分类讨论，注意用double，时间复杂度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++){
            double a1=sc.nextInt(),b1=sc.nextInt(),c1=sc.nextInt(),a2=sc.nextInt(),b2=sc.nextInt(),c2=sc.nextInt();
            System.out.println(find(a1*b2,a2+b1*b2,b2*c1+c2));
        }
    }
    static String find(double a,double b,double c){
        return a==0?(b==0?(c==0?"INF":"0"):"1"):b*b-a*c*4==0?"1":b*b-a*c*4>0?"2":"0";
    }
}

F 嘤嘤不想找最小喵

参考资料

运用哈希，本代码时间复杂度为O(nlogn)

import java.util.*;
public class Main{
    static long base=(int)2e9+3,mod=(int)2e9+9;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long hash[]=new long[n+1];
        for(int i=1;i<=n;i++){
            hash[i]=(hash[i-1]*base+sc.nextInt()+mod)%mod;
        }
        for(int i=1;;i++){
            if((find(hash,0,n-i*2)+find(hash,i*2,n))%mod==find(hash,i,n-i)*2%mod){
                System.out.println(i);
                break;
            }
        }
    }
    static long find(long hash[],int l,int r){
        return (hash[r]+mod-hash[l]*pow(base,r-l)%mod)%mod;
    }
    static long pow(long a,int b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}