第一题

解决思路:分类讨论

当k==0的时候,有n*n对答案

当k!=0的时候,设x%y=z,z>=k.分类讨论:当x<y的时候,当x>y的时候

def simple(n, k):    cnt = 0    for i in range(1, n + 1):        for j in range(1, n + 1):            if i % j >= k:                cnt += 1    return cntdef better(n, k):    if k == 0:        return n * n    s = 0    for i in range(k, n + 1):        s += n - i    for i in range(k + 1, n):        group_count = n // i        s += (group_count - 1) * (i - k)        s += max(0, n % i - k + 1)    return sdef test():    import random    n = random.randint(3, 100)    k = random.randint(0, n)    return simple(n, k) == better(n, k)for _ in range(1000):    ans = test()    if not ans:        exit(-1)

第二题

解决思路:如果暴力枚举,$2^{30}$显然太大了.如果是$2^15$那该多好哇!那样我就只需要开辟一个大数组,从0,一直循环到$2^{15}-1$就可以了.

此题的正确思路就是:分治,创建两个大数组a[65536],b[65536],分别表示前半部分物品选择情况和后半部分选择情况,a[i]表示决策i(用i的二进制表示是否选择某个物品)的体积总和.接下来,对于每一个a[i],寻找b中小于v-a[i]的决策.此步可以通过排序+二分搜索极好地优化.

于是余有叹焉:

这道题的分治真是令人大开眼界,仔细回忆一下,我们过去学过的一切分治算法,无一不是跟递归紧密联系起来的.似乎解决问题一旦分治就要以递归的方式分治到底.

而实际上,这却是错觉.

程序设计的目的在于在有限的时间和空间内实现某个目的,如果分治一次足以解决任务,那就够了.在这道题中,只能够分治一次,而无法做到多次分治.因为既然分治,必然涉及到合并分治结果.而多次分治就会造成合并困难.

import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.Arrays;import java.util.Scanner;public class Main {static long[] build(int[] a, int beg, int end) {    int n = end - beg;    long ans[] = new long[1 << n];    for (int i = 0; i < ans.length; i++) {        long s = 0;        for (int j = 0; j < n; j++) {            if ((i & (1 << j)) != 0) {                s += a[beg + j];            }        }        ans[i] = s;    }    return ans;}static int ceil(long[] ar, long x) {    int l = 0, r = ar.length;    while (l + 1 < r) {        int m = (l + r) >> 1;        if (ar[m] > x) {            r = m;        } else if (ar[m] < x) {            l = m;        } else {            l = m;        }    }    return r;}static int merge(long[] first, long[] second, int v) {    int s = 0;    for (int i = 0; i < first.length; i++) {        if (first[i] > v) break;        else {            s += ceil(second, v - first[i]);        }    }    return s;}static int solve(int[] a, int v) {    Arrays.sort(a);    long[] first = build(a, 0, a.length / 2);    long[] second = build(a, a.length / 2, a.length);    Arrays.sort(first);    Arrays.sort(second);    return merge(first, second, v);}public static void main(String[] args) throws FileNotFoundException {//    Scanner cin = new Scanner(System.in);    Scanner cin = new Scanner(new FileInputStream("in.txt"));    int n = cin.nextInt();    int v = cin.nextInt();    int[] a = new int[n];    for (int i = 0; i < n; i++) a[i] = cin.nextInt();    cin.close();    if (n == 1) {        System.out.println("1");    } else {        int ans = solve(a, v);        System.out.println(ans);    }}}