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
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
B – Pentagon (abc333 B)
题目大意
给定一个五边形和两个由两个顶点组成的线段,问线段长度是否相等。
解题思路
由全等可得比较两线段的长度等价于比较其端点在边上的距离相等。
于是给每个顶点编号,计算下一条线段的两个端点的距离(有两个,顺时针和逆时针,取较小的),然后判断这个距离是否相等即可。
神奇的代码
#include
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 pos;
for (int i = 0; i
C – Repunit Trio (abc333 C)
题目大意
定义一类数,其数位都是(1),即 (1,11,111,1111,…)。
问第 (n)小的数,它可以表示成三个上述数的和。
解题思路
范围只有(333),直接枚举所有的组合情况,超过(333)即 break
。
神奇的代码
#include
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 a;
set 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 (ans.begin(), ans.end())[n - 1]
D – Erase Leaves (abc333 D)
题目大意
给定一棵树,每次删去一个叶子。
问把(1)号点删除的最小操作数。
解题思路
考虑(1)号点的所有儿子,当仅剩一个儿子时才可以删去 (1)号点,那就保留儿子子树最大的那棵,其余全删除即可。
DFS
预处理下每个子树的大小和最大的儿子子树大小。
神奇的代码
#include
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> edge(n);
for (int i = 0; i > u >> v;
--u, --v;
edge[u].push_back(v);
edge[v].push_back(u);
}
vector 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
E – Takahashi Quest (abc333 E)
题目大意
冒险,有背包,背包有容量。有两种事件:
- 遇到一瓶种类为(x)的毒药,可以选择捡到背包里或不捡
- 遇到一个种类为(x)的怪兽,如果没有对应的毒药,则寄了。否则消耗一瓶。
依次给出 (n)个事件,问能否活到最后,如果能活到,问背包容量的最小值。并给出对应的第一类事件的行为。
解题思路
类似于小车加油的问题,遇到一瓶毒药时,先不决定是否捡,而是作为一种后备选项,直到遇到对应的怪兽时,再决定当初要不要捡。
为了使背包容量最小,当这类毒药有多个时间点可以捡的时候,我们肯定是选择最近的那个时刻(l)来捡,直到当前时刻(r)用掉。选更早时刻的不会更优。
决策是上述的贪心做法,剩下的就是维护背包的容量,如果 时刻(l)捡一个物品,到时刻 (r)用掉,那么时刻 ([l, r-1])的背包容量都会 (+1)。由于要多次区间加法,仅最后一次查区间最值,这里可以用差分数组维护。
神奇的代码
#include
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>> potion(n);
vector bag(n + 1);
vector action;
bool ok = true;
for (int i = 0; i > 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
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
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 > n;
vector dp{0, 1};
int inv2 = inv(2);
for (int i = 2; i 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
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())
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net