QB Day1

发表于

今天上午考了一次试，有三道题，整理一下。

本次试题链接

第一题大意为给你 $n$ 个数，你需要求出每对数相异或的和(此处需要注意的是 $(a, b)$ 和 $(b, a)$ 为同一对)。

对于这道题，我们可以把每个数拆分成几个二进制位，对于第 $i$ 位，统计所有数的第 $i$ 位的值进行求和，放进一个数组 $a$ 中。即

$$ a[i] = \sum\limits_{j = 1}^n[num[j] & (1<<i)>>i] $$

这样我们就可以快速求某个数 $x$ 异或所有数的和，记为 $s(x)$ ，即：

$$ s(x) = \sum_{i = 0}^{\lfloor\log_2x\rfloor} t[(x >> i) & 1, i] $$

$t(x, i)$ 的定义为若 $x = 1$ 则为 $a[i] << i$，否则为 $(n - a[i]) << i$。

时间复杂度 $O(nlogn)$ ，强烈谴责此类卡常数行为！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>
#define MAXN 1000001
#define DEBUG(x) std::cerr << #x << " = " << (x) << '\n'

int a[21], num[MAXN];

inline int GetBit(int x, int i) {
	return (1LL * x & (1 << i)) >> i;
}

inline int read() {
	int res = 0; char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch <= '9' && ch >= '0') res = res * 10 + ch - '0', ch = getchar();
	return res;
}

int main(int argc, char *argv[]) {
	freopen("alien.in", "r", stdin);
	freopen("alien.out", "w", stdout);
	
	int n;
	long long ans = 0;
	
	n = read();
	for(int i = 0; i < n; i++){
		num[i] = read();
		for(int j = 0; j < 21; j++) 
			a[j] += GetBit(num[i], j);
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 21; j++) {
			if(GetBit(num[i], j)) ans = ans + (1LL * (n - a[j]) << j);
			else ans = ans + (1LL * a[j] << j);
		}
	}
	
	printf("%lld", ans / 2);
	return 0;
}

第二道题题目叙述的比较清楚了，我们一个很显然的做法就是用 map 差分，即我们考虑斜率变化的点，差分求即可。

对于这个题目我们需要写一个分数结构体，否则 double 精度不及格。

偷偷谴责一下。。

1
此处应有代码

对于第三题感觉特别神，对于此题我们很容易想到一个时间复杂度为 $O(a * n^2)$ 的方程，发现过不了，但 DP 的值只是在 $n$ 以内，所以我们把求的东西和 $a$ 的那一维交换，即可在 $O(n^3)$ 的时间复杂度内解决这个问题。

不过此题细节问题较多，代码较复杂，暂时没有心情打，先缓缓吧！

1
此处应有代码