# Google Kick Start 2019 Round G 题解
# Problem A - Book Reading
# 题目描述
有一本页的书,其中缺了页,分别为。 现在有个读者,其中的第个读者只会阅读页码数为整数倍的那些页(缺失的页除外)。 请统计所有读者阅读的页数总和。
数据范围: 。
# 题解
我们需要的实际上是一个数组cnt[N+1]
,用于记录从1到N每个数字的整数倍中,缺页的数量。求得cnt
后,只需要统计即可。
# 思路1 穷举倍数
用一个哈希表torn[N+1]
记录第页是否损坏,然后我们从1开始,遍历它不超过的所有倍数,记录下损坏的总页数。
时间复杂度为
参考代码
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
int n, m, q;
cin >> n >> m >> q;
vector<int> cnt(n + 1), torn(n + 1);
for (int i = 0; i < m; ++i) {
int p;
scanf("%d", &p);
torn[p]++;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n / i; ++j)
if (torn[i * j])
cnt[i]++;
ll ans = 0;
for (int i = 0; i < q; ++i) {
int r;
scanf("%d", &r);
ans += n / r - cnt[r];
}
cout << "Case #" << case_num << ": " << ans << endl;
}
};
int main() {
Solution solution;
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
solution.solve(i);
}
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
43
# 思路2 分解因数
对于每一个缺失的页码,将其分解质因数,然后搜索得到其所有的因子,给对应的cnt
加上1。(这是我比赛时用的方法,比前一种方法的工作量要大上不少,也导致了第一题用时比较久,40分钟才过。)
参考代码
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> primes{2, 3, 5, 7};
class Solution {
void process(int p, vector<ll> &cnt) {
unordered_map<int, int> factor;
int i = 0;
int p0 = p;
while (p > 1) {
while (p % primes[i] == 0) {
factor[primes[i]]++;
p /= primes[i];
}
i++;
if (primes[i] * primes[i] > p) {
if (p > 1)
factor[p]++;
break;
}
}
vector<int> nums{1};
for (const auto &f : factor) {
int n = nums.size();
for (int j = 0; j < n; ++j) {
int m = nums[j];
for (int k = 1; k <= f.second; ++k) {
m *= f.first;
nums.emplace_back(m);
}
}
}
for (int num : nums) {
cnt[num] += 1;
}
}
public:
void solve(int case_num) {
int n, m, q;
cin >> n >> m >> q;
vector<ll> cnt(n + 1);
for (int i = 0; i < m; ++i) {
int p;
scanf("%d", &p);
process(p, cnt);
}
ll ans = 0;
for (int i = 0; i < q; ++i) {
int r;
scanf("%d", &r);
ans += n / r - cnt[r];
}
cout << "Case #" << case_num << ": " << ans << endl;
}
};
int main() {
Solution solution;
int t;
cin >> t;
for (int i = 4; i < 501; ++i) {
int n = 2 * i + 1;
int j = 0;
bool prime = true;
while (primes[j] * primes[j] <= n) {
if (n % primes[j] == 0) {
prime = false;
break;
}
j++;
}
if (prime)
primes.emplace_back(n);
}
for (int i = 1; i <= t; ++i)
solution.solve(i);
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# Problem B - The Equation
# 题目描述
有个非负整数,以及一个目标值,请找出满足的最大的非负整数。如果不存在这样的,输出-1。
数据范围:。
# 题解
这一题的小数据集数据规模非常小,数字上限只到100,所以暴力穷举就可以通过。但这一做法显然对于大数据集是不奏效的。
所有与异或相关的题目,必然要考虑二进制有关的性质。我们首先考虑和式,不妨看一个例子:
数字 | 二进制表示 |
---|---|
A1=15 | 1 1 1 1 |
A2=8 | 1 0 0 1 |
A3=6 | 0 1 1 0 |
A4=3 | 0 0 1 1 |
1的个数 | 2 2 3 3 |
0的个数 | 2 2 1 1 |
----- | ------- |
k=7 | 0 1 1 1 |
在计算异或和的时候,我们原本是计算与每一个的异或值,然后求和。但实际上,通过观察,可以发现,异或计算的每一位是独立的,也即,我们可以计算的每一位与所有这一位的异或值,最后对所有的结果求和。
这启发我们用两个数组ones[64]
和zeros[64]
统计所有二进制表示中每一位上1和0的数量。然后就可以把刚才的和式重写为:
其中已经写成二进制形式。这里上限取50,是因为,所以最终的结果不会超过。
写成这样的形式之后,我们不难找到一条贪心策略。我们从二进制最高位开始,如果这一位上设为1后,可以异或和满足不超过的条件,我们就把这一位设为1,因为这样得到的数一定比把这一位设为0得到的数大。
我们如何判断能不能满足条件呢?对于第位来说,它产生的和是有最小值的,这个最小值就是。所以我们可以预先计算出从第0位到第50位的最小值,并求出累积和min_val[64]
。
得到这一累积和后,我们就可以很容易地判断某一位上取1之后,后面的位置是否存在一种取法,使得总异或和不超过。只要这一条件能够满足,我们就取1。否则检查取0时能否满足,如果能满足,就取0。如果取0也不行,说明无解。
参考代码
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
ll n, m;
cin >> n >> m;
vector<ll> a(n), ones(64), zeros(64);
for (int i = 0; i < n; ++i) {
ll d;
cin >> d;
bitset<64> bs(d);
for (int j = 0; j < 64; ++j) {
if (bs[j])
ones[j]++;
else
zeros[j]++;
}
}
vector<ll> min_val(64);
ll last = 0;
for (int i = 0; i <= 50; ++i) {
ll num = (1ll << i);
last += (ll)min(ones[i], zeros[i]) * num;
min_val[i] = last;
}
ll sum = 0;
bitset<64> k(0);
for (int i = 50; i >= 0; --i) {
ll num = (1ll << i);
ll one = num * zeros[i];
ll zero = num * ones[i];
if (sum + one + (i > 0 ? min_val[i - 1] : 0) <= m) {
k.set(i);
sum += one;
} else if (sum + zero + (i > 0 ? min_val[i - 1] : 0) <= m) {
sum += zero;
} else {
cout << "Case #" << case_num << ": " << -1 << endl;
return;
}
}
ll ans = k.to_ullong();
cout << "Case #" << case_num << ": " << ans << endl;
}
};
int main() {
Solution solution;
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
solution.solve(i);
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# Problem C - Shifts
# 题目描述
有A和B两个保安,他们要排一个天的值班表。每一天至少要有一个人值班,也可以两个人都值班。A第天值班的快乐值为,B第天值班的快乐值为。求出一共有多少种排法,可以使得A和B的快乐值总和都不少于。
数据范围:
# 题解
这题有一个很容易看出来的穷举方法。因为要求每一天至少有一个人值班,所以每一天实际上有三种情况:A值班,B值班,或者A、B都值班。那么我们就可以穷举每一天的情况,然后检查是否满足条件。这样的时间复杂度是,对于小数据集没有问题,但大数据集,而约等于,显然会超时。
怎么办?
# 思路1 剪枝
剪枝是搜索类问题中的常用策略。这一题可以怎么剪枝呢?
- 如果穷举到某一天时,发现即使后面所有天都给A排班,A的快乐值也不够,或者所有天都给B排班,B的快乐值也不够,那么这条分支就不用继续向下搜索了。
- 如果穷举到某一天时,发现已经满足A和B的快乐值都不少于H,那么剩下来的天一共种情况都能满足要求。所以直接累加到总的方法数中,不再继续搜索。
由于本题数据比较弱,使用这两个剪枝条件就可以通过了。
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> three;
class Solution {
ll ans, n, h;
vector<ll> ca, cb;
void dfs(vector<ll> &a, vector<ll> &b, ll asum, ll bsum, int n) {
if (n == 0) {
if (asum >= h && bsum >= h)
ans++;
return;
}
for (int i = 1; i <= 3; ++i) {
ll na = asum, nb = bsum;
if (i & 1)
na += a[n - 1];
if (i & 2)
nb += b[n - 1];
if (ca[n - 1] + na < h || cb[n - 1] + nb < h)
continue;
if (na >= h && nb >= h) {
ans += three[n - 1];
continue;
}
dfs(a, b, na, nb, n - 1);
}
}
public:
void solve(int case_num) {
cin >> n >> h;
vector<ll> a(n), b(n);
ca = vector<ll>(n + 1);
cb = vector<ll>(n + 1);
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
ca[i + 1] = ca[i] + a[i];
}
for (int i = 0; i < n; ++i) {
scanf("%lld", &b[i]);
cb[i + 1] = cb[i] + b[i];
}
if (ca[n] < h || cb[n] < h) {
cout << "Case #" << case_num << ": " << 0 << endl;
return;
}
ans = 0;
dfs(a, b, 0, 0, n);
cout << "Case #" << case_num << ": " << ans << endl;
}
};
int main() {
Solution solution;
ll n = 1;
for (int i = 0; i < 21; ++i) {
three.emplace_back(n);
n *= 3l;
}
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
solution.solve(i);
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# 思路2 状压DP
朴素穷举的最大问题是底数是3,如果我们能把底数降到2,就是一个可以处理的数据规模了。
很容易想到把A和B分开处理。计算A能够满足条件的排法,再计算B能够满足条件的排法。问题是,如何去掉不合法的情况,也即存在没有人站岗的情况的排法?
我们用一个位的二进制数state
表示A每天的站岗情况,1表示A这天站岗,0表示A这天不站岗。我们先假设A、B不同时站岗。那么A不站岗的时候,B就要站岗。我们可以计算出每一个state
对应的B得到的快乐值,如果不少于,就记为f[state]=1
。
接下来,我们需要派生出包含A、B都站岗的情形。对于一个已经满足B的state
,我们保持B的状态不变,然后将其中的0替换为1,就可以得到所有满足B的快乐值的(A,B)
状态组。这样可以保证每天至少有一个人站岗。
比如说,如过state
是1001
,且满足B的快乐值不少于,那么就可以从1001
这个state
,得到了(1001, 1001)
、(1101, 1001)
、(1011, 1001)
、(1111, 1001)
这几个状态。第二个数,实际上就是B的排班表,不过0和1正好是反过来的,也即0站岗,1不站岗。
为了不重复不遗漏,在派生过程中,我们需要一位一位进行(可以参考代码中这部分内外循环的顺序)。
这样,我们就得到了所有满足B的快乐值不小于的方法,然后,我们再检查是否满足A的快乐值不小于即可。
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class Solution {
public:
void solve(int case_num) {
ll n, h;
cin >> n >> h;
ll states = (1 << n);
vector<ll> a(n), b(n), f(states);
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 0; i < n; ++i) {
scanf("%lld", &b[i]);
}
// 检查B的快乐值是否被满足。
for (int i = 0; i < states; ++i) {
ll sum = 0;
for (int j = 0; j < n; ++j)
if (!(i & (1 << j)))
sum += b[j];
if (sum >= h)
f[i]++;
}
// 派生B的状态。
// 注意这里循环的顺序,要把位的循环放在外层,才能保证不重复不遗漏。
for (int j = 0; j < n; ++j)
for (int i = 0; i < states; ++i)
if (i & (1 << j))
f[i] += f[i ^ (1 << j)];
// 检查A的快乐值是否被满足。
ll ans = 0;
for (int i = 0; i < states; ++i) {
ll sum = 0;
for (int j = 0; j < n; ++j)
if (i & (1 << j))
sum += a[j];
if (sum >= h)
ans += f[i];
}
cout << "Case #" << case_num << ": " << ans << endl;
}
};
int main() {
Solution solution;
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
solution.solve(i);
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63