唉唉，神秘暑假；
唉唉，神秘 VP；
补题链接
A. 项目管理
Mid
给定 $n$ 个员工，每个员工的级别为 $a_i$，项目中至多只能有 $b_i$ 个人级别大于 $a_i$。最大化项目的参与人数。
赛时考虑二分，但是 check 函数没搓出来。听说 神·SUNNY 暴力过了，很是震惊。（是数据范围太弱了吗）
我们比较容易考虑到的是我们可以先按照 $a_i$ 从小到大排序，然后 $a_i$ 相同的就从大到小排序。因为限制的是级别大于本级的人数，因此我们尽量选级别小的；同样小级别的，我们选容忍度高的。
我们考虑二分答案：首先，显然有存在一个分界点 $p$ 使得 $\text{pred}$（即我们的check函数）在 $[0,p)$ 上可行而在 $[p,n)$ 上不可行。
采用这种描述方式是因为这样可以直接使用 std::partition_point(first, last, pred) 而不是手搓二分。
其作用就是使用二分法返回在区间 [first, last) 中第一个不满足谓词 pred 的元素。
因为考虑到问题是具有单调性的，显然有 $x$ 越大越不可行，因此我们二分思路是正确的。
然后我们在 check 函数中选 $x$ 个人，按照级别从小往大选，每一个级别最多能选 $\max(x - |已选择人数|,|该级别人数|)$ 个人，我们从大到小枚举并判断值在该级别中是否可行即可。
代码
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
|
using i3 = array<int, 3>;
void solve() {
int n;
cin >> n;
vector<i3> a(n);
int cnt = 0;
for (auto &[idx, l, r] : a) {
cin >> l >> r;
idx = ++cnt;
}
sort(a.begin(), a.end(), [](i3 l, i3 r) {
if (l[1] == r[1])
return l[2] > r[2];
return l[1] < r[1];
});
auto check = [&](int x, vector<int> *ans) {
int cnt = 0;
int l = 0;
bool ok = ans != nullptr;
while (l < n and cnt < x) {
vector<i3> tmp;
int r = l;
while (r < n and a[r][1] == a[l][1]) {
tmp.emplace_back(a[r]);
r++;
}
int res = min(x - cnt, (int)tmp.size());
int ret = 0;
for (int i = res; i >= 1; i--) {
int cur = max(x - cnt - i, 0);
if (cur <= tmp[i - 1][2]) {
ret = i;
break;
}
}
cnt += ret;
l = r;
if (ok) {
for (int i = 0; i < ret; i++)
ans->emplace_back(tmp[i][0]);
}
}
return cnt == x;
};
int p = *ranges::partition_point(views::iota(0, n + 1), [&](int x) {
return check(x, nullptr);
}) - 1;
vector<int> ans;
check(p, &ans);
cout << ans.size() << "\n";
for (auto &x : ans)
cout << x << " \n"[&x == &ans.back()];
}
|
D. 分布式系统
Easy
给定 $q$ 个操作和一个整数 $n$，第 $i$ 个操作记做 $a_i,\ b_i$。每一个操作会将每一个节点 $k=(b_i+j)\bmod n,j\in [0,a_i),k\in [0,n)$ 的值增加 $1$，求最后每一个节点的值。
显然可以使用差分。我们记 $a_i+b_i$ 为 $sum_i$，每一个节点的初始值为 $\sum_{i=0}^q\lfloor sum_i \rfloor$，然后再处理 $sum_i \bmod n$ 部分的节点即可。
代码
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
|
#define int long long
void solve() {
int n, q;
cin >> n >> q;
vector<int> ans(n + 1);
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
int r = a / n;
ans[0] += r;
ans[n] -= r;
int c = a % n;
if (c == 0)
continue;
if (b <= (b + c - 1) % n) {
ans[b] += 1;
ans[(b + c - 1) % n + 1] -= 1;
} else {
ans[b] += 1;
ans[n] -= 1;
ans[0] += 1;
ans[(b + c - 1) % n + 1] -= 1;
}
}
for (int i = 0; i < n; i++) {
ans[i + 1] += ans[i];
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " \n"[i == n - 1];
}
}
|
E. 最大公因数
Mid+
本题的重点可能在于需要恰好执行 $k$ 次操作。
因此我们可以得到最终的答案显然有 $ans|(\sum_{i=1}^n a_i +k)$。于是我们可以计算出 $sum=\sum_{i=1}^n a_i +k$ 的值然后枚举 $sum$ 的每一个因数即可。
嗯……问题看起来就是这样，非常简单。但是问题在于：这个 $sum$ 的数量级可能达到 $10^{12}$。显然不能 $O(n)$ 地遍历 $1..sum$ 来判断是否是因数（另外，这里的因数显然不只是质因数）。
稍有常识的小伙伴就可以想到我们遍历因数可以只遍历到 $\sqrt{sum}$ 即可，这样我们的复杂度就变成 $O(\sqrt{n})$ 的了，对于 $10^{12}$ 说不定能过。
然而并不能，因为实际上我们判断某一个因数是否可行用一般的方法的复杂度是 $O(n)$ 的。因此总的时间复杂度就变成 $O(\sqrt{sum}+nm)$ 了（其中 $m$ 是 $sum$ 的因数个数）。
于是我们就可以费尽心机开始优化：
首先我们考虑到若 $x>\max(a_i)$ 的情况，此时我们可以直接得出我们这个时候的操作次数 $cnt=xn-(sum-k)$，时间复杂度为 $O(1)$。
然后我们就需要考虑一下 $x\le\max(a_i)$ 的情况了。我们可以利用和上一种情况相似的思想：对于区间 $[L,R]$ 且 $R - L + 1 \le x$，把其中所有元素加成 $x$ 的倍数的操作数是 $c\times kx-s$，其中 $k=\lfloor \frac{L}{x} \rfloor$，$c$ 是区间内元素个数，$s$ 是区间内元素之和。因此我们就能在 $\max{a_i}/x$ 的复杂度下算完一个 $x$ 的可行性。总的复杂度是 $O(\max{a_i}\times(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{\max{a_i}}))\approx O(\max{a_i}\log\max{a_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
|
#define int long long
void solve() {
int n;
i64 k;
cin >> n >> k;
vector<int> a(n);
i64 sum = k;
int mx = -1;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
mx = max(a[i], mx);
}
vector<i64> fact;
for (i64 i = 1; i * i <= sum; i++) {
if (sum % i == 0) {
fact.emplace_back(i);
fact.emplace_back(sum / i);
}
}
sort(fact.begin(), fact.end(), greater{});
vector<i64> freq(mx + 1), pre(mx + 1);
for (auto x : a) {
freq[x]++;
pre[x] += x;
}
for (int i = 1; i < mx; i++) {
freq[i + 1] += freq[i];
pre[i + 1] += pre[i];
}
i64 ans = 1;
for (auto x : fact) {
i64 cnt = 0;
if (x <= mx) {
int rng = (mx + x - 1) / x;
for (int i = 1; i <= rng; i++) {
int L = (i - 1) * x + 1;
int R = min(mx, i * x);
i64 c = freq[R] - (freq[max(0ll, L - 1)]);
i64 s = pre[R] - (pre[max(0ll, L - 1)]);
cnt += c * i * x - s;
if (cnt > k)
break;
}
} else {
cnt = x * n - (sum - k);
}
if (cnt <= k and (k - cnt) % x == 0) {
cout << x << "\n";
return;
}
}
cout << "-1\n";
}
|
G. 装配线
Mid-
给定 $n$ 个任务和 $k$ 个工人，每过单位时间工人手中的完成的任务会向下一个工人手中移动直到最后一个工人完成，每个工人单位时间内只能完成一个任务，求完成所有任务需要几分钟。
考虑到没有任何堵塞的情况下，对于第 $t_i$ 分钟交给工人 $w_i$ 的任务 $a_i$ 来说，其耗时为 $t_i+k-w$。
在考虑堵塞的情况下，其实我们只需要考虑最后一个工人即可。
最后一位工人每分钟只能完成一个任务，因此所有任务在他这里实际上是在一个“单机 + 服务时间 1 分钟 + 先到先服务（FCFS）”的排队系统中被处理。
- 先将所有 $b_i$ 按非降序排序，记为
$$
a_1 \le a_2 \le \cdots \le a_n.
$$
- 令 $f_i$ 为第 $i$ 个（按上面顺序）任务的实际完成时间，则有递推
$$
f_1 = a_1,\quad
f_i = \max\bigl(a_i,\;f_{i-1} + 1\bigr)\quad(i=2,\dots,n).
$$
其中：
- 如果任务到达时机器空闲，就能立刻开始并在 $a_i$ 完成；
- 否则就要等到前一个任务处理完毕（即 $f_{i-1}+1$）后才能完成。
也就是从后往前更新堵塞即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
int w, t;
cin >> w >> t;
a[i] = t + k - w;
}
sort(a.begin(), a.end());
for (int i = 1; i < n; i++) {
a[i] = max(a[i], a[i - 1] + 1);
}
cout << a.back() << "\n";
}
|
H. 最小生成树
给定无向图 $G=(V,E)$。可以至多加入 $k$ 条边，每条边的权值为 $|u-v|$。最小化图的最小生成树的权值之和。
我们可以先跑一遍 Kruskal 得到该图的最小生成树，然后再做。
首先我们可以推出：加入边的最优情况只能是加入权值为 $1$ 的连接 $i$ 和 $i+1$ 的边来替代某条原本存在的连接 $i$ 和 $i+1$ 的权值大于 $1$ 的边。
证明
若我们的最小生成树 $T$ 中存在新增的一条边 $(u,v)$ 其权值 $|u-v|>1$。则去掉该边后 $T$ 会变成两个联通块。其中这两个联通块中必然存在一个节点 $i$ 使得 $i$ 和 $i+1$ 分属两个不同的联通块。连接此两节点即可，权值显然小于之前的权值。
然后我们直接选最大的 $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
|
using i4 = array<int, 4>;
using i64 = long long;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<i4> es;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
es.push_back({u, v, w, i + 1});
}
DSU dsu(n);
sort(es.begin(), es.end(), [](const i4 &l, const i4 &r) { return l[2] < r[2]; });
vector<i4> ans;
for (auto [u, v, w, i] : es) {
if (not dsu.same(u, v)) {
dsu.merge(u, v);
ans.push_back({u, v, w, i});
}
}
sort(ans.begin(), ans.end(), [](const i4 &l, const i4 &r) { return l[2] > r[2]; });
DSU usd(n);
i64 sum = 0;
vector<int> ret;
for (auto [u, v, w, i] : ans) {
if (k and w > 1) {
k--;
continue;
}
usd.merge(u, v);
sum += w;
ret.emplace_back(i);
}
vector<pair<int, int>> res;
int cnt = m;
for (int i = 1; i < n; i++) {
if (not usd.same(i, i - 1)) {
usd.merge(i, i - 1);
res.emplace_back(i, i + 1);
ret.emplace_back(++cnt);
sum++;
}
}
cout << res.size() << "\n";
for (auto [u, v] : res)
cout << u << " " << v << "\n";
cout << sum << "\n";
for (auto i : ret)
cout << i << ' ';
cout << "\n";
}
|
I. 方阵谜题
Mid
给定两个个 $3\times 3$ 的包含 $1..9$ 的网格，可以执行任意次如下操作：
- 右移某行；
- 下移某列；
- 顺时针旋转。
求将第一个网格转化为第二个网格所需的最小操作次数。
我们只需要关心网格的某位置元素在在第二个网格的哪个位置即可。我们可以使用 $BFS$ 来遍历所有的操作序列提前计算好所有位置变换的最短路径，使用时直接查询即可。
代码
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
|
using u8 = unsigned char;
using grid = array<u8, 9>;
grid op[7];
struct Hash {
size_t operator()(const grid &a) const noexcept {
size_t res = 0;
for (int i = 8; i >= 0; i--) {
res *= 10;
res += a[i];
}
return res;
}
};
unordered_map<grid, int, Hash> dist;
void initOp() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 9; j++)
op[i][j] = j, op[i + 3][j] = j;
int r = i * 3;
op[i][r] = r + 2, op[i][r + 1] = r, op[i][r + 2] = r + 1;
int c = i;
op[i + 3][c] = c + 6, op[i + 3][c + 3] = c, op[i + 3][c + 6] = c + 3;
}
op[6] = {6, 3, 0, 7, 4, 1, 8, 5, 2};
}
void initDist() {
queue<grid> q;
grid e;
iota(e.begin(), e.end(), 0);
q.push(e);
dist[e] = 0;
while (!q.empty()) {
grid cur = q.front();
q.pop();
int d = dist[cur];
for (int i = 0; i < 7; i++) {
grid res = {};
for (int j = 0; j < 9; j++)
res[j] = cur[op[i][j]];
if (not dist.contains(res)) {
dist[res] = d + 1;
q.push(res);
}
}
}
}
void solve() {
grid a, b, p;
for (int i = 0; i < 3; i++) {
string s;
cin >> s;
for (int j = 0; j < 3; j++) {
a[s[j] - '0' - 1] = i * 3 + j;
}
}
for (int i = 0; i < 3; i++) {
string s;
cin >> s;
for (int j = 0; j < 3; j++) {
b[i * 3 + j] = s[j] - '0' - 1;
}
}
for (int i = 0; i < 9; i++) {
p[i] = a[b[i]];
}
if (not dist.contains(p)) {
cout << "-1\n";
return;
}
cout << dist[p] << "\n";
}
|
L. 恒星
Easy-
过于简单，不做解释。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void solve() {
string a, b;
cin >> a >> b;
int na = mp[a[0]] * 10 + a[1] - '0';
int nb = mp[b[0]] * 10 + b[1] - '0';
if (na == nb) {
cout << "same\n";
} else if (na < nb) {
cout << "hotter\n";
} else {
cout << "cooler\n";
}
}
|