20230908 滴滴AK

先mark一下，到点了更新

====分割线====

t1. 糖果工厂可以生产n种不同的糖果，假设这些糖果的编号分别为1到n，每一天工厂可以生产Ci个编号为i的糖果。今天工厂接到了一个订单，需求是a包糖果，且每包糖果必须是同一种类的，每包数量不能少于b个。假设糖果工厂在无存货的情况下，至少需要多少天才能完成这个订单?

package didi;

import java.math.BigInteger;
import java.util.Scanner;

//简单二分，但是要用BigInteger，不然会溢出
//int 只能过82%
//long 只能过91%
public class t1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long a = scanner.nextInt(), b = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        BigInteger l = new BigInteger("0"), r = new BigInteger(String.valueOf(Long.MAX_VALUE));
        while (l.compareTo(r) < 0) {
            BigInteger mid = l.add(r.subtract(l).divide(new BigInteger("2")));
            BigInteger count = check(nums, b, mid);
            if (count.compareTo(new BigInteger(String.valueOf(a))) >= 0) {
                r = mid;
            } else {
                l = mid.add(new BigInteger("1"));
            }
        }
        System.out.println(l);
    }

    static BigInteger check(int[] nums, long b, BigInteger mid) {
        BigInteger count = new BigInteger("0");
        for (int num : nums) {
            count = count.add(new BigInteger(String.valueOf(num)).multiply(mid).divide(new BigInteger(String.valueOf(b))));
        }
        return count;
    }
}

t2.现在有n个由大写英文字符组成的字符串，且这些字符串不会互相包含，也不会相等。现在想知道有哪些字符串满足如下条件。设满足条件的字符串为S，存在其他的两个字符串拼接在一起后，能通过去除一个非空前缀和一个非空后缀变为字符串S。这两个用于拼接的字符串可以是同一个，也可以为S。

package didi;

import java.util.*;

// 将一个字符串分成两部分，分别存到lSet和rSet中
// 然后遍历所有字符串，如果lSet中包含r，rSet中包含l，则这个字符串满足条件
public class t2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HashSet<String> lSet = new HashSet<>();
        HashSet<String> rSet = new HashSet<>();
        String[] arr = new String[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = scanner.next();
            for (int j = 0; j < arr[i].length() - 1; ++j) {
                String l = arr[i].substring(0, j + 1);
                String r = arr[i].substring(j + 1);
                lSet.add(l);
                rSet.add(r);
            }
        }
        LinkedList<String> res = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < arr[i].length() - 1; ++j) {
                String l = arr[i].substring(0, j + 1);
                String r = arr[i].substring(j + 1);
                if (lSet.contains(r) && rSet.contains(l)) {
                    res.add(arr[i]);
                    break;
                }
            }
        }
        System.out.println(res.size());
        String[] resArr = new String[res.size()];
        for (int i = 0; i < res.size(); ++i) {
            resArr[i] = res.get(i);
        }
        Arrays.sort(resArr);
        for (String s : resArr) {
            System.out.println(s);
        }
    }
}