Codeforces Round 1016 (Div. 3)

慷规扣 · 2025-6-7 10:36:08

A. Ideal Generator

我们称一个由 \(k\) 个正整数组成的数组 \(a\) 为回文数组，如果满足

\[[a_1,a_2,\dots,a_k]=[a_k,a_{k-1},\dots,a_1].\]
例如，数组 \([1,2,1]\) 和 \([5,1,1,5]\) 是回文数组，而数组 \([1,2,3]\) 和 \([21,12]\) 则不是。
我们称一个数 \(k\) 为“理想生成器”，如果任意整数 \(n\) （\(n \ge k\)）都可以表示为一个长度恰为 \(k\) 的回文数组元素之和。该数组的每个元素都必须大于 \(0\)。
例如，数 \(1\) 是一个理想生成器，因为任何自然数 \(n\) 都可以通过数组 \([n]\) 来生成。然而，数 \(2\) 不是理想生成器 —— 没有长度为 \(2\) 的回文数组的元素之和等于 \(3\)。
判断给定的数 \(k\) 是否为理想生成器。
\(k \leq 1000\)

由于 \(a_i = a_{k-i+1}\)，当 \(k\) 为偶数时数组和不能为奇数，为奇数时是理想生成器。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
puts(n & 1 ? "YES" : "NO");
}
return 0;
}

复制代码

B. Expensive Number

正整数 \(n\) 的 “代价” 定义为 \(n\) 除以它的各位数字之和的结果。
例如，数字 \(104\) 的代价为 \(\frac{104}{1+0+4}=\frac{104}{5}=20.8\)，而数字 \(111\) 的代价为 \(\frac{111}{1+1+1}=\frac{111}{3}=37\)。
现给定一个不含前导零的正整数 \(n\)。你可以从数字 \(n\) 中移除任意数量的数字（可以不移除任何数字），要求剩下的数字至少有一位且严格大于零。注意，剩下的数字不能重新排列，因此，最终得到的数字可能会有前导零。
\(n \leq 10^{100}\)

最小代价为 \(1\)，最优做法为保留最低位的非 \(0\) 数，移除掉其余所有非 \(0\) 数以及数位比该位高的 \(0\)。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
char s[N];
int main() {
int T;
cin >> T;
while (T--) {
scanf("%s", s + 1);
n = strlen(s + 1);
int c = 0;
bool flag = 0;
for (int i = n; i; i--) {
flag |= s[i] != '0';
c += flag && s[i] == '0';
}
printf("%d\n", n - c - 1);
}
return 0;
}

复制代码

C. Simple Repetition

帕沙热爱素数！在他再次尝试寻找生成素数的新方法时，他对互联网上发现的一种算法产生了兴趣：
为了得到一个新数字 \(y\)，将数字 \(x\) 的十进制表示（不含前导零）重复 \(k\) 次。
例如，当 \(x=52\) 且 \(k=3\) 时，得到 \(y=525252\)；当 \(x=6\) 且 \(k=7\) 时，得到 \(y=6666666\)。
\(x \leq 10^9,1 \leq k \leq 7\)

如果 \(x\) 不为 \(1\) 且 \(k\) 大于 \(1\)，此时 \(x\) 必定是 \(y\) 的因数。当 \(x\) 为 \(1\) 时，只有在 \(k\) 为 \(2\) 时 \(y\) 为质数。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
if (n == 1 && m == 2) {
puts("YES");
} else if (m > 1) {
puts("NO");
} else {
bool flag = n == 1;
for (ll i = 2; i * i <= n; i++)
if (n % i == 0) {
flag = 1;
}
puts(flag ? "NO" : "YES");
}
}
return 0;
}

复制代码

E. Min Max MEX

给定一个长度为 \(n\) 的数组 \(a\) 以及一个数字 \(k\)。
一个子数组被定义为数组中由一个或多个连续元素组成的序列。你需要将数组 \(a\) 划分为 \(k\) 个不重叠的子数组 \(b_1, b_2, \dots, b_k\)，要求这些子数组的并集等于整个数组 \(a\)。此外，你需要最大化一个值 \(x\)，其中 \(x\) 等于所有子数组的 MEX 值的最小值，即

\[x = \min\{\text{MEX}(b_i) \mid 1\le i\le k\}.\]
\(1 \leq k \leq n \leq 2 \times 10^5\)

显然 \(x\) 可以二分，考虑在固定了 \(x\) 后如何判断是否可行。对于两个相邻的子数组，它们合并后的 \(\operatorname{MEX}\) 一定不小于合并前的 \(\operatorname{MEX}\)，那么如果存在一种方式将 \(a\) 划分成 \(y(y>1)\) 段且每一段的 \(\operatorname{MEX}\) 都不小于 \(x\)，则一定存在一种方式能将 \(a\) 划分成 \(y - 1\) 段且每一段的 \(\operatorname{MEX}\) 都不小于 \(x\)，因此应该尽可能地将数组分成更多段。从左到右遍历数组，维护当前子数组的 \(\operatorname{MEX}\)，当 \(\operatorname{MEX} \geq x\) 时以当前位置为当前子数组的结尾，最后判断子数组数量是否大于等于 \(k\)。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
void cal(ll c, int& x, int& y, int d) {
if (!c) return;
if (c < (ll)d * d) return cal(c, x, y, d >> 1);
c -= (ll)d * d;
if (c < (ll)d * d) return cal(c, x += d, y += d, d >> 1);
c -= (ll)d * d;
if (c < (ll)d * d) return cal(c, x += d, y, d >> 1);
c -= (ll)d * d;
return cal(c, x, y += d, d >> 1);
}
ll cal(ll x, ll y, ll px, ll py, ll d) {
ll dx = px + d, dy = py + d;
if (!d) return 0;
if (x < dx && y < dy) return cal(x, y, px, py, d >> 1);
if (x >= dx && y >= dy) return d * d + cal(x, y, dx, dy, d >> 1);
if (x >= dx) return d * d * 2 + cal(x, y, dx, py, d >> 1);
return d * d * 3 + cal(x, y, px, dy, d >> 1);
}
void solve() {
while (m--) {
char op[2];
ll x, y;
scanf("%s", op);
if (op[0] == '-') {
scanf("%lld%lld", &x, &y);
x--, y--;
printf("%lld\n", cal(x, y, 0ll, 0ll, 1 << (n - 1)) + 1);
} else {
scanf("%lld", &x);
int a = 0, b = 0;
cal(x - 1, a, b, 1 << (n - 1));
printf("%d %d\n", a + 1, b + 1);
}
}
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
solve();
}
return 0;
}

复制代码

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}\)。
例如，如果选择了第一个神经网络，且当前 \(c=[∗,\text{“like”},∗]\)，而 \(b_1=[\text{“I”},\text{“love”},\text{“apples”}]\)，那么在使用第一个神经网络进行操作后，\(c\) 可能变为 \([\text{“I”},\text{“like”},∗]\) 或 \([∗,\text{“like”},\text{“apples”}]\)。

选择位置 \(j\) 并将 \(c_j\) 替换为空白。

不幸的是，由于黑客们访问神经网络的方式，他们只能在所有操作完成之后才能看到修改后的数组 \(c\)，因此他们必须提前指定整个操作序列。
然而，神经网络的随机行为可能导致预期的数组永远无法获得，或者需要进行过多的操作才能获得。
因此，黑客们指望你来帮忙选择一系列操作，使得能够在最少的操作次数内保证获得数组 \(a\)。
更形式化地说，如果存在一系列操作可以保证将数组 \(c\) 转换为数组 \(a\)，那么在所有这样的操作序列中，找到操作次数最少的那个，并输出其中的操作数。
如果不存在能将数组 \(c\) 转换为数组 \(a\) 的操作序列，则输出 \(-1\)。
\(1 \leq n,m \leq 500,|a_i|,|b_{i,j}| \leq 10\)

对于一开始所有元素为空的时候，最坏情况是每一次操作都会随机到一个 \(a_i \neq b_{j,i}\) 的位置，那么最优操作应该是先选择一个同位置字符串与 \(a\) 相等数量最多的一个 \(b\) 并进行 \(n\) 次一操作，这样操作后，对于 \(c\) 中剩下每一个依旧与 \(a_i\) 不相等的位置 \(i\)，先进行二操作，再随便找一个在该位置的字符串与 \(a_i\) 相等的 \(b\) 进行一次一操作即可。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
bool check(int mid) {
vector<bool> st(mid + 2);
int c = 0, cur = 0;
for (int i = 1; i < n; i++) {
if (w[i] <= mid && !st[w[i]]) {
cur++, st[w[i]] = 1;
if (cur == mid) {
cur = 0, c++;
fill(st.begin(), st.end(), 0);
}
}
}
return c >= m;
}
void solve() {
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
solve();
}
return 0;
}

复制代码

G. Shorten the Array

给定一个长度为 \(m\) 的数组 \(b\)，其“美丽值”定义为所有可能的下标对 \(1 \le i \le j \le m\) 中，\(b_i \oplus b_j\) 的最大值，其中 \(x \oplus y\) 表示数字 \(x\) 和 \(y\) 的按位异或。我们用 \(f(b)\) 表示数组 \(b\) 的美丽值。
当数组 \(b\) 满足 \(f(b) \ge k\) 时，称其为美丽的数组。
最近，Kostya 从商店购买了一个长度为 \(n\) 的数组 \(a\)。他觉得这个数组太长了，所以计划从中截取一个美丽的子数组。也就是说，他想选择下标 \(l\) 和 \(r\)（\(1 \le l \le r \le n\)），使得子数组 \(a_l, a_{l+1}, \dots, a_r\) 是美丽的。该子数组的长度为 \(r - l + 1\)。需要注意的是，整个数组 \(a\) 也被视为一个子数组（当 \(l=1\) 且 \(r=n\) 时）。
你的任务是找出数组 \(a\) 中最短的美丽子数组的长度。如果不存在美丽的子数组，则输出 \(-1\)。
\(n \leq 2 \times 10^5,0 \leq k,a_i \leq 10^9\)

写了个可持久化字典树板子。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
void solve() {
cin >> n >> m;
vector<string> a(n + 10);
vector<bool> st(n + 10);
vector<vector<string> > b(m + 2, vector<string>(n + 2));
for (int i = 1; i < n + 1; i++) cin >> a[i];
for (int i = 1; i < m + 1; i++)
for (int j = 1; j < n + 1; j++)
cin >> b[i][j], st[j] = st[j] | (b[i][j] == a[j]);
for (int i = 1; i < n + 1; i++)
if (!st[i]) {
puts("-1");
return;
}
int top = 0;
for (int i = 1; i < m + 1; i++) {
int c = 0;
for (int j = 1; j < n + 1; j++) c += a[j] == b[i][j];
top = max(top, c);
}
if (!top) {
puts("-1");
return;
}
printf("%d\n", n * 3 - 2 * top);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册