题解 | 牛客小白月赛125

A 幂运算

构造 即可。

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
		System.out.println(sc.nextInt()+" "+"1");
	}
}

B 琪露诺的 K 维偏序

二分查找小于x的数量即可。

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []a = new int [n+2];
        for(int i=1;i<=n;i++) {
            a[i] = sc.nextInt();
        }
        while(m-->0) {
            int k = sc.nextInt(),x = sc.nextInt();
            int l=1,r=n;
            int p = 0;
            while(l<=r) {
                int mid = l+r>>1;
                if(a[mid] < x) {
                    p = mid;
                    l = mid+1;
                }
                else r = mid-1;
            }
            System.out.println(p>=k ? "Yes" : "No");
        }
	}
}

C 合成大企鹅

排序，因为任意选择，贪心选最小的两个合并即可。
看成相邻选写区间dp的有无

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        List<Double> a = new ArrayList<>();
        for(int i=1;i<=n;i++) {
            a.add((double)sc.nextInt());
        }
        while(a.size()>1) {
            Collections.sort(a);
            List<Double>b = new ArrayList<>();
            b.add(Math.sqrt(a.get(0)*a.get(1)));
            for(int i=2;i<a.size();i++) b.add(a.get(i));
            a = b;
        }
        System.out.println(a.get(0));
	}
}

D/E ⑨运算(Hard Version)

构造，分类讨论。

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
        while(t-->0){
            long x = sc.nextLong();
            boolean f = true;
            long m = x;
            while(m>0) {
                if(m%10 != 9) f= false;
                m/=10;
            }
            if(f) {
                System.out.println(0);continue;
            }
            long []a = new long[20];
            for(int i=1;i<=18;i++) {
                a[i] = a[i-1]*10+1;
            }
            long ans = (long)1e18;
            for(int i=1;i<=17;i++) {
                if(a[i] < x) continue;
                long u = (a[i]-x)/9, v = a[i]-x-9*u;
                ans = Math.min(ans, u+1+v);
            }
            for(int i=1;i<=17;i++) {
                if(a[i]*9 < x) continue;
                if(x%9 == 0) {
                    ans = Math.min(ans, (a[i]*9-x)/9);
                    break;
                }
            }
            System.out.println(ans);
        }
	}
}

F 琪露诺的排列构造

构造，分类讨论。

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
			if(n%2 == 1) {
				if(n == 1) {
					System.out.println(-1);
					continue;
				}
				System.out.print(""+n);
				for(int i=1;i<n;i++) System.out.print(" "+i);
				System.out.println("");
			}
			else {
				if(n == 2) System.out.println(-1);
				else if(n == 4) {
					System.out.println("2 4 1 3");
				}
				else {
					System.out.print("3 1 2 "+n);
					for(int i=4;i<n;i++) System.out.print(" "+i);
					System.out.println("");
				}
			}
            System.out.flush();
        }
	}
}

F 琪露诺的排列构造

打表，找规律。
容易写出fun(r) - fun(l-1)的方式。

import java.util.*;

import java.io.*;
import java.math.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) throws IOException {
		int t = 1;
        t=sc.nextInt();
        while (t-- > 0)
            solve();
        System.out.flush();
	}
    
    static long fun(int x,int p,int q) {
        long res = 0;
        long k = x/q;
        res = k * 1l*(1+p-1)*(p-1)/2;
        if(k*q<x) res += 1l*(1+Math.min(x-k*q, p-1))*Math.min(x-k*q, p-1)/2;
        return res;
    }
		
    static void solve() throws IOException {
        int l = sc.nextInt(),r = sc.nextInt(),p = sc.nextInt(),q = sc.nextInt();
        System.out.println(fun(r,p,q) - fun(l-1,p,q));
    }
}