第一题
解决思路:分类讨论
当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);
}
}
}