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())
标签：AtCoder,Beginner,int,cin,long,333,tie,using,dp From： https://www.cnblogs.com/Lanly/p/17919200.html