A
题目链接
直接按题意模拟即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int Main()
{
int N, C;
std::cin >> N >> C;
std::vector<int> T(N + 1);
for (int i = 1; i <= N; ++i)
std::cin >> T[i];
int last = -1e9, ans = 0;
for (int i = 1; i <= N; ++i)
if (T[i] - last >= C)
++ans, last = T[i];
std::cout << ans << std::endl;
return 0;
}
|
B
题目链接
以左手为例。假设当前位置是$l$，要去的位置是$t$。
实际上只有两种走过去的方式——顺时针和逆时针。
如果顺时针走先碰到右手的位置$r$，那么只能逆时针走。等价于顺时针走$l$到$r$的距离小于$l$到$t$的距离。
于是我们写一个函数求从$a$走到$b$，按逆时针和顺时针的距离即可。
以顺时针为例，距离的求法是$b-a(b>a);n+b-a(b<a)$。或者统一一下，直接写$(n+b-a)\bmod n$。
逆时针走就是用$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
32
33
34
35
36
37
38
39
40
|
int dist(int n, int a, int b, int d)
{
if (d == 1)
return (n + (b - a)) % n;
else
return (n - (n + (b - a)) % n) % n;
};
int Main()
{
int n, q;
std::cin >> n >> q;
int l = 1, r = 2;
int ans = 0;
for (int i = 1; i <= q; ++i)
{
std::string h;
int t;
std::cin >> h >> t;
if (h == "L")
{
if (dist(n, l, t, 1) >= dist(n, l, r, 1))
ans += dist(n, l, t, -1);
else
ans += dist(n, l, t, 1);
l = t;
}
else
{
if (dist(n, r, t, 1) >= dist(n, r, l, 1))
ans += dist(n, r, t, -1);
else
ans += dist(n, r, t, 1);
r = t;
}
// std::cout << ans << std::endl;
}
std::cout << ans << std::endl;
return 0;
}
|
C
题目链接
如果有N个箱子和N个玩具，想每个玩具都放进去的话，那么一定是排序之后，$a[i]\leq b[i]$。
考虑现在少一个箱子，那么可以在出现$a[i]>b[i]$的时候，买一个$a[i]$大小的箱子就行。
这里可以使用双指针，一个指针$i$指向$a$数组，第二个指针$j$指向$b$数组。如果出现$j<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
|
int Main()
{
int n;
std::cin >> n;
std::vector<int> a(n + 1), b(n);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= n - 1; ++i)
std::cin >> b[i];
std::sort(a.begin() + 1, a.end(), std::greater<int>{});
std::sort(b.begin() + 1, b.end(), std::greater<int>{});
b.push_back(0);
int ans = 0;
for (int i = 1, j = 1; i <= n; ++i)
{
if (a[i] <= b[j])
{
j++;
continue;
}
else if (std::abs(j - i) == 1)
return printf("-1\n"), 0;
else
ans = a[i];
}
std::cout << ans << std::endl;
return 0;
}
|
D
题目链接
找到通向$1$的最小环，等价于有向图上找从$1$开始到$1$的前继的点的最短路。由于图没有边权，因此使用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
|
int Main()
{
int n, m;
std::cin >> n >> m;
std::vector adj(n + 1, std::vector<int>{});
for (int i = 1; i <= m; ++i)
{
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
}
std::queue<int> q;
q.push(1);
std::vector<int> dist(n + 1, 1e9);
dist[1] = 0;
while (q.size())
{
int u = q.front();
q.pop();
for (int v : adj[u])
{
if (v == 1)
return printf("%d\n", dist[u] + 1), 0;
if (dist[v] > dist[u] + 1)
dist[v] = dist[u] + 1, q.push(v);
}
}
printf("-1\n");
return 0;
}
|
E
题目链接
这种两个元素组合起来求一个最小值或者最大值的题，一般的解决方法是枚举其中一个元素，然后以枚举到的值为限制，求另一个值的最小值。
以这道题为例，可以枚举$max(A[i])$。那么我们发现，能加入到子序列中的都是比$A[i]$小的值。
相当于把两个数组都按$A[i]$排序之后，取$A[i]$为最大值，然后在$A[1]…A[i-1]$里找到$K-1$个数使得$B$数组的和最小。
显然找到找到最小的$K-1$个$B$数组里的数就行。那么维护一个大小为$K-1$的set或者堆即可。
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
|
int Main()
{
int N, K;
std::cin >> N >> K;
std::vector<int> A(N + 1), B(N + 1);
for (int i = 1; i <= N; i++)
{
std::cin >> A[i];
}
for (int i = 1; i <= N; i++)
{
std::cin >> B[i];
}
ll ans = 1e18;
std::vector<int> ord(N + 1);
for (int i = 1; i <= N; ++i)
ord[i] = i;
std::sort(ord.begin() + 1, ord.end(),
[&](int i, int j)
{
return A[i] < A[j];
});
std::priority_queue<int> pq;
ll sum = 0;
for (int p = 1; p <= N; ++p)
{
int i = ord[p];
sum += B[i];
pq.push(B[i]);
while (pq.size() > K)
{
sum -= pq.top();
pq.pop();
}
if (pq.size() == K)
ans = std::min(ans, sum * A[i]);
}
std::cout << ans << "\n";
return 0;
}
|
F
题目链接
可以考虑一个dp。
$dp[i][j]$表示前$i$个查询之后，另一只手在$j$位置的最小操作数。然而这里“另一只手”的描述稍微有点不利于转移。
注意到每次操作之后都有某一只手的位置是固定的，现在未知的就是另一只手的位置，我们的枚举也是另一只手。为了方便明确状态和转移，这里不妨以两只手的某种关系来做状态的第二维。
例如：两只手位置的和、两只手位置的差、两只手位置的乘积等等。
这里选择两只手位置的和$s$来做状态的第二维。那么只需要根据上一个操作即可解出目前两只手的位置。注意规避两只手位置相同，或者小于等于$0$的情况。
其实更好的状态可以选择枚举两只手位置的异或值。这样只要我们不从$0$开始枚举，那么能规避两只手位置是负数以及相同的情况，可以少写一些判断。
接下来考虑$dp[i][s]$。前i个查询之后，目前两只手位置和为$s$的最小操作数。
我们在思考转移的时候，感觉前一个状态不太好找。那么不妨考虑顺推。用$dp[i][s]$去推$dp[i+1][s’]$。
现在我们知道$i$查询之后的左右手的值$l, r$。
以及$i+1$查询，某一只手的目的地$t$。假设是左手。
根据B题的结论，我们依旧是两种决策——从顺时针走和逆时针走。
如果从顺时针走先碰到了右手，那么右手的最终位置是$(t+1) \bmod n$。
从逆时针走先碰到右手，右手的最终位置是$(t-1) \bmod n$。
用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
|
int Main()
{
int n, q;
std::cin >> n >> q;
std::vector<std::array<int, 2>> op(q + 1);
for (int i = 1; i <= q; ++i)
{
std::string h;
std::cin >> h >> op[i][1];
op[i][0] = (h == "R");
}
std::vector dp(q + 1, std::vector<int>(n * 2 + 1, 1e9));
dp[0][3] = 0;
op[0] = {0, 1};
auto dist = [&](int a, int b, int d)
{
if (d == 1)
return (n + (b - a)) % n;
else
return (n - (n + (b - a)) % n) % n;
};
for (int i = 0; i < q; ++i)
{
for (int s = 2; s <= n + n; ++s)
{
if (dp[i][s] > 2 * q * n)
continue;
int l = (op[i][0] == 0) ? op[i][1] : (s - op[i][1]);
int r = (op[i][0] == 1) ? op[i][1] : (s - op[i][1]);
if (l <= 0 || r <= 0 || l == r)
continue;
if (op[i + 1][0] == 1)
std::swap(l, r);
// printf("dp[%d][%d][%d] = %d\n", i, l, r, dp[i][s]);
int L = op[i + 1][1];
if (dist(l, L, -1) >= dist(l, r, -1))
{
int R = (L - 1) % n;
if (R == 0)
R = n;
dp[i + 1][L + R] = std::min(dp[i + 1][L + R], dist(l, L, -1) + dist(r, R, -1) + dp[i][s]);
}
if (dist(l, L, -1) < dist(l, r, -1))
{
dp[i + 1][L + r] = std::min(dp[i + 1][L + r], dist(l, L, -1) + dp[i][s]);
}
if (dist(l, L, 1) >= dist(l, r, 1))
{
int R = (L + 1) % n;
if (R == 0)
R = n;
dp[i + 1][L + R] = std::min(dp[i + 1][L + R], dist(l, L, 1) + dist(r, R, 1) + dp[i][s]);
}
if (dist(l, L, 1) < dist(l, r, 1))
dp[i + 1][L + r] = std::min(dp[i + 1][L + r], dist(l, L, 1) + dp[i][s]);
}
}
int ans = *std::min_element(dp[q].begin(), dp[q].end());
std::cout << ans << std::endl;
return 0;
}
|
G
题目链接
一道数学期望的题目。
假设有一个探测排列$q$。我们来分析一下这个$q$有什么性质。
$q[i]$在第$i$次被探测到，那么相当于$q[i]$的父亲在$i$之前被探测到了。
也就是说，$q$中节点的顺序，应该保证$q[i]$的父亲在$q[i]$之前出现。
然后考虑这个排列$q$的操作期望。设$sum$是$a$的总和。
如果财宝在$q[i]$位置，那么有$\frac{a[q[i]]}{sum}$的概率在$q[i]$停止探测。
于是根据期望的公式，一个排列$q$的期望操作次数就是
$$E(q)=\sum_{i=1}^n \frac{i*a[q[i]]}{sum}$$注意到$sum$是一个定值。那么最小期望操作次数的排列$q$，满足$\sum_{i=1}^n i*a[q[i]]$是最小的。
整理一下，最佳的排列$q$，需要满足两个条件：
1.$q$中节点的顺序，应该保证$q[i]$的父亲在$q[i]$之前出现
2.$\sum_{i=1}^n i*a[q[i]]$是最小的
这个问题叫做按树上先序的贪心。
原题是2018年湖南省队的题目排列。
贪心的idea可能比较反直觉。
假设没有树上的父亲要在前面这个条件，根据排序不等式，显然是把$a[i]$按降序排序能得到最小值。
那么考虑当前最大的$a[i]$。
如果$a[i]$的父亲是$0$，那么可以直接搜点$i$。
如果$a[i]$有其它的父亲，那么一定是搜完了父亲之后，直接来搜$i$。
第二句话等价于在最优排列中，$i$的父亲和$i$一定是挨着的。
因此我们可以考虑把$i$和$i$的父亲合并起来，因为他们俩必定是挨在一起出现。
于是若干操作之后，要比较的是多个合并后的节点。
那么合并之后的节点需要怎么计算权重呢？
根据题目限制的条件，假设两个合并之后的节点$x$和$y$，分别代表两个必须要挨在一起的序列。
节点x的序列长度为$c_1$，序列权重和为$s_1$，这个序列的答案$(\sum i*a[i])$是$ans_1$。节点y的序列长度为$c2$，序列权重和为$s2$，序列的答案是$ans_2$。
如果$x$在$y$之前，相当于为答案提供的贡献是$ans_1+ans_2+c_1* s_2$。反之，为答案提供的贡献是$ans_2+ans_1+c_2*s_1$。
如果$x$在$y$之前更好，把这两个式子做一个差，等价于$\frac{s_1}{c_1}>\frac{s_2}{c_2}$;相当于合并之后的节点，权重是平均值。
用堆维护当前节点的权重大小，用并查集维护节点之间的合并关系，这道题就解决了。
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
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include <atcoder/modint>
using modint = atcoder::modint998244353;
struct DSU
{
public:
DSU() : n(0) {}
explicit DSU(int _n) : n(_n), parent_or_size(_n + 1, -1) {}
int merge(int a, int b)
{
int x = leader(a), y = leader(b);
if (x == y)
return x;
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b)
{
return leader(a) == leader(b);
}
int leader(int a)
{
if (parent_or_size[a] < 0)
return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a)
{
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups()
{
std::vector<int> leader_buf(n + 1), group_size(n + 1);
for (int i = 1; i <= n; i++)
{
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(n);
for (int i = 1; i <= n; i++)
{
result[i].reserve(group_size[i]);
}
for (int i = 1; i <= n; i++)
{
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v)
{ return v.empty(); }),
result.end());
return result;
}
private:
int n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
std::vector<int> p(n + 1);
for (int i = 1; i <= n; ++i)
read(p[i]);
for (int i = 1; i <= n; ++i)
read(a[i]);
p[0] = -1;
struct comp
{
bool operator()(const std::array<int, 3> &lhs, const std::array<int, 3> &rhs) const
{
auto [_, v1, s1] = lhs;
auto [__, v2, s2] = rhs;
return 1ll * v1 * s2 < 1ll * v2 * s1;
}
};
DSU dsu(n);
std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>, comp> heap{};
for (int i = 1; i <= n; ++i)
{
heap.push({i, a[i], 1});
}
modint ans = 0;
int size = 0;
while (heap.size())
{
auto [i, v, cnt] = heap.top();
heap.pop();
int fa = p[i];
if (dsu.leader(i) != i || cnt != dsu.size(i))
continue;
int u = dsu.leader(p[i]);
ans += 1ll * dsu.size(u) * v;
a[u] += v;
dsu.merge(u, i);
if (u != 0)
heap.push({u, a[u], dsu.size(u)});
}
ans /= modint(a[0]);
printf("%d\n", ans);
return 0;
}
|
