A - Christmas Present (abc334 A)
题目大意
给定两个数\(b,g(b \neq g)\),如果 \(b\)大则输出 Bat
,否则输出Glove
。
解题思路
比较大小输出即可。
神奇的代码
#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, b;
cin >> a >> b;
if (a > b)
cout << "Bat" << '\n';
else
cout << "Glove" << '\n';
return 0;
}
B - Christmas Trees (abc334 B)
题目大意
给定\(a,m,l,r\),问有多少个整数 \(k\)满足 \(l \leq a + mk \leq r\).
解题思路
对不等式化简一下即为
\(\frac{l - a}{m} \leq k \leq \frac{r - a}{m}\)
的整数个数。
答案就是\(\lfloor \frac{r - a}{m} \rfloor - \lceil \frac{l - a}{m} \rceil + 1\)。
在C++
直接用floor,ceil
函数貌似有精度问题。
上下取整的转换是\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor\)。
但C++
的取整都是向0
取整(舍尾),在负数的时候不适用,因此代码里先把它们全部平移到正数。
神奇的代码
#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);
LL a, m, l, r;
cin >> a >> m >> l >> r;
l -= a;
r -= a;
if (l < 0) {
LL shift = -l;
shift += m - shift % m;
l += shift;
r += shift;
}
LL R = r / m;
LL L = (l + m - 1) / m;
LL ans = R - L + 1;
cout << ans << '\n';
return 0;
}
C - Socks 2 (abc334 C)
题目大意
给定\(n\)双袜子,编号 \(1-n\),但丢失了其中 \(k\)双袜子各一只。
现重新俩俩配对,使得每双袜子的编号差的和最小。
解题思路
考虑原本成双的袜子,如果拆开来配对单个袜子的话,发现不会更优。因此仅考虑单个袜子的。
单个袜子的按照编号从小到大一一配对,容易发现这是最小的了,任意交换两个配对方式都会导致差的和更大。
如果是偶数只则完美匹配,如果是奇数只,则需舍弃一只,枚举舍弃的这只(容易发现舍弃了这只后,左边数量一定是偶数,右边数量一定是偶数的情况才更优),剩下的就是从头一一匹配,而从尾一一匹配,这个可以事先预处理得到。时间复杂度是\(O(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 n, k;
cin >> n >> k;
vector<int> a(k);
for (auto& i : a)
cin >> i;
LL ans = 0;
if (~k & 1) {
for (int i = 0; i < k; i += 2)
ans += a[i + 1] - a[i];
} else if (k > 1) {
LL sum = 0;
for (int i = k - 1; i > 0; i -= 2)
sum += a[i] - a[i - 1];
ans = sum;
for (int i = 0; i < k - 1; i += 2) {
sum -= a[i + 2] - a[i + 1];
sum += a[i + 1] - a[i];
ans = min(ans, sum);
}
}
cout << ans << '\n';
return 0;
}
D - Reindeer and Sleigh (abc334 D)
题目大意
有\(n\)个雪橇,第 \(i\)个雪橇需要 \(r_i\)只麋鹿拉。
给定 \(q\)个询问,对于每个询问给定 \(x\)只麋鹿,问最多能拉多少个雪橇。
解题思路
很显然我们优先拉需要的麋鹿数量少的雪橇。
因此先对拉雪橇所需的麋鹿数量\(r_i\)拍个序,找到最大的\(k\)使得\(\sum_{i=1}{k}r_i \leq x\)。
在一个关于\(r_i\)的前缀和数组上 二分找到对应位置即可。时间复杂度是\(O(q\log 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 n, q;
cin >> n >> q;
vector<LL> r(n);
for (auto& i : r)
cin >> i;
ranges::sort(r);
partial_sum(r.begin(), r.end(), r.begin());
while (q--) {
LL x;
cin >> x;
auto pos = ranges::upper_bound(r, x) - r.begin();
cout << pos << '\n';
}
return 0;
}
E - Christmas Color Grid 1 (abc334 E)
题目大意
给定包含 .#
的二维网格。现随机将一个 .
改成#
,问#
的期望连通块数量。
解题思路
由于网格大小只有\(1000 \times 1000\),可以枚举每个 .
,计算它变成#
后的影响。
考虑如何计算影响,首先计算出原图的所有#
的连通块\(block\),可以用并查集或者BFS
。然后考虑当一个.
变成#
后,它能连通多少个不同的连通块。很显然四个方向,如果有\(x\)个不同的连通块,那么此时连通块数量就变成\(block + 1 - x\)。
所有情况求和,再除以 .
的数量即为答案。
神奇的代码
#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) { return qpower(x, mo - 2); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> s(h);
int red = 0;
for (auto& i : s) {
cin >> i;
red += ranges::count(i, '.');
}
vector<vector<int>> own(h, vector<int>(w, 0));
int block = 0;
array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};
auto BFS = [&](int x, int y) {
queue<array<int, 2>> team;
team.push({x, y});
block++;
own[x][y] = block;
while (!team.empty()) {
auto [x, y] = team.front();
team.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w ||
s[nx][ny] != '#' || own[nx][ny])
continue;
own[nx][ny] = block;
team.push({nx, ny});
}
}
};
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#' && !own[i][j])
BFS(i, j);
}
LL ans = 0;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j) {
if (s[i][j] == '.') {
set<int> nei;
for (int k = 0; k < 4; ++k) {
int x = i + dx[k], y = j + dy[k];
if (x < 0 || y < 0 || x >= h || y >= w || s[x][y] == '.')
continue;
nei.insert(own[x][y]);
}
ans += block + 1 - int(nei.size());
}
}
ans = ans % mo * inv(red) % mo;
cout << ans << '\n';
return 0;
}
F - Christmas Present 2 (abc334 F)
题目大意
二维平面,起点\(st\),依次去\(n\)个点送礼物,一次只能携带最多 \(k\)个礼物。只能回起点补充礼物。
问从起点出发,送完 \(n\)个点的礼物,并回到起点的最小距离和。
解题思路
考虑当前已经送完了前\(i\)点的礼物,那我接下来的决策就是决定送多少(\(\leq k\))个礼物 ,不同的决策就有一个距离代价。
由此设\(dp[i]\)表示送完前 \(i\)个点的礼物,并回到起点的最小距离和。考虑上次送了几个礼物,得转移式:
\(dp[i] = \min_{i - k \leq j \leq i - 1}(dp[j] + dis[st \to j+1] + dis[j + 1 \to ... \to i] + dis[i \to st])\)
时间复杂度是\(O(n^2)\)。
把中间的\(dis[j+1 \to ... \to i]\)用距离前缀和代替 \(sum[i] - sum[j + 1]\),并把与 \(j\)无关的项抽出来,得
\(dp[i] = \min_{i - k \leq j \leq i - 1}(dp[j] + dis[st \to j+1] - sum[j + 1]) + sum[i] + dis[i \to st]\)
中间是一个关于数组\(cost[j] = dp[j] + dis[st \to j+1] - sum[j + 1]\)的滑动窗口取 \(\min\),用单调队列优化即可。
时间复杂度是 \(O(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 n, k;
cin >> n >> k;
vector<array<int, 2>> pos(n + 1);
for (auto& i : pos)
cin >> i[0] >> i[1];
vector<double> sum(n + 2);
auto calc = [&](array<int, 2>& a, array<int, 2>& b) {
LL dx = a[0] - b[0];
LL dy = a[1] - b[1];
return sqrt(dx * dx + dy * dy);
};
vector<double> dis(n + 2, 0);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + calc(pos[i], pos[i - 1]);
dis[i] = calc(pos[i], pos[0]);
}
deque<pair<double, int>> team;
vector<double> dp(n + 1);
team.push_back({dp[0] + dis[1] - sum[1], 0});
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
while (!team.empty() && team.front().second < i - k) {
team.pop_front();
}
dp[i] = team.front().first + sum[i] + dis[i];
double cur = dp[i] + dis[i + 1] - sum[i + 1];
while (!team.empty() && team.back().first >= cur)
team.pop_back();
team.push_back({cur, i});
}
cout << fixed << setprecision(10) << dp.back() << '\n';
return 0;
}
G - Christmas Color Grid 2 (abc334 G)
题目大意
给定包含 .#
的二维网格。现随机将一个 #
改成.
,问#
的期望连通块数量。
解题思路
由于网格大小只有\(1000 \times 1000\),可以枚举每个 #
,计算它变成.
后的影响。
枚举#
,当它变成 .
,原本所在的#
连通块可能会被拆分成若干块,也可能不会被拆开,这取决于这个点是否是关键点,或者说割点
。
我们需要一个描述这样性质的信息,即tarjan
里的dfn
和low
。其中dfn[i]
表示第一次访问该点的时间,low[i]
表示从该点往下走,通过返祖边能往上返回的最早的节点的时间。
注意一张图可以看作是一颗DFS树
和一些返祖边构成,而这些返祖边就是会造成连通块不会被拆开
的原因。
因此先对原图进行DFS
,得到每个点的dfn
和low
。然后依次考虑删除每个点\(u\),对于其儿子点 \(v\),考虑其是否还和点\(u\)的父亲往上部分连通。
根据定义,如果 \(dfn[u] \leq low[v]\),说明 \(v\)子树无法回溯到点 \(u\)的父亲往上,也就和上面断开了,此时连通块数量会\(+1\)。。
因此,记\(dfs[u] \leq low[v]\)的 \(v\)的数量为 \(c\)。
如果当前点 \(u\)是根,则删去该点后,连通块 数量会增加\(c-1\),否则就增加 \(c\)。文章来源:https://www.toymoban.com/news/detail-760808.html
这样考虑一个#
后的连通块数量就能\(O(1)\)算的,所有情况累加,除以#
数量即为答案。文章来源地址https://www.toymoban.com/news/detail-760808.html
神奇的代码
#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) { return qpower(x, mo - 2); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> s(h);
int greeen = 0;
for (auto& i : s) {
cin >> i;
greeen += ranges::count(i, '#');
}
vector<int> dfn(h * w), low(h * w);
int time = 0;
int block = 0;
auto tr = [&](int x, int y) { return x * w + y; };
auto invtr = [&](int x) -> array<int, 2> { return {x / w, x % w}; };
array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};
vector<vector<int>> son(h * w);
vector<int> f(h * w);
auto dfs = [&](auto self, int u, int fa) -> void {
++time;
f[u] = fa;
dfn[u] = low[u] = time;
auto [x, y] = invtr(u);
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w || s[nx][ny] == '.')
continue;
int nu = tr(nx, ny);
if (nu == fa)
continue;
if (dfn[nu])
low[u] = min(low[u], dfn[nu]);
else {
son[u].push_back(nu);
self(self, nu, u);
low[u] = min(low[u], low[nu]);
}
}
};
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j) {
auto it = tr(i, j);
if (s[i][j] == '#' && !dfn[it]) {
++block;
dfs(dfs, it, it);
}
}
LL ans = 0;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
int cnt = 0, u = tr(i, j);
for (auto& v : son[u]) {
cnt += (dfn[u] <= low[v]);
}
ans += block - 1 + cnt + (f[u] != u);
}
}
ans = ans % mo * inv(greeen) % mo;
cout << ans << '\n';
return 0;
}
到了这里,关于AtCoder Beginner Contest 334的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!