3 月 19 日测试题解
原来这就是 AK 的滋味吗，不过，我却完全没感到开心呢。
T1
题意
给出两个整数 \(a\)，\(b\)，重复以下操作直到 \(a = b\)：
- 设 \(a > b\)，否则交换 \(a\) 与 \(b\)，然后让 \(a\) 减去 \(b\)。
输出操作次数。
\(a, b \le 10^{18}\)。
思路
\(\text{100pts}\)
毫无难度的题目，其实就是在模拟辗转相除法，一样的方法再加个计数就行了，只不过我没写递归的。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
i64 a, b;
std::cin >> a >> b;
i64 ans = 0;
while (a != b) {
if (a < b) {
std::swap(a, b);
}
if (a % b == 0) {
ans += a / b - 1;
break;
}
ans += a / b;
a -= a / b * b;
}
std::cout << ans << "\n";
return;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
T2
题意
给出五个包含 \(n\) 个元素的数组，问是否存在一种方法，从每个数组中选出一个数并使得五个数之和等于 \(0\)。
对于 \(30\%\) 的数据，\(n \le 20\)；
对于 \(100\%\) 的数据，\(n \le 200\)，数组中元素的最大值不超过 \(10^8\)。
思路
\(\text{30pts}\)
暴力枚举，时间复杂度为 \(O(n^5)\)。
\(\text{100pts}\)
话说折半都考第几次了。
考虑折半搜索，先计算出前边两个数组的和，再算后边两个的，然后枚举一下就做完了，我用的哈希表，期望的时间复杂度为 \(O(n^3)\)。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<std::vector<int>> a(5, std::vector<int>(n));
for (int i = 0; i < 5; i++) {
for (int j = 0; j < n; j++) {
std::cin >> a[i][j];
}
}
std::unordered_set<int> sum1, sum2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[0][i] + a[1][j];
sum1.insert(cur);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[2][i] + a[3][j];
sum2.insert(cur);
}
}
for (auto i : sum1) {
for (auto j : sum2) {
for (auto k : a[4]) {
if (i + j + k == 0) {
std::cout << "YES\n";
return 0;
}
}
}
}
std::cout << "NO\n";
return 0;
}
T3
题意
给定一个长度为 \(n\) 的序列 \(a\)，你可以任意选取序列中的两个相同数字 \(i\) ，将它们删去后，将其合并为 \(2i\) 后再加入序列，问有多少个 \(a\) 的子序列满足通过合并能够得到 2048。
对于 \(40\%\) 的数据，\(n \le 20\)；
对于 \(100\%\) 的数据，\(n \le 10^5\)，\(a_i \le 2048\)。
思路
\(\text{40pts}\)
我们考虑二进制枚举子序列在判断其能不能产生 2048。
如何快速判断呢？首先意识到不是 2 的幂的数字并不重要，因为它们无论怎么合并都不可能产生 2048，因此我们只需要记录它们的个数就好了。将这些多余的数字删去后，我们可以这样想：合成 2048 一共需要 \(2^{11}\) 个 1，那么是不是只要一个子序列的和超过了 \(2^{11}\)，就一定可以合并出 2048 呢？
更一般地，我们有命题如下：
任意地给定一个只包含 \(2^i\) 的序列 \(a\)，若 \(\sum_{j \in a}{j} \ge 2^k\) 且有 \(\forall j \in a, j \lt 2^k\)，则可以通过合并的方式得到 \(2^k\)，其中 \(i, k \in \mathbb{N}\)。
只要这个命题是真的，我们就有了一种快速判断序列合法性的方法。事实上，这个命题确实为真。我们可以通过如下方法证明：
显然我们有如下结论：
对于一个只包含 \(2^i\) 的序列 \(a\)，若 \(\sum_{j \in a}j \ge 2^k\) 且有 \(\forall j \in a, j \lt 2^k\)，则至少存在一对 \(m, n\) 使得 \(a_m = a_n\)。
通过 \(\sum_{i = 0}^{n} = 2^{n + 1} - 1\)，这个结论可以证明。
那么显然，\(a_m\) 与 \(a_n\) 是可以合成的，设 \(m\) 与 \(n\) 是满足条件且 \(a_m\) 最小的一对，我们期望的是产生连锁反应，即可以一直向上合成。会不会出现无法再向上合成的情况呢？其实是不会的。因为如果不能向上合成，那么只有两种情况：
- \(\sum_{j \in a} j < 2^k\)
- 至少存在一对 \(p\) 与 \(q\) 使得 \(a_p = a_q\) 并且 \(a_p \ge a_m\)。
第二种情况是好说的，如果存在这么一对 \(p\) 与 \(q\) 的话，那你为什么还要从 \(m\) 与 \(n\) 开始向上合成呢？这是不优的。因此，我们可以将 \(a_p\) 与 \(a_q\) 作为新的起点向上合成。
而为什么只有这两种情况呢？因为 \(a_p \ge a_m\)，所以如果不存在这样的 \(p\) 与 \(q\) 并且还有数字缺失的话，那么肯定是不符合 \(\sum_{j \in a}j \ge 2^k\) 的。
那么我们可以通过这种方式得到 \(2^k\)。
证明思路很混乱，看看就行了，没必要深究。
那么我们只需要枚举出所有的子序列，就可以拿到 \(\text{40pts}\) 了，哦对了，不要忘掉被删掉的数字。
\(\text{100pts}\)
上边的思路是没错的，我们需要把枚举的部分换成一个 01 背包。
这里有一个小技巧，如果直接算大于等于 2048 的个数不是很好算，但是我们可以先把小于 2048 的个数算出来，总的子序列个数为 \(2^n\)，然后做下减法就好了，时间复杂度为 \(O(2048n)\)，可以接受。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
i64 fastPow(i64 base, i64 pow, i64 mod) {
i64 res = 1;
while (pow) {
if (pow & 1) {
(res *= base) %= mod;
}
(base *= base) %= mod;
pow >>= 1;
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
static const int MOD = 998244353, M = 1 << 11;
int n;
std::cin >> n;
std::vector<int> a;
int rst = 0;
for (int i = 0; i < n; i++) {
int cur;
std::cin >> cur;
if (__builtin_popcount(cur) == 1) {
a.push_back(cur);
} else {
rst++;
}
}
if (!a.size()) {
std::cout << 0 << "\n";
return 0;
}
std::vector<int> f(M + 1);
f[0] = 1;
for (int i = 0; i < a.size(); i++) {
for (int j = M; j >= a[i]; j--) {
(f[j] += f[j - a[i]]) %= MOD;
}
}
for (int i = 1; i <= M; i++) {
(f[i] += f[i - 1]) %= MOD;
}
i64 ans = (fastPow(2, a.size(), MOD) - f[M - 1] + MOD) % MOD;
(ans *= fastPow(2, rst, MOD)) %= MOD;
std::cout << ans << "\n";
return 0;
}