Codeforces Round 1016 (Div. 3)
A. Ideal Generator我们称一个由 \(k\) 个正整数组成的数组 \(a\) 为回文数组，如果满足
\[=.\]
例如，数组 \(\) 和 \(\) 是回文数组，而数组 \(\) 和 \(\) 则不是。
我们称一个数 \(k\) 为“理想生成器”，如果任意整数 \(n\) （\(n \ge k\)）都可以表示为一个长度恰为 \(k\) 的回文数组元素之和。该数组的每个元素都必须大于 \(0\)。
例如，数 \(1\) 是一个理想生成器，因为任何自然数 \(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;
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;
char s;
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 != '0';
c += flag && s == '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;
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 值的最小值，即
\
\(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;
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;
ll x, y;
scanf("%s", op);
if (op == '-') {
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;
bool check(int mid) {
vector<bool> st(mid + 2);
int c = 0, cur = 0;
for (int i = 1; i < n; i++) {
if (w <= mid && !st]) {
cur++, st] = 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;
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;
for (int i = 1; i < m + 1; i++)
for (int j = 1; j < n + 1; j++)
cin >> b, st = st | (b == a);
for (int i = 1; i < n + 1; i++)
if (!st) {
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 == b;
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;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]