2018网易在线笔试题

第一题

解决思路:分类讨论
当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 cnt


def 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 s


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