ABC376(A-G)
A - Candy Button¶
题目大意
有一个按钮，你将会按这个按钮 \(N\) 次，你会在第 \(T_i(0 < T_1 < T_2 < \cdots < T_N)\) 秒按一次。按一次按钮你会获得一颗糖果，两次获得糖果的间隔必须大于等于 \(C\) 秒。问：你能获得多少次糖果？
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, c;
cin >> n >> c;
int last = -1000, now;
int ans = 0;
for (int i = 0; i < n; i++)
{
cin >> now;
if (now - last >= c)
{
ans++;
last = now;
}
}
cout << ans << endl;
return 0;
}
B - Hands on Ring (Easy)¶
题目大意
有一个环，环上有 \(N(3 \le N \le 100)\) 个位置。有两个棋子 L 和 R。初始的时候，L 在位置 \(1\)，R 在位置 \(2\)。你可以将棋子移动到环上相邻的位置，但是，在任意时刻都不能出现两个棋子公用
给你 \(Q(1 \le Q \le 100)\) 条指令，每条指令包含一个字符 \(H_i\) 和整数 \(T_i\)。其中 \(H_i\) 只可能是字符 L 和 R，\(1 \le T_i \le N\)。对于一条指令，如果 \(H_i\) 是 L，表示你需要将 L 棋子移动到位置 \(T_i\) 上。如果 \(H_i\) 是 R，表示你需要将 R 棋子移动到位置 \(T_i\) 上。对于每条指令，你 只能 \(H_i\) 一枚棋子。
问：执行完所有指令最少需要移动多少步棋子？
解题思路
移动棋子可以逆时针和顺时针，但是一定会有一个方向会被另一枚棋子挡住，所以排除掉被挡住的方向即可。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
int l = 0, r = 1;
int ans = 0;
auto move_left = [n](int s, int t) -> int
{ return (s - t + n) % n; };
auto move_right = [n](int s, int t) -> int
{ return (t - s + n) % n; };
while (q--)
{
char h;
int t;
cin >> h >> t;
t--;
if (h == 'L')
{
if (t == l)
continue;
int dl = move_left(l, t);
int dr = move_right(l, t);
ans += dl < move_left(l, r) ? dl : dr;
l = t;
}
else
{
if (t == r)
continue;
int dl = move_left(r, t);
int dr = move_right(r, t);
ans += dl < move_left(r, l) ? dl : dr;
r = t;
}
}
cout << ans << endl;
return 0;
}
C - Prepare Another Box¶
题目大意
有 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个玩具和 \(N-1\) 个箱子，第 \(i\) 个玩具的大小是 \(A_i\)，第 \(i\) 个箱子可以装一个 \(B_i\) 大小的玩具。一个箱子只能装一个玩具，你还需要再买一个箱子，问：至少还需要一个多少容量的箱子才能装下所有的玩具？如果无论多大的箱子都不能装下所有的玩具，输出 -1。
解题思路
将 \(A\) 和 \(B\) 排序，然后从后往前一个个对（即寻找 \(A_i \le B_{i-1}\)），碰到第一个装不下的玩具时，即从后往前找到第一组不满足 \(A_i \le B_{i-1}\) 的 \(i\)，表示我们需要买一个大小为 \(A_i\) 的箱子。然后再判断 \(B_1\) 到 \(B_{i-1}\) 能否装下 \(A_1\) 到 \(A_{i-1}\)，如果能答案就是 \(A_i\)。否则答案就是 -1
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 1; i < n; i++)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin() + 1, b.end());
for (int i = n - 1; i >= 0; i--)
{
if (b[i] < a[i])
{
for (int j = 1; j <= i; j++)
{
if (b[j] < a[j - 1])
{
cout << -1 << endl;
return 0;
}
}
cout << a[i] << endl;
break;
}
}
return 0;
}
D - Cycle¶
题目大意
给你一个有向图，求包含点 \(1\) 在内最小的环的边数。
解题思路
将所有的形如 \((t, 1)\) 的边存起来。然后从点 \(1\) 开始跑一遍 bfs，接着遍历所有的点 \(t\)，答案就是 \(\min\{dis[t]+1\}\)
参考代码
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max() / 2;
const int MAXN = 2E5 + 10;
const int MAXM = 2E5 + 10;
int n, m;
int head[MAXN], edge[MAXM], ne[MAXM], idx = 1;
void add(int u, int v)
{
edge[idx] = v;
ne[idx] = head[u];
head[u] = idx++;
}
int dis[MAXN];
void bfs()
{
fill(dis, dis + MAXN, INF);
dis[1] = 0;
queue<int> q;
q.push(1);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if (dis[v] > dis[u] + 1)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
}
int main()
{
cin >> n >> m;
vector<int> t;
while (m--)
{
int u, v;
cin >> u >> v;
add(u, v);
if (v == 1)
t.push_back(u);
}
bfs();
int ans = INF;
for(auto u : t)
ans = min(ans, dis[u] + 1);
if(ans == INF)
ans = -1;
cout << ans << endl;
return 0;
}
E - Max × Sum¶
题目大意
给你两个长度为 \(N(1 \le N \le 2 \times10^5)\) 的序列 \(A\) 和 \(B\)。设 \(S\) 表示 \({1, 2, \cdots, N}\) 的一个长度为 \(K\) 的子集。求出最小的 \((\max\limits_{i\in S}A_i)\times(\sum\limits_{i\in S}B_i)\)
解题思路
将 \((A_i, B_i)\) 按照 \(A_i\) 排序，从小到大遍历的相当于最大的 \(A_i\) 已经固定，只需要维护最小的 \(K\) 个 \(B_i\) 即可，用大顶堆可以轻松实现。
参考代码
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<pair<LL, LL>> ab(n);
for (int i = 0; i < n; i++)
cin >> ab[i].first;
for (int i = 0; i < n; i++)
cin >> ab[i].second;
sort(ab.begin(), ab.end());
LL sum = 0;
priority_queue<LL> heap;
for (int i = 0; i < k; i++)
{
sum += ab[i].second;
heap.push(ab[i].second);
}
LL ans = sum * ab[k - 1].first;
for (int i = k; i < n; i++)
{
sum += ab[i].second;
heap.push(ab[i].second);
LL big = heap.top();
heap.pop();
sum -= big;
ans = min(ans, sum * ab[i].first);
}
cout << ans << endl;
}
return 0;
}
F - Hands on Ring (Hard)¶
题目大意
有一个环，环上有 \(N(3 \le N \le 3000)\) 个位置。有两个棋子 L 和 R。初始的时候，L 在位置 \(1\)，R 在位置 \(2\)。你可以将棋子移动到环上相邻的位置，但是，在任意时刻都不能出现两个棋子公用
给你 \(Q(1 \le Q \le 3000)\) 条指令，每条指令包含一个字符 \(H_i\) 和整数 \(T_i\)。其中 \(H_i\) 只可能是字符 L 和 R，\(1 \le T_i \le N\)。对于一条指令，如果 \(H_i\) 是 L，表示你需要将 L 棋子移动到位置 \(T_i\) 上。如果 \(H_i\) 是 R，表示你需要将 R 棋子移动到位置 \(T_i\) 上。在对于每条指令，如有需要，你 可以 移动两枚棋子。
问：执行完所有指令最少需要移动多少步棋子？
解题思路
本题和 B 题的区别就在于可以移动两枚棋子。B 题由于只能移动一颗棋子，移动的方式其实是固定的。但是可以移动两个棋子，每一次移动就会有顺时针和逆时针两种路径，可以这样处理指令的时候我们可以让另一枚棋子挪开。例如：现在 \(L = 2, R = 4\)，将 \(R\) 移动到 \(1\)，可以让 \(L\) 挪到 \(N\)，然后再让 \(R\) 挪到 \(1\)。
因此每一次移动都要考虑另一枚棋子的状态。定义 \(dp[i][j]\) 表示处理完前 \(i\) 条指令之后，另一枚棋子停在位置 \(j\) 所需要移动的最小步数。转移的时候从前向后更新。注意另一枚棋子恰好停在 \(T_i\) 上的情况。
参考代码
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
const int INF = numeric_limits<int>::max() / 2;
int main()
{
int n, q;
cin >> n >> q;
vector<char> h(q);
vector<int> t(q);
for (int i = 0; i < q; i++)
{
cin >> h[i] >> t[i];
t[i]--;
}
vector<vector<int>> dp(q, vector<int>(n, INF));
auto move_left = [n](int s, int t) -> int
{ return (s - t + n) % n; };
auto move_right = [n](int s, int t) -> int
{ return (t - s + n) % n; };
auto update = [&move_left, &move_right, n](vector<int> &dp, int base, int hand, int other_hand, int target) -> void
{
if (hand == target)
dp[other_hand] = min(dp[other_hand], base);
else
{
int dl = move_left(hand, target);
int dr = move_right(hand, target);
int dhands = move_left(hand, other_hand);
int lpos = (target - 1 + n) % n;
int rpos = (target + 1) % n;
if (dl > dhands)
{
dp[lpos] = min(dp[lpos], base + move_left(other_hand, lpos) + dl);
dp[other_hand] = min(dp[other_hand], base + dr);
}
else if (dl == dhands)
{
dp[lpos] = min(dp[lpos], base + 1 + dl);
dp[rpos] = min(dp[rpos], base + 1 + dr);
}
else
{
dp[rpos] = min(dp[rpos], base + move_right(other_hand, rpos) + dr);
dp[other_hand] = min(dp[other_hand], base + dl);
}
}
};
if (h[0] == 'L')
update(dp[0], 0, 0, 1, t[0]);
else
update(dp[0], 0, 1, 0, t[0]);
for (int i = 0; i < q - 1; i++)
{
if (h[i] == h[i + 1])
{
for (int other_hand = 0; other_hand < n; other_hand++)
{
if (dp[i][other_hand] == INF)
continue;
update(dp[i + 1], dp[i][other_hand], t[i], other_hand, t[i + 1]);
}
}
else
{
for (int other_hand = 0; other_hand < n; other_hand++)
{
if (dp[i][other_hand] == INF)
continue;
update(dp[i + 1], dp[i][other_hand], other_hand, t[i], t[i + 1]);
}
}
}
int ans = INF;
for (int x = 0; x < n; x++)
ans = min(ans, dp[q - 1][x]);
cout << ans << endl;
return 0;
}
AGC023 F - 01 on Tree¶
注：本题解法是 G 题的前置知识。
题目大意
给你一颗 \(N(1 \le N \le 2 \times 10^5)\) 个点的树，点的编号为 \(1\) 到 \(N\)，其中 \(1\) 是根节点。节点 \(i(2 \le i \le N)\)，的父节点是 \(p_i\)。每个节点上有数值 \(V_i\)，其中 \(V_i\) 是 \(0\) 或 \(1\)。求出该图的一个拓扑序列，使得该拓扑序列对应的 \(V_i\) 值组成的 01 序列的逆序数最少。
解题思路
首先需要知道 \(01\) 序列计算逆序数的一个推论，设有一段 \(01\) 序列 \(S = S_1 + S_2\)，其中 \(+\) 表示字符串连接。用 \(R(S)\) 表示序列 \(S\) 的逆序数，\(C_0(S)\) 表示序列 \(S\) 中 \(0\) 的个数，\(C_1(S)\) 表示序列 \(S\) 中 \(1\) 的个数，则 \(R(S) = R(S_1) + R(S_2) + C_1(S_1) \times C_0(S_2)\)。下面考虑如何构造答案。
拓扑序列第一个点一定是根节点 \(1\)，考虑如何加入节点。可以发现：
- 如果当前可以加入 \(0\)，那么加入 \(0\) 一定会比加入 \(1\) 更好。
这个结论是非常显然的，于是考虑一种归并式的做法，将所有的 \(0\) 合并到父节点上，被归并的节点相当于当父节点被选择后就一并选择。归并后，树上还剩下一些形如 \(1000...\) 的节点。假设某个节点 \(x\) 现在有子节点 \(a\) 和 \(b\)，如果先归并 \(a\)，再归并 \(b\)，产生的逆序数就是 \(R(x) = R(a) + R(b) + C_1(a) \times C_0(b)\)，如果归并 \(b\) 再归并 \(a\)，产生的逆序数就是 \(R(x) = R(a) + R(b) + C_1(b) \times C_0(a)\)，因此，当且仅当 \(C_1(a) \times C_0(b) < C_1(b) \times C_0(a)\) 即 \(\frac{C_1(a)}{C_0(a)} < \frac{C_1(b)}{C_0(b)}\)，此时先归并 \(a\) 更优。所以，维护每个节点里面 \(0\) 和 \(1\) 的数量，按照 \(\frac{C_1(a)}{C_0(a)}\) 排序放到小顶堆里面就能选出下一个归并的节点。
下面考虑推广 \(\frac{C_1(a)}{C_0(a)}\)，为了实现优先选 \(0\)，当 \(C_1(a) = 0\) 时，小顶堆一定会弹出全是 \(0\) 的序列，所以实际上不需要预处理所有将所有的 \(0\) 合并的步骤。再考虑 \(C_0(a) = 0\) 的情况，这实际就相当于全是 \(1\) 的某个序列，这种序列一定是最后被添加的（也就是添加到末尾的），可以令 \(\frac{C_1(a)}{C_0(a)} =+\infty\)，就能保证最后弹出。
每一次合并的时候需要计算合并新序列所新增的逆序数，这同样可以通过 \(R(S) = R(S_1) + R(S_2) + C_1(S_1) \times C_0(S_2)\) 来计算，增量的部分就是 \(C_1(S_1) \times C_0(S_2)\)。此外，合并的时候还需要维护一个并查集，堆实际也是懒删除堆，注意判断堆顶的元素是不是最新的。
参考代码
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using LL = long long;
// 并查集，merge(a, b) 会让 b 加入 a
// 下标从0开始
class DSU
{
public:
explicit DSU(int n) : parent_or_size(n, -1) {}
// b 加入到 a 的集合
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;
}
int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int a) { return -parent_or_size[leader(a)]; }
private:
std::vector<int> parent_or_size;
};
struct Node
{
int id;
LL c0, c1;
bool operator>(const Node &other) const { return c1 * other.c0 > other.c1 * c0; }
bool operator!=(const Node &other) const { return id != other.id || c0 != other.c0 || c1 != other.c1; }
};
int main()
{
int n;
cin >> n;
vector<int> p(n), v(n);
p[0] = -1;
DSU dsu(n);
for (int i = 1; i < n; i++)
{
cin >> p[i];
p[i]--;
}
vector<Node> state(n);
priority_queue<Node, vector<Node>, greater<Node>> heap;
for (int i = 0; i < n; i++)
{
state[i] = {i, 0, 0};
cin >> v[i];
v[i] ? state[i].c1++ : state[i].c0++;
if (i)
heap.push(state[i]);
}
LL ans = 0;
while (!heap.empty())
{
Node u = heap.top();
heap.pop();
int uid = u.id;
u = state[dsu.leader(uid)];
if (u != state[uid])
continue;
int fid = dsu.leader(p[uid]);
Node &f = state[fid];
ans += f.c1 * u.c0;
f.c0 += u.c0;
f.c1 += u.c1;
dsu.merge(fid, uid);
if (fid)
heap.push(f);
}
cout << ans << endl;
return 0;
}
G - Treasure Hunting¶
题目大意
给你一颗 \(N+1(1 \le N \le 2 \times 10^5)\) 个点的树，点的编号为 \(0\) 到 \(N\)，其中 \(0\) 是根节点。节点 \(i(1 \le i \le N)\)，的父节点是 \(p_i\)。除了根节点以外有一个节点藏有宝藏。每个节点 \(i(1 \le i \le N)\) 有一个权值 \(a_i\)，节点 \(i(1 \le i \le N)\) 出现宝藏的概率是 \(\frac{a_i}{\sum\limits_{i=1}^Na_i}\)。你可以搜索节点来发现宝藏，搜索节点 \(i(1 \le i \le N)\) 的前提是节点 \(i\) 的父节点 \(p_i\) 已经被搜索过。初始的时候你已经搜索过节点 \(0\)（节点 \(0\) 一定没有宝藏），搜索一个新节点需要耗费 \(1\) 点体力（搜索节点 \(0\) 不需要耗费体力）。你需要求出一个最优的搜索顺序，使得搜索到宝藏所耗费的体力的数学期望最小。输出最小的数学期望，答案对 \(998244353\) 取模
解题思路
设某个搜索序列为 \(P = (P_1, P_2, \cdots, P_N)\)，令 \(S = \sum\limits_{i=1}^Na_i\)，则数学期望为 \(E = \sum\limits_{i =1}^Ni \times \frac{a_i}{S} = \frac{1}{S} \sum\limits_{i =1}^Ni \times a_i\)
这实际上可以转换成上面的 01 on tree 来解决，我们将包括根节点 \(0\) 在内的节点 \(i(0 \le i \le N)\) 初始的时候视为 \(000...1\) 的序列，其中 \(0\) 重复了 \(a_i\) 次（\(a_0 = 0\)），这样初始只有根节点的时候只有 \(1\) 个 \(1\)，合并一个点 \(i\) 就相当于增加了 \(1 \times a_i\) 的逆序数，然后有 \(2\) 个 \(1\)，下一次合并点 \(j\) 就会增加 \(2 \times a_j\) 的逆序数，所以逆序数就等价于 \(\sum\limits_{i =1}^Ni \times a_i\)，所以问题就转化为 01 on tree。
参考代码
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using LL = long long;
const LL MOD = 998244353;
// 并查集，merge(a, b) 会让 b 加入 a
// 下标从 0 开始
class DSU
{
public:
explicit DSU(int n) : parent_or_size(n, -1) {}
// b 加入到 a 的集合
void merge(int a, int b)
{
int x = leader(a), y = leader(b);
if (x == y)
return;
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
}
int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int a) { return -parent_or_size[leader(a)]; }
private:
// 如果 parent_or_size[u] >= 0，表示指向的父节点
// 如果 parent_or_size[u] < 0，表示自己就是父节点，-parent_or_size[u] 表示集合大小
std::vector<int> parent_or_size;
};
struct Node
{
int id;
LL c0, c1;
bool operator>(const Node &other) const { return c1 * other.c0 % MOD > other.c1 * c0 % MOD; }
bool operator!=(const Node &other) const { return id != other.id || c0 != other.c0 || c1 != other.c1; }
};
pair<LL, LL> exgcd(LL a, LL b)
{
if (b == 0)
return {1, 0};
auto [x, y] = exgcd(b, a % b);
return {y, x - a / b * y};
}
LL inv(LL a, LL p)
{
auto [x, y] = exgcd(a, p);
if (x < 0)
x += p;
return x;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> p(n + 1), a(n + 1);
p[0] = -1;
DSU dsu(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> p[i];
p[i];
}
vector<Node> state(n + 1);
state[0] = {0, 0, 1};
priority_queue<Node, vector<Node>, greater<Node>> heap;
LL sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
state[i] = {i, a[i], 1};
heap.push(state[i]);
}
sum %= MOD;
sum = inv(sum, MOD);
LL ans = 0;
while (!heap.empty())
{
Node u = heap.top();
heap.pop();
int uid = u.id;
u = state[dsu.leader(uid)];
if (u != state[uid])
continue;
int fid = dsu.leader(p[uid]);
Node &f = state[fid];
ans = (ans + f.c1 * u.c0) % MOD;
f.c0 = (f.c0 + u.c0) % MOD;
f.c1 = (f.c1 + u.c1) % MOD;
dsu.merge(fid, uid);
if (fid)
heap.push(f);
}
cout << ans * sum % MOD << endl;
}
return 0;
}
创建日期: 2024-12-21