有的人边上课边打abc
A - Weak Beats (abc323 A)
题目大意
给定一个\(01\)字符串,问偶数位(从\(1\)开始) 是否全为\(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);
string s;
cin >> s;
bool ok = true;
for (int i = 1; i < s.size(); i += 2) {
ok &= (s[i] == '0');
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Round-Robin Tournament (abc323 B)
题目大意
给定\(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;
cin >> n;
vector<int> a(n);
for (auto& i : a) {
string s;
cin >> s;
i = count(s.begin(), s.end(), 'o');
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) {
if (a[x] != a[y])
return a[x] > a[y];
else
return x < y;
});
for (auto& i : id)
cout << i + 1 << ' ';
return 0;
}
C - World Tour Finals (abc323 C)
题目大意
给定每道题的分数,以及每个人的通过情况,每个人的得分为解决题目的分的和,其中第\(i\)个人还有\(i\)的额外加分。
对于每个人,问最少还得解决多少道题,才能成为第一。
解题思路
因为范围只有\(100\),可以采取最朴素的做法,先统计每个人的分数,得到当前最高的分数。
然后对于每个人,从未通过题目的分数,排个序,大到小依次解决获得分数,看何时超过最高分。
由于每个人有不同的额外得分,所以不会有同分。
时间复杂度为 \(O(n^2\log n)\)
也可以每次遍历未通过的题目,找分数最大的,这样复杂度为\(O(n^3)\)同样可以通过。
神奇的代码
#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, m;
cin >> n >> m;
vector<int> a(m);
for (auto& i : a)
cin >> i;
vector<int> score(n);
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
score[i] = i + 1;
for (int j = 0; j < m; ++j)
score[i] += a[j] * (s[i][j] == 'o');
}
int maxx = *max_element(score.begin(), score.end());
for (int i = 0; i < n; ++i) {
if (score[i] == maxx) {
cout << 0 << '\n';
continue;
}
int dis = maxx - score[i];
vector<int> unsolve;
for (int j = 0; j < m; ++j)
if (s[i][j] == 'x')
unsolve.push_back(a[j]);
sort(unsolve.begin(), unsolve.end(), greater<int>());
int ans = 0;
for (; dis > 0 && ans < unsolve.size(); ++ans) {
dis -= unsolve[ans];
}
cout << ans << '\n';
}
return 0;
}
D - Merge Slimes (abc323 D)
题目大意
有\(n\)类数字,第 \(i\)类数字为 \(s_i\),有 \(c_i\)个。
同类数字可以两两合并,得到一个\(s_i + s_i\)数字。
问最后剩下的数字数量。
解题思路
因为数字很大,可以考虑用map
存对应数的数量。
但是不能遍历\(map\)的每个元素,然后合并,累计到更大的数里。因为如果更大的数不存在,会插入到 \(map\)中,从而可能导致原因迭代器失效。
但考虑到一类元素不断合并,最终停止时,其个数一定是\(1\),就不用管它了,我们只考虑一开始的那些类别。 因此事先用set
储存原来的数的类别。
然后对于set
的每一个类别,从小到大考虑不断合并,直到数量变为\(1\)。由于每次合并数量都除以 \(2\)。因此每一类最多 \(\log\)次就结束了。
最后看 map
里剩余数的个数。
神奇的代码
#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;
unordered_map<LL, int> cnt;
set<int> a;
for (int i = 0; i < n; ++i) {
int s, c;
cin >> s >> c;
cnt[s] = c;
a.insert(s);
}
int ans = 0;
for (auto& i : a) {
int sum = 0;
for (LL j = i; true; j = j + j) {
sum = (sum + cnt[j]);
if (sum < 2) {
cnt[j] = sum;
break;
}
cnt[j] = sum % 2;
sum /= 2;
}
}
for (auto& i : cnt) {
ans += i.second;
}
cout << ans << '\n';
return 0;
}
E - Playlist (abc323 E)
题目大意
给定\(n\)首歌的播放时间。
从第\(0\)秒,随机选一首歌播放。当一首歌播放完后,立刻随机选下一首歌播放。
问第 \(X + 0.5\)秒 时播放第一首歌的概率。
解题思路
假设第一首歌的播放时长为\(t\)。
那么要在 \(X + 0.5\)秒播放第一首歌,则要求第一首歌在第 \(X, X - 1, X - 2, ..., X - t + 1\)秒中的一秒开始播放。
而如果我知道能够在第 \(X,X-1,X-2,...,X-t + 1\)秒开始播放的概率(或者说这些时刻恰好播放完的概率),那么这些概率的和,再乘以\(\frac{1}{n}\)(即选到第一首歌播放的概率),就是答案。
设 \(dp[i]\)表示能够在第 \(i\)秒开始播放的概率,转移则枚举之前播放的是哪一首歌,比如第 \(j\)首,播放时长为\(t_j\),则有 \(dp[i] += dp[i - t_j] \times \frac{1}{n}\)。
即 \(dp[i] = \sum_{t_j \leq i} dp[i - t_j] \times \frac{1}{n}\)
初始条件就是\(dp[0] = 1\)。即第 \(0\)秒肯定能够播放一首歌。
最后答案就是\(\sum_{i = x - t + 1}^{x} dp[i] \times \frac{1}{n}\)
时间复杂度为 \(O(n^2)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int qpower(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) {
ret = 1ll * ret * a % mo;
}
a = 1ll * a * a % mo;
b >>= 1;
}
return ret;
}
int inv(int x) { return qpower(x, mo - 2); }
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, x;
cin >> n >> x;
vector<int> t(n);
for (auto& i : t) {
cin >> i;
}
vector<int> dp(x + 1);
int one = inv(n);
dp[0] = 1;
for (int i = 1; i <= x; ++i) {
int sum = 0;
for (auto& j : t) {
if (i < j)
continue;
sum += 1ll * dp[i - j] * one % mo;
if (sum >= mo)
sum -= mo;
}
dp[i] = sum;
}
int ans = 0;
for (int i = max(0, x - t[0] + 1); i <= x; ++i) {
ans = ans + dp[i];
if (ans >= mo)
ans -= mo;
}
ans = 1ll * ans * one % mo;
cout << ans << '\n';
return 0;
}
F - Push and Carry (abc323 F)
题目大意
二维平面,推箱子。给定你的位置,箱子位置,目标位置,一次上下左右移动一格,问把箱子推到目标位置的最小步数。
解题思路
虽然坐标范围挺大的,但实际上决策只有两种。枚举两种决策分别计算下步数取最小即可。
假设箱子在左下,目标位置在右上。很显然,推箱子只有两个决策:
- 先向上推,再向右推。
- 先向右推,再向上推。
而为了把箱子向上推,那么事先要走到箱子的下方。同理向右推,要事先走到箱子的左方。
最终步数的贡献来自于:
- 起始位置走到推箱子的位置的步数
- 推动箱子的步数(固定的,为箱子位置到目标位置的曼哈顿距离)
- 中间转动方向时额外需要的步数(固定的,为\(2\)),比如向上推时,你在箱子下方,然后要向右推,你需要走到箱子的左方,步数为\(2\)。
因此只有第一个位置需要枚举,事实上就两种情况:
- 先向上推,则求出初始位置到箱子下方的距离
- 先向右推,则求出初始位置到箱子左方的距离
而这个距离事实上也是个曼哈顿距离,因为除了箱子别无障碍,两种方式到达指定位置中,必有一种是畅通无阻的。
当注意一种情况,当初始位置、箱子位置、到达箱子的位置处于同一条线,且箱子位置在中间的时候,此时并不是畅通无阻的,必须要偏移一下。比如初始位置在左边,箱子在中间,为了把箱子往左推,你要跑到箱子右边,但不能穿过箱子,此时的步数在曼哈顿距离的基础上还要\(+2\),即先向上走或向下走,再走回来。
代码里两种情况的分别考虑就相当于交换了下两个坐标,再考虑一次。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int sign(LL x) {
if (x == 0)
return 0;
else if (x > 0)
return 1;
else
return -1;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
array<array<LL, 2>, 3> pos;
for (auto& i : pos)
for (auto& j : i)
cin >> j;
auto& [player, box, target] = pos;
auto dis = [&](const array<LL, 2>& a, const array<LL, 2>& b) {
return abs(a[0] - b[0]) + abs(a[1] - b[1]);
};
LL bound = dis(box, target);
auto in_middle = [](LL l, LL m, LL r) {
LL L = min(l, r), R = max(l, r);
return m > L && m < R;
};
auto solve = [&]() {
LL ret = bound;
int d = sign(box[0] - target[0]);
if (d == 0)
return numeric_limits<LL>::max();
array<LL, 2> t1 = box;
t1[0] += d;
ret += dis(player, t1);
if ((player[0] == t1[0] && player[0] == box[0] &&
in_middle(player[1], box[1], t1[1])) ||
(player[1] == t1[1] && player[1] == box[1] &&
in_middle(player[0], box[0], t1[0])))
ret += 2;
if (box[1] != target[1])
ret += 2;
return ret;
};
LL ans = solve();
for (auto& i : pos)
swap(i[0], i[1]);
ans = min(ans, solve());
cout << ans << '\n';
return 0;
}
G - Inversion of Tree (abc323 G)
题目大意
给定一个排列\(p\)。问有多少种形态的树,满足对于树上的任意一条边\((u,v)(u < v)\),有 \(p_u > p_v\)
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 323beginner atcoder contest 323 题解323 beginner atcoder 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