Kickstart 2022 D
这场 700 名多点，除了D的大数据点之外都过了。
A. Image Labeler
题意
给你 n 个任务，m个分类。每个任务都有一个值，将这些任务分配给这些类别。要求每个任务只能属于一个类别，且一个类别里面至少有一个任务。每个类别的值是其中所有任务的中位数。最终分数是所有类别的值的和。求这个和的最小值。
范围
1≤T≤100
1≤N≤1e4.
1≤M≤1e4.
1≤M≤N.
1≤Ai≤1e5
1
2
3
4
T
N M
A1 ... AN
...
输入
1
2
3
4
5
1
3 2
11 24 10
5 1
6 2 5 1 9
输出
1
2
Case #1: 34.5
Case #2: 5.0
思路
通过样例可以观察出。如果对于 n-1 == m的情况（也就是原题中小测试点的情况），最优解必然是让最小的两个放在一起，然后其他的各自占一个类别。
由这个思路扩展，可以得到： 从大到小排序，然后顺序先放置m-1个任务，它们每个都单独占据一个类别。其余的全都放在一个类别中。
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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int a[100005];
int main() {
int T;
cin >> T;
int c = 1;
while (T--) {
cout << "Case #" << c << ": ";
c++;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
reverse(a, a + n);
double ans = 0;
for (int i = 0; i < m; ++i) {
if (i == m - 1) {
if ((n - i) % 2 == 0) { // 剩余个数为偶数，需要算平均数
ans += (a[(i + n) / 2] + a[(i + n) / 2 - 1]) / 2.0;
} else { // 奇数
ans += a[(i + n) / 2];
}
break;
}
ans += a[i];
}
cout << fixed << setprecision(6);
cout << ans << endl;
}
return 0;
}
B. Maximum Gain
题意
给你两个任务A，B。 每个任务是一个数组，长度分别为n, m。数组每个元素是一个整数，表示子任务的值。做子任务的时候只能选择任意任务中最左侧或者最右侧的未完成的子任务。 你总共能选择K个子任务。求能做的子任务值的和的最大值。
1≤T≤100
1≤N≤6000
1≤M≤6000
1≤Ai, Bi≤1e9
1≤K≤N+M
1
2
3
4
5
6
T
N
A1 ... AN
M
B1 ... BM
K
输入
1
2
3
4
5
6
7
8
9
10
11
2
3
3 1 2
4
2 8 1 9
5
4
1 100 4 3
6
15 10 12 5 1 10
6
输出
1
2
Case #1: 24
Case #2: 148
思路
在AB两个任务中总共选K个，可见，两个任务之间是没有影响，也没有顺序关系的。不妨就认为先选A，剩下的选B中的任务。
定义问题为
dpa[i] 表示在A中选择i个子任务所得的最大值
dpb[i] 同理，表示在B中。
这样我们只需要遍历K个子任务的分配（分成两部分就是K+1种分配方式）
对于 dpa[i] 来说, 从左右取的顺序是无关的，可以看做先连续取左边，再连续取右边。因此问题可以进一步分解成， left[j](j<=i) ，也就是我们枚举从左侧连续选j个，从右侧连续选i-j个。这样求解dpa的时间复杂度就是 O(n^2) .
求解dpb同理，复杂度 O(m^2) .
然后遍历一下 K 的拆分就可以了。
代码
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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int m;
int n;
int k;
ll a[6005], b[6005];
ll suma[6005], sumb[6005];
ll dpa[3005], dpb[3005];
ll rangeSum(ll arr[], int l, int r) {
if (l > r) return 0;
return arr[r] - arr[l - 1];
}
int main() {
int T;
cin >> T;
int c = 1;
while (T--) {
cout << "Case #" << c << ": ";
c++;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
suma[i] = suma[i - 1] + a[i];
}
cin >> m;
for (int i = 1; i <= m; ++i) {
cin >> b[i];
sumb[i] = sumb[i - 1] + b[i];
}
cin >> k;
for (int i = 1; i <= min(n, k); ++i) { // A
dpa[i] = -1;
for (int j = 0; j <= i; ++j) { // left
dpa[i] = max(dpa[i], rangeSum(suma, 1, j) +
rangeSum(suma, n - (i - j) + 1, n));
}
}
for (int i = 1; i <= min(m, k); ++i) { // B
dpb[i] = -1;
for (int j = 0; j <= i; ++j) { // left
dpb[i] = max(dpb[i], rangeSum(sumb, 1, j) +
rangeSum(sumb, m - (i - j) + 1, m));
}
}
ll ans = -1;
dpa[0] = dpb[0] = 0;
for (int i = 0; i <= min(n, k); ++i) { // A
ll ansA = dpa[i];
ll ansB = 0;
if (k - i > m) {
ansB = dpb[m];
} else {
ansB = dpb[k - i];
}
ans = max(ans, ansA + ansB);
}
cout << ans << endl;
}
return 0;
}
C. Touchbar Typing
题意
给你一个整数数组S，表示要打的字符串，长度为n。给你一个整数数组K, 表示键盘， 长度为m。保证s内的元素都出现在K里过。注意：S和K中都可能有重复的元素。
打字遵循如下规则：打字不需要花时间，只有移动才花时间。开始的第一个字符是不需要时间的（就是可以瞬间移动到要打的第一个字符上）
然后移动的时间是两个字符之间的距离 |j-i| 。求打S所需的最小移动时间。
范围
1≤T≤100.
1≤Ki≤2500.
1≤Si≤2500.
1≤N≤2500.
1≤M≤2500.
1
2
3
4
5
T
N
A1 ... AN
M
B1 ... BM
输入
1
2
3
4
5
6
7
8
9
10
2
5
1 2 3 2 1
3
1 2 3
3
1 1 1
2
2 1
输出
1
2
3
Case #1: 4
Case #2: 0
思路
这个题小数据范围不大(N, M<=100)，可以记忆化搜索。也就是模拟操作，首先记录下每个字符对应的键盘的位置。然后每次都进行dfs去搜索，然后加上记忆化。就可以过前两个点了。
1
dfs(curPos,SIndex) // curPos是现在手指的位置，curSIndex是接下来要处理的S的下标
大数据点着实让我思考了很久，在比赛的最后10分钟的时候才A掉。 在写记忆化的时候注意到一个事实：dfs的状态最多只有N*M个。而在大数据点下，这个值也并不大，因此就往DP方向考虑，但是没有进展。
回顾了一下算法在大数据点超时的原因：既然状态并不多，那肯定是层和层之间的传递太慢了，需要大规模的剪枝才行。比如遇到K和S中全是a, b的情况。那么两层之间的路径就达到了N*M。因此引入了如下的思考：
如果多想一步呢？当前在pos, 下一个要处理b，下下个是c。那么a和c的关系有两种，一种是所有的c都在pos的一侧，这种情况下，只需要选择对应方向上的b即可，只有这一侧没有b，才会去选择另一侧最近的b。第二种情况是两侧都有。 对于只有一侧的情况，可以更深入的考虑，假设c只存在于一个位置posc，而在pos到posc中间有多个b，那么无论选择哪一个b，pos->b->posc 的总长度是定值。那我们就选择较近的那个。
综上所述，无论c在左侧也好，在右侧也罢，出现多个也好，只需要考虑离pos左右各最近的一个b即可。其他的b不会比这个更优。
因此每一层瞬间就只剩下了两个！！ 为了达到这个选择效果，可以先对每个键对应的位置 进行排序，然后用二分查找。
代码
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int n, m;
int c = 1;
int s[2505], k[2505];
unordered_map<int, vector<int>> mp;
pair<int, ll> cache[2505][2505];
int left(vector<int> &a, int n, int x) {
int l = 0, r = n, mid;
while (l < r) {
mid = (l + r) / 2;
if (a[mid] <= x) {
l = mid + 1;
} else {
r = mid;
}
}
return l - 1;
}
int right(vector<int> &a, int n, int x) {
int l = 0, r = n, mid;
while (l < r) {
mid = (l + r) / 2;
if (a[mid] <= x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
ll dfs(int cur, int idx) {
if (idx == n) {
return 0;
}
auto p = cache[cur][idx];
if (p.first == c) {
return p.second;
}
int target = s[idx];
vector<int> &v = mp[target];
int sz = v.size();
ll curAns = -1;
auto leftP = left(v, sz, cur);
if (leftP >= 0) {
int pos = v[leftP];
int dis = abs(cur - pos);
curAns = dis + dfs(pos, idx + 1);
}
auto rightP = right(v, sz, cur);
if (rightP < sz) {
int pos = v[rightP];
int dis = abs(cur - pos);
if (curAns == -1) {
curAns = dis + dfs(pos, idx + 1);
} else {
curAns = min(curAns, dis + dfs(pos, idx + 1));
}
}
cache[cur][idx] = make_pair(c, curAns);
return curAns;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
printf("Case #%d: ", c++);
mp.clear();
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &s[i]);
}
n = unique(s, s + n) - s;
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d", &k[i]);
mp[k[i]].push_back(i);
}
for (int i = 0; i < m; ++i) {
vector<int> &v = mp[k[i]];
sort(v.begin(), v.end());
}
int fi = s[0];
vector<int> &v = mp[fi];
int sz = v.size();
ll ans = -1;
for (int i = 0; i < sz; ++i) {
if (ans == -1) {
ans = dfs(v[i], 1);
} else {
ans = min(ans, dfs(v[i], 1));
}
}
printf("%lld\n", ans);
}
return 0;
}
D. Suspects and Witnesses
题意
n个嫌犯，m条供述，每一条格式如下：Ai 说 Bi是无辜的，且保证Ai!=Bi 已知无辜的人说的话一定是真的。嫌犯说的真假未定。 已知最多有K个犯人，求有多少人一定是无辜的。
范围
1≤T≤100.
2≤N≤105.
1≤M≤105.
1≤Ai≤N
1≤Bi≤N
Ai≠Bi
(Ai, Bi)≠(Aj, Bj)
小数据 K = 1 大数据 K <= 20
1
2
3
4
5
6
T
N M K
A1 B1
A2 B2
...
AM BM
输入
1
2
3
4
5
6
7
8
9
2
3 2 1
1 2
2 3
3 3 1
1 2
2 3
3 1
输出
1
2
Case #1: 2
Case #2: 3
思路
大数据目前还没思路，之后补题看一下
小数据的思路很简单。可以这样想，如果有个人是最终的犯人，那么所有说他无辜的人都是假话了，与最多一个犯人冲突。因此如果把数据看做是一张图的话，A->B表示A说B是无辜的。那么所有入度不为0的人一定不是犯人。而入度为0的人则无法证明。因此答案就是入度不为0的节点个数。
代码
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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
int n, m, k;
int main() {
int T;
cin >> T;
int c = 1;
while (T--) {
cout << "Case #" << c << ": ";
c++;
cin >> n >> m >> k;
vector<pii> v;
map<int, int> in, all;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
in[b]++;
}
if (k == 1) {
cout << in.size() << endl;
} else { // 大数据不会，先占个位
cout << 1 << endl;
return 0;
}
}
return 0;
}
