AtCoder Beginner Contest 321
A - 321-like Checker (abc321 A)
题目大意
给定一个数，问从高位到低位，数字是不是递减的。
解题思路
可以以字符串读入，然后依次判断即可。
神奇的代码
#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;
auto ok = [&]() {
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i + 1] >= s[i])
return false;
}
return true;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Cutoff (abc321 B)
题目大意
给定\(n-1\)个数字，问最后一个数字最少是多少，使得你的分数不小于 \(x\)。
数字在 \([0,100]\)之间。分数是去掉最低最高后的和。
解题思路
因为范围不大，直接枚举最后一个数，找最大最小，然后求分数判断即可。时间复杂度是\(O(100^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, x;
cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n - 1; ++i)
cin >> a[i];
int ans = 0;
auto ok = [&]() {
auto tmp = a;
sort(tmp.begin(), tmp.end());
int sum =
accumulate(tmp.begin(), tmp.end(), 0) - tmp.front() - tmp.back();
return sum >= x;
};
for (; ans <= 100; ++ans) {
a[n - 1] = ans;
if (ok())
break;
}
if (ans == 101)
ans = -1;
cout << ans << '\n';
return 0;
}
C - 321-like Searcher (abc321 C)
题目大意
给定\(k\)，问\(321-like\)的第 \(k\)小的数是多少。
\(321-like\)就是第一题的定义，从高位到低位逐数字递减。
解题思路
最大的是\(9876543210\)，可以猜测数不多，直接搜索全部数出来，然后排序看第\(k\) 个是多少即可。
神奇的代码
#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 k;
cin >> k;
LL s = 0;
vector<LL> ans;
function<void(int)> dfs = [&](int x) {
s = s * 10 + x;
ans.push_back(s);
for (int i = x - 1; i >= 0; --i)
dfs(i);
s /= 10;
};
for (int i = 9; i >= 0; --i) {
dfs(i);
}
sort(ans.begin(), ans.end());
cout << ans[k] << '\n';
return 0;
}
D - Set Menu (abc321 D)
题目大意
给定两个数组\(a,b\)和一个数\(p\)，各从中取一个数\(x,y\)，得到贡献 \(\min(x+y, p)\) 。问所有取法的贡献和。
解题思路
对数组\(b\)排序，枚举数组 \(a\)，那么小于 \(p-a\)的 \(b\)的贡献是 \(a+b\)，其余的贡献是 \(p\)，因此二分找到这个界限，分别计算这两类的贡献和即可，前者是个关于\(b\)的前缀和，后者就是一个数组\(b\)中 \(\geq p-a\)的数量的统计。时间复杂度是 \(O(n\log m)\)。
也可以对\(a,b\)都排序，此时\(a\)枚举从大到小， \(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);
int n, m;
LL p;
cin >> n >> m >> p;
vector<LL> a(n), b(m);
vector<LL> sumb(m);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
sort(b.begin(), b.end());
partial_sum(b.begin(), b.end(), sumb.begin());
LL ans = 0;
for (auto& i : a) {
LL r = p - i;
auto cnt = lower_bound(b.begin(), b.end(), r) - b.begin();
ans += 1ll * i * cnt + (cnt ? sumb[cnt - 1] : 0) + 1ll * p * (m - cnt);
}
cout << ans << '\n';
return 0;
}
E - Complete Binary Tree (abc321 E)
题目大意
给定一棵完全二叉树，问与点\(x\)的距离为\(k\)的个数。
有 \(t\)组。
解题思路
考虑点\(5\)距离为 \(k\)的点都在哪。
首先在以该点的子树内，深度为 \(k\)的点有 \(2^k\)（起始为\(0\)）， 对应的标号都可以求出来，这样可以判断在\(n\)内的标号有多少个。
然后考虑该点的父亲的另一个节点（点\(4\)）的子树内，此时我们要求的深度是 \(2^{k-2}\)的点的个数。
然后考虑该点的父亲的父亲的另一个节点（点\(3\)）的子树内，此时我们要求的深度是\(2^{k-3}\)的点的个数。
不断往父亲考虑，因为每次往父亲走，点标号都会除以 \(2\)，最多 \(\log\)次就考虑完了。
总的复杂度是 \(O(t\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 t;
cin >> t;
auto solve = [&](LL x, LL k, LL n) {
if (k < 0)
return 0ll;
if (k >= 64)
return 0ll;
__int128 num = (1ll << k), l = x;
l = (l << k);
__int128 r = l + num - 1;
if (l > n)
return 0ll;
LL ret = min(r, (__int128)n) - l + 1;
return ret;
};
while (t--) {
LL n, x, k;
cin >> n >> x >> k;
LL ans = 0;
if (k)
ans += solve(x, k, n);
while (x > 1 && k > 0) {
--k;
ans += solve((x ^ 1), k - 1, n);
x /= 2;
}
if (x && k == 0)
ans++;
cout << ans << '\n';
}
return 0;
}
F - #(subset sum = K) with Add and Erase (abc321 F)
题目大意
箱子，放球，拿球，球上有数，各不相同。
每次操作后，问里面球数和为\(k\)的方案数。
解题思路
不考虑拿走球的操作，每次放球，求方案数，就是一个经典的\(0/1\)背包。
设 \(dp[i]\)表示和为 \(j\)的方案数，考虑选不选这个球（其数字为\(x\)），则有 \(dp[i] = dp[i] + dp[i - x]\)
现在拿走这个球，得从中剔除选了这个球的方案数。
设\(dp2[i]\)表示不选该球，和为 \(i\)的方案数。由于 \(dp[i]\)的方案包括两部分：选了该球和没选该球的。只要减去选了该球的方案数，那就是没选该球的方案数。而选了该球的方案数，其实就是 \(dp2[i-x]\)，即选了这个球后，剩下的 \(i-x\)就是由不选该球的方案数组成，这恰好是我们定义的 \(dp2[i-x]\)的定义。
于是 \(dp2[i] = dp[i] - dp2[i - x]\)转移式即可。
时间复杂度是 \(O(qn)\)。
这其实是最经典的退背包问题。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q, k;
cin >> q >> k;
vector<int> dp(k + 1, 0);
dp[0] = 1;
while (q--) {
string op;
int x;
cin >> op >> x;
if (op[0] == '+') {
for (int i = k; i >= x; --i) {
dp[i] += dp[i - x];
if (dp[i] >= mo)
dp[i] -= mo;
}
} else {
vector<int> dp2(k + 1, 0);
for (int i = 0; i <= k; ++i) {
if (i < x) {
dp2[i] = dp[i];
} else {
dp2[i] = dp[i] - dp2[i - x];
if (dp2[i] < 0)
dp2[i] += mo;
}
}
dp.swap(dp2);
}
cout << dp[k] << '\n';
}
return 0;
}
G - Electric Circuit (abc321 G)
题目大意
给定\(n\)个部件和 \(m\)条线。部件有接口，有红蓝两色，数量都是\(m\)。一条线链接的两个接口必须不同颜色，但可以同个部件。
将部件视为点，线视为边，随机连线，问联通块的期望个数。
解题思路
<++>
神奇的代码