title:
categories: 算法题解
description:
tags:
- atcoder
- DFS
- 思维
- 贪心
- 差分
- 概率DP
- 连分数
cover: /img/chino/vec/chino56.jpg
katex: true
date: 2023-12-21 14:47:38
A - Three Threes (abc333 A)
题目大意
给定一个\(0-9\)的数\(n\)，输出这个数 \(n\)次。
解题思路
模拟即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a;
cin >> a;
cout << string(a, '0' + a) << '\n';
return 0;
}
B - Pentagon (abc333 B)
题目大意
给定一个五边形和两个由两个顶点组成的线段，问线段长度是否相等。
解题思路
由全等可得比较两线段的长度等价于比较其端点在边上的距离相等。
于是给每个顶点编号，计算下一条线段的两个端点的距离（有两个，顺时针和逆时针，取较小的），然后判断这个距离是否相等即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
map<char, int> pos;
for (int i = 0; i < 5; ++i) {
pos['A' + i] = i;
}
auto dis = [&](char a, char b) {
int dis = abs(pos[a] - pos[b]);
return min(dis, abs(5 - dis));
};
if (dis(s1[0], s1[1]) == dis(s2[0], s2[1]))
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Repunit Trio (abc333 C)
题目大意
定义一类数，其数位都是\(1\)，即 \(1,11,111,1111,...\)。
问第 \(n\)小的数，它可以表示成三个上述数的和。
解题思路
范围只有\(333\)，直接枚举所有的组合情况，超过\(333\)即 break。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<LL> a;
set<LL> ans;
for (LL i = 1; 1; i = i * 10 + 1) {
a.push_back(i);
for (auto& j : a)
for (auto& k : a) {
ans.insert(i + j + k);
}
if (ans.size() >= n)
break;
}
cout << vector<LL>(ans.begin(), ans.end())[n - 1] << '\n';
return 0;
}
D - Erase Leaves (abc333 D)
题目大意
给定一棵树，每次删去一个叶子。
问把\(1\)号点删除的最小操作数。
解题思路
考虑\(1\)号点的所有儿子，当仅剩一个儿子时才可以删去 \(1\)号点，那就保留儿子子树最大的那棵，其余全删除即可。
DFS预处理下每个子树的大小和最大的儿子子树大小。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<int>> edge(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
edge[u].push_back(v);
edge[v].push_back(u);
}
vector<int> son(n), maxson(n);
auto dfs = [&](auto self, int u, int fa) -> void {
maxson[u] = son[u] = 1;
for (auto& v : edge[u]) {
if (v == fa)
continue;
self(self, v, u);
maxson[u] = max(maxson[u], son[v]);
son[u] += son[v];
}
};
dfs(dfs, 0, 0);
cout << son[0] - maxson[0] << '\n';
return 0;
}
E - Takahashi Quest (abc333 E)
题目大意
冒险，有背包，背包有容量。有两种事件：
- 遇到一瓶种类为\(x\)的毒药，可以选择捡到背包里或不捡
- 遇到一个种类为\(x\)的怪兽，如果没有对应的毒药，则寄了。否则消耗一瓶。
依次给出 \(n\)个事件，问能否活到最后，如果能活到，问背包容量的最小值。并给出对应的第一类事件的行为。
解题思路
类似于小车加油的问题，遇到一瓶毒药时，先不决定是否捡，而是作为一种后备选项，直到遇到对应的怪兽时，再决定当初要不要捡。
为了使背包容量最小，当这类毒药有多个时间点可以捡的时候，我们肯定是选择最近的那个时刻\(l\)来捡，直到当前时刻\(r\)用掉。选更早时刻的不会更优。
决策是上述的贪心做法，剩下的就是维护背包的容量，如果 时刻\(l\)捡一个物品，到时刻 \(r\)用掉，那么时刻 \([l, r-1]\)的背包容量都会 \(+1\)。由于要多次区间加法，仅最后一次查区间最值，这里可以用差分数组维护。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<vector<array<int, 2>>> potion(n);
vector<int> bag(n + 1);
vector<int> action;
bool ok = true;
for (int i = 0; i < n; ++i) {
int t, x;
cin >> t >> x;
--x;
if (t == 1) {
potion[x].push_back({int(action.size()), i});
action.push_back(0);
} else {
if (potion[x].empty()) {
ok = false;
break;
} else {
auto [potion_pos, pos] = potion[x].back();
potion[x].pop_back();
action[potion_pos] = 1;
bag[pos]++;
bag[i + 1]--;
}
}
}
int ans = bag[0];
for (int i = 1; i < n; ++i) {
bag[i] += bag[i - 1];
ans = max(ans, bag[i]);
}
if (!ok) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
for (auto& i : action)
cout << i << ' ';
cout << '\n';
}
return 0;
}
F - Bomb Game 2 (abc333 F)
题目大意
\(n\)个人排队。每个时刻两个事件等概率发生：
- 第一个人出队
- 第一个人去该队伍的最后的位置。
最后剩下一个人。
问每个人存活到最后的概率。
解题思路
设\(dp[i][j]\)表示有 \(i\)个人时，第 \(j\)个人存活的概率。根据概率的定义，有
- \(dp[i][1] = \frac{1}{2}dp[i][i]\)
- \(dp[i][j] = \frac{1}{2}dp[i - 1][j - 1] + \frac{1}{2}dp[i][j - 1]\)
很显然会发现有循环依赖，粗暴点可以直接高斯消元，但这题\(n\)有 \(3000\)跑不动 \(O(n^3)\)。
那就把循环依赖去掉，去掉的方法就是把式子展开，然后移项即可。
\(dp[i][1] = \frac{1}{2^{i}} dp[i][1] + \sum_{j=1}^{i-1} \frac{1}{2^{j+1}} dp[i-1][i-j]\)
\(dp[i][1] = \frac{\sum_{j=1}^{i-1} 2^{i - j - 1} dp[i-1][i-j]}{2^i - 1}\)
求出了\(dp[i][1]\)后， \(dp[i][2],dp[i][3]\)都可以顺势算出来了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b) {
long long qwq = 1;
while (b) {
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x) {
if (x < 0)
x += mo;
return qpower(x, mo - 2);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> dp{0, 1};
int inv2 = inv(2);
for (int i = 2; i <= n; ++i) {
vector<int> dp2(n + 1);
int p2 = 1;
for (int j = i - 1; j >= 1; --j) {
dp2[1] += 1ll * dp[i - j] * p2 % mo;
if (dp2[1] >= mo)
dp2[1] -= mo;
p2 = 1ll * p2 * 2 % mo;
}
dp2[1] = 1ll * dp2[1] * inv(qpower(2, i) - 1) % mo;
for (int j = 2; j <= i; ++j) {
dp2[j] = 1ll * (dp[j - 1] + dp2[j - 1]) * inv2 % mo;
}
dp.swap(dp2);
}
for (int i = 1; i <= n; ++i)
cout << dp[i] << " \n"[i == n];
return 0;
}
G - Nearest Fraction (abc333 G)
题目大意
给定\(r,n\)，找一对 \(p,q\)，使得 \(0 \leq p , q \leq n\)，\(gcd(p,q) == 1\),且 \(|r - \frac{p}{q}|\)最小。
解题思路
考虑到糖水加糖，越加越甜。对于初始范围\([\frac{0}{n}, \frac{n}{0}]\) ，可以二分中间值\(\frac{0+n}{n+0}\)（分子分母分别取均值），然后判断 \(r\)在哪个范围内。然后继续二分。
但貌似 atcoder的c++的long double的精度不够。
python竟然有直接求解的库，偷了。
减了个1e-100是想避免出现多个最小值。limit_denominator是输出分母最小的那个，而原题要求\(\frac{p}{q}\)最小。
神奇的代码
from fractions import Fraction
fr = Fraction(input())
n = int(input())
print(*(fr - Fraction("1e-100")).limit_denominator(n).as_integer_ratio())
- Beginner AtCoder Contest 333beginner atcoder contest 333 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327