# # Google Kick Start 2019 Round G 题解

## # Problem A - Book Reading

### # 题解

#### # 思路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);
}

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
43

#### # 思路2 分解因数

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

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

### # 题目描述

$N$个非负整数$A_1,A_2,...A_N$，以及一个目标值$M$，请找出满足$\sum_{i=1}^N(A_i \ xor\ k)\leq M$的最大的非负整数$k$。如果不存在这样的$k$，输出-1。

### # 题解

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

$\sum_{i=0}^{50}2^i\times(ones[i]\times(1-k[i])+zeros[i]\times k[i])$

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

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

## # Problem C - Shifts

### # 题解

#### # 思路1 剪枝

1. 如果穷举到某一天时，发现即使后面所有天都给A排班，A的快乐值也不够，或者所有天都给B排班，B的快乐值也不够，那么这条分支就不用继续向下搜索了。
2. 如果穷举到某一天时，发现已经满足A和B的快乐值都不少于H，那么剩下来的$k$天一共$3^k$种情况都能满足要求。所以直接累加到总的方法数中，不再继续搜索。

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

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

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

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63