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)
题目大意
给定包含 .#
的二维网格。先随机将一个 .
改成#
,问#
的期望连通块数量。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 334beginner atcoder contest 334 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 310 beginner atcoder contest 327 beginner atcoder contest 332