题解 | 牛客小白月赛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)

构造，分类讨论。
因为有×9操作，易得一定有解。

1. 判断是否已经是好数字；
2. 通过 +9 达成 好数字；
3. 设 ×9 前 +9 a次，×9 后 +9 b次，有 ，除 9 得 ，要 最小，显然最优解为 。枚举 ，解得 再求 即可。

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 琪露诺的排列构造

构造，分类讨论。

1. 奇数：显然1无解。不为1，有比较容易的构造：。第1项为偶数，2至n项依次递增，符合题意。
2. 偶数：显然2无解。大于4的情况，可拆分成两个奇数块，每个块用奇数情况构造即可；n=4的情况手造或枚举均可。

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();
        }
	}
}

G 琪露诺的连续取模求和

打表，找规律。
设 为对区间 内每一个整数，依次对从 到 内所有整数取模后求和。容易写出 的方式。
手玩几个可知，对于任意 ，有以下循环节：

求出几个循环节以及边界即可。

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));
    }
}