Codeforces Round 1016 (Div. 3)题解
题目地址https://codeforces.com/contest/2093
锐评
在所有题意都理解正确的情况下，整体难度不算太难。但是偏偏存在F这么恶心的题意，样例都不带解释一下的，根本看不懂题。D题也恶心，在于递归过程的拆分，需要点数学，跟打印递归定义的图形一样，写麻了，好在过了。E题居然卡双 \(log\) 做法常数，也是恶心。反而是G题很典，太裸了，可惜被D防住了，根本没看到G题。再次陷入“看完所有题不会写，不看完所有题却会写”的魔咒。主要还是自己太菜了，打破不了这个魔咒，大佬们就没这个烦恼。
题解
Problem A. Ideal Generator
题目大意
由 \(k\) 个正整数组成的数组 \(a\) 在 \( = \) 的情况下称为回文数组（其实就是正着读反着读是一样的）。例如，数组 \(\) 和 \(\) 是回文数组，而数组 \(\) 和 \(\) 不是回文数组。
如果任何整数 \(n\) ( \(n \geq k\) ) 都可以表示为一个长度正好为 \(k\) 的回文数组的元素之和，我们就称这个数 \(k\) 为理想生成数。数组中的每个元素都必须大于 \(0\) 。
例如，数字 \(1\) 是一个理想生成数，因为任何自然数 \(n\) 都可以用数组 \(\) 生成。然而，数字 \(2\) 并不是一个理想生成数，因为不存在长度为 \(2\) 的和为 \(3\) 的回文数组。
请判断给定的数字 \(k\) 是否是理想生成数。
题解思路：思维
先通过样例观察，发现奇数可以，偶数不行。开始验证，假如和为 \(k\) ，那么全部数组元素为 \(1\) 即可，假如和为 \(k + 1\) ，那么全部数组元素为 \(1\) 的基础上，有一个数要加上 \(1\) 还要是回文数组，那么只能放在最中间的位置上了，不然所放位置对称的那一个位置就不相等了。又因为 \(n\) 是连续的，所以差值为 \(1\) 只有数组长度是奇数才能满足，每次都在最中间位置加上 \(1\) 。时间复杂度为 \(O(1)\) 。
参考代码（C++）
#include <bits/stdc++.h>
using namespace std;
int n;
void solve() {
cin >> n;
cout << ((n & 1) ? "YES\n" : "NO\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}Problem B. Expensive Number
题目大意
正整数 \(n\) 的代价被定义为数字 \(n\) 除以其数位之和的结果。
例如，数字 \(104\) 的代价是 \(\frac{104}{1 + 0 + 4} = 20.8\) ，数字 \(111\) 的代价是 \(\frac{111}{1 + 1 + 1} = 37\) 。
给你一个不包含前导零的正整数 \(n\) 。你可以从数字 \(n\) 中删除任意数位(包括不删除)，这样剩下的数字至少包含一位数，并且严格大于零。剩下的数字不能重新排列。因此，你可能得到一个前导为零的数字。
例如，给你一个数字 \(103554\) 。如果去掉 \(1\) 、 \(4\) 和一个数字 \(5\) ，最后得到的数字是 \(035\) ，其代价是 \(\frac{035}{0 + 3 + 5} = 4.375\) 。
为了使代价最小，你需要从这个数字中删除最少多少个数字？
题解思路：贪心
首先，一个数字的数位之和是不可能大于这个数字的，最多和它相等。那么代价最小意味着什么？显然就是相等。所以只有一位数字时代价达到最小，代价为 \(1\) 。因为题目删除数位后允许有前导 \(0\) ，所以选定某个数字前面的 \(0\) 可以不删除。又因为题目要求删除后组成的这个数必须严格大于 \(0\) ，所以我们要找一个非 \(0\) 数位。因为前导 \(0\) 可以保留，后导 \(0\) 不能保留（保留就不是个位数了），所以我们倒着枚举，找到第一个非 \(0\) 数位位置，将这个位置前面的非 \(0\) 数位删除以及后面的数位删除，删除的数位个数即是答案。时间复杂度为 \(O(n)\) 。
参考代码（C++）
#include <bits/stdc++.h>
using namespace std;
string str;
void solve() {
cin >> str;
int n = str.size();
int id = n - 1;
for (int i = n - 1; i >= 0; --i)
if (str != '0') {
id = i;
break;
}
int ans = n - 1 - id;
for (int i = id - 1; i >= 0; --i)
if (str != '0')
++ans;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}Problem C. Simple Repetition
题目大意
帕夏喜欢质数！为了找到生成质数的新方法，他再次对互联网上的一种算法产生了兴趣：
[*]要得到一个新数字 \(y\) ，重复 \(k\) 次数字 \(x\) 的十进制表示 \(x\) (不含前导零)。
例如， \(x = 52\) 和 \(k = 3\) 可以得到 \(y = 525252\) ， \(x = 6\) 和 \(k = 7\) 可以得到 \(y = 6666666\) 。
帕夏非常希望得到的数字 \(y\) 是质数，但他还不知道如何检验这种算法生成的数字的质性。请帮助帕夏，告诉他 \(y\) 是否是质数！
如果一个整数 x 只有 2 个不同的除数 1 和 x ，那么这个整数 x 就是质数。例如， 13 是质数，因为它只有 2 个除数： 1 和 13 。请注意，数字 1 不是质数，因为它只有一个除数。
题解思路：思维/分类讨论
我们来一一分析下。
[*]\(k = 1\) ，显然只需要判定 \(x\) 是否质数。
[*]\(k \gt 1\) ，即 \(x\) 至少重复了 \(2\) 次，设 \(x\) 有 \(n\) 个数位，那么 \(y\) 显然有一个除数 \(x\) ，使得 \(\frac{y}{x} = a_1 \underbrace{0 \cdots 0}_{n - 1个} a_2 \underbrace{0 \cdots 0}_{n - 1个} \dots a_k\) ，其中 \(a_i = 1, 1 \leq i \leq k\) 。那么只要\(1 \lt x \lt y\) ， \(y\) 必然不是质数，显然 \(x \lt y\) 必然成立，所以只需要再单独判断一下 \(x\) 为 \(1\) 的情况即可。
根据上面的分析，问题得解。时间复杂度为 \(O(1)\) 。
参考代码（C++）
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool check(int x) {
if (x < 2)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
void solve() {
cin >> n >> m;
if (m == 1)
cout << (check(n) ? "YES\n" : "NO\n");
else if (n == 1) {
int x = 0;
for (int i = 0; i < m; ++i)
x = x * 10 + 1;
cout << (check(x) ? "YES\n" : "NO\n");
} else
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}单 \(log\) 通过代码。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, q;
ll dfs1(int cur, int l, int r, int x, int y) {
// cout << "dfs1:" << cur << ':' << l << ':' << r << ':' << x << ':' << y << '\n';
if (l == x && r == y)
return 1;
ll dt = 1LL << (cur - 1);
ll dd = dt * dt;
if (x >= l + dt && y >= r + dt)
return dd + dfs1(cur - 1, l + dt, r + dt, x, y);
if (x >= l + dt)
return (dd << 1) + dfs1(cur - 1, l + dt, r, x, y);
if (y >= r + dt)
return 3 * dd + dfs1(cur - 1, l, r + dt, x, y);
return dfs1(cur - 1, l, r, x, y);
}
pii dfs2(int cur, int l, int r, ll d) {
// cout << "dfs2:" << cur << ':' << l << ':' << r << ':' << d << '\n';
if (d == 1)
return {l, r};
ll dt = 1LL << (cur - 1);
ll dd = dt * dt;
if (d > 3 * dd)
return dfs2(cur - 1, l, r + dt, d - 3 * dd);
if (d > (dd << 1))
return dfs2(cur - 1, l + dt, r, d - (dd << 1));
if (d > dd)
return dfs2(cur - 1, l + dt, r + dt, d - dd);
return dfs2(cur - 1, l, r, d);
}
void solve() {
cin >> n >> q;
string op;
int x, y;
ll d;
while (q--) {
cin >> op;
if (op == "->") {
cin >> x >> y;
cout << dfs1(n, 1, 1, x, y) << '\n';
} else {
cin >> d;
pii ans = dfs2(n, 1, 1, d);
cout << ans.first << ' ' << ans.second << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}Problem F. Hackers and Neural Networks
题目大意
黑客们再次试图利用神经网络的输出创建娱乐短语。这一次，他们想获得长度为 \(n\) 的字符串数组 \(a\) 。
最初，他们有一个长度为 \(n\) 的数组 \(c\) ，其中充满了空白，用符号 \(*\) 表示。因此，如果 \(n = 4\) ，则初始值为 \(c=[*, *, *, *]\) 。
黑客可以访问 \(m\) 个神经网络，每个神经网络都有自己的请求答案版本--长度为 \(n\) 的字符串数组 \(b_i\) 。
黑客试图通过以下操作从数组 \(c\) 中获取数组 \(a\) ：
[*]选择神经网络 \(i\) ，对数组 \(c\) 执行下一步操作：选择一个随机的空白，例如在位置 \(j\) 处，将 \(c_j\) 替换为 \(b_{i, j}\) 。
例如，如果选择了第一个神经网络 \(b_1 = [\text{«I»}, \text{«love»}, \text{«apples»}]\) ，当前 \(c = [*, \text{«like»}, *]\) ，那么在对第一个神经网络进行操作后， \(c\) 可能会变成 \([\text{«I»}, \text{«like»}, *]\) 或 \([*, \text{«like»}, \text{«apples»}]\) 。
[*]选择位置 \(j\) 并将 \(c_j\) 替换为空白。
不幸的是，由于黑客访问神经网络的方式，他们只能在所有操作完成后才能看到修改后的数组 \(c\) ，因此他们必须事先指定整个操作序列。
然而，神经网络的随机行为可能会导致永远无法获得所需的数组，或者获得所需的数组需要过多的操作。
因此，黑客们希望您能帮助他们选择一个操作序列，以保证在最少的操作次数内获得数组 \(a\) 。
更具体地说，如果存在一个操作序列可以保证从数组 \(c\) 中获得数组 \(a\) ，那么在所有这样的序列中，找出一个操作次数最少的序列，并输出其中的操作次数。
如果没有将数组 \(c\) 转换成数组 \(a\) 的操作序列，则输出 \(-1\) 。
题解思路：贪心
题意真的很长且很拉，真的看完好像不知道要求什么？让我们再细细品味一下！反正就是进行两个操作嘛，只要对应位置的字符串不对就一定要继续操作。只要操作，那么操作次数必然会增加。
假如某个操作后，某个位置已经是正确的，下一次操作你会不会去改它？显然不会了，不然你还得再至少进行一次操作二以及至少随机一次操作一，而且随机后不一定是对的，何必呢？
如果所有位置都是空的，你会不会进行操作二？显然也不会，白白浪费一次操作嘛。所以第一次操作肯定是操作一，这是个随机过程。
通过上面的分析，我们唯一能决定的就是可以选择跑哪个神经网络。从概率论角度来说，我们当然希望选择命中概率更高的，这样所得的期望就越大，后续所需要的操作就更少。所以第一次操作就至关重要了，我们就选命中概率最大的神经网络，这样我们就能保证 \(n\) 次操作后，随机正确位置最大。这样所有位置都被填满了，最后对不正确的位置，我们只需要先执行一次操作二，再找到一个神经网络，其对应位置存在正确字符串，因为只会空白位置随机，而当前空白位置只有一个，显然这是一个必然事件。
上面操作一定是最优的吗？一定的。假设你选择某个神经网络的命中率是 \(\frac{x}{y}\) ，你把其他所有的神经网络全部组合起来，命中率形如 \(\frac{x + a}{y + b}\) ，其不可能更大。
对于不存在的情况，显然所有对应位置都没有目标串，就无法做到。时间复杂度为 \(O(mn \max(|b_{i, j}|))\) 。
参考代码（C++）
#include using namespace std;using ll = long long;using pii = pair;const int maxn = 505;string p, str;int cntr, cntc;int n, m;void solve() { cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> p; cntc = 0; } for (int i = 0; i < m; ++i) { cntr = 0; for(int j = 0; j < n; ++j) { cin >> str; if (str == p) { ++cntc; ++cntr; } } } for (int i = 0; i < n; ++i) if (cntc == 0) { cout
页:
[1]