找回密码
 立即注册
首页 业界区 科技 Codeforces Round 1016 (Div. 3)

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\) 为偶数时数组和不能为奇数,为奇数时是理想生成器。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. int main() {
  10.     int T;
  11.     cin >> T;
  12.     while (T--) {
  13.         cin >> n;
  14.         puts(n & 1 ? "YES" : "NO");
  15.     }
  16.     return 0;
  17. }
复制代码
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\)。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. char s[N];
  10. int main() {
  11.     int T;
  12.     cin >> T;
  13.     while (T--) {
  14.         scanf("%s", s + 1);
  15.         n = strlen(s + 1);
  16.         int c = 0;
  17.         bool flag = 0;
  18.         for (int i = n; i; i--) {
  19.             flag |= s[i] != '0';
  20.             c += flag && s[i] == '0';
  21.         }
  22.         printf("%d\n", n - c - 1);
  23.     }
  24.     return 0;
  25. }
复制代码
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\) 为质数。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. int main() {
  10.     int T;
  11.     cin >> T;
  12.     while (T--) {
  13.         cin >> n >> m;
  14.         if (n == 1 && m == 2) {
  15.             puts("YES");
  16.         } else if (m > 1) {
  17.             puts("NO");
  18.         } else {
  19.             bool flag = n == 1;
  20.             for (ll i = 2; i * i <= n; i++)
  21.                 if (n % i == 0) {
  22.                     flag = 1;
  23.                 }
  24.             puts(flag ? "NO" : "YES");
  25.         }
  26.     }
  27.     return 0;
  28. }
复制代码
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\)。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. void cal(ll c, int& x, int& y, int d) {
  10.     if (!c) return;
  11.     if (c < (ll)d * d) return cal(c, x, y, d >> 1);
  12.     c -= (ll)d * d;
  13.     if (c < (ll)d * d) return cal(c, x += d, y += d, d >> 1);
  14.     c -= (ll)d * d;
  15.     if (c < (ll)d * d) return cal(c, x += d, y, d >> 1);
  16.     c -= (ll)d * d;
  17.     return cal(c, x, y += d, d >> 1);
  18. }
  19. ll cal(ll x, ll y, ll px, ll py, ll d) {
  20.     ll dx = px + d, dy = py + d;
  21.     if (!d) return 0;
  22.     if (x < dx && y < dy) return cal(x, y, px, py, d >> 1);
  23.     if (x >= dx && y >= dy) return d * d + cal(x, y, dx, dy, d >> 1);
  24.     if (x >= dx) return d * d * 2 + cal(x, y, dx, py, d >> 1);
  25.     return d * d * 3 + cal(x, y, px, dy, d >> 1);
  26. }
  27. void solve() {
  28.     while (m--) {
  29.         char op[2];
  30.         ll x, y;
  31.         scanf("%s", op);
  32.         if (op[0] == '-') {
  33.             scanf("%lld%lld", &x, &y);
  34.             x--, y--;
  35.             printf("%lld\n", cal(x, y, 0ll, 0ll, 1 << (n - 1)) + 1);
  36.         } else {
  37.             scanf("%lld", &x);
  38.             int a = 0, b = 0;
  39.             cal(x - 1, a, b, 1 << (n - 1));
  40.             printf("%d %d\n", a + 1, b + 1);
  41.         }
  42.     }
  43. }
  44. int main() {
  45.     int T;
  46.     cin >> T;
  47.     while (T--) {
  48.         cin >> n >> m;
  49.         solve();
  50.     }
  51.     return 0;
  52. }
复制代码
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\) 进行一次一操作即可。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. bool check(int mid) {
  10.     vector<bool> st(mid + 2);
  11.     int c = 0, cur = 0;
  12.     for (int i = 1; i < n; i++) {
  13.         if (w[i] <= mid && !st[w[i]]) {
  14.             cur++, st[w[i]] = 1;
  15.             if (cur == mid) {
  16.                 cur = 0, c++;
  17.                 fill(st.begin(), st.end(), 0);
  18.             }
  19.         }
  20.     }
  21.     return c >= m;
  22. }
  23. void solve() {
  24.     int l = 0, r = n;
  25.     while (l < r) {
  26.         int mid = l + r + 1 >> 1;
  27.         if (check(mid)) l = mid;
  28.         else r = mid - 1;
  29.     }
  30.     printf("%d\n", r);
  31. }
  32. int main() {
  33.     int T;
  34.     cin >> T;
  35.     while (T--) {
  36.         cin >> n >> m;
  37.         for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
  38.         solve();
  39.     }
  40.     return 0;
  41. }
复制代码
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\)
写了个可持久化字典树板子。
  代码
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int, int> pii;
  4. typedef pair<int, pair<int, int> > piii;
  5. typedef long long ll;
  6. const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
  7. ll res;
  8. int n, m, cnt, w[N];
  9. void solve() {
  10.     cin >> n >> m;
  11.     vector<string> a(n + 10);
  12.     vector<bool> st(n + 10);
  13.     vector<vector<string> > b(m + 2, vector<string>(n + 2));
  14.     for (int i = 1; i < n + 1; i++) cin >> a[i];
  15.     for (int i = 1; i < m + 1; i++)
  16.         for (int j = 1; j < n + 1; j++)
  17.             cin >> b[i][j], st[j] = st[j] | (b[i][j] == a[j]);
  18.     for (int i = 1; i < n + 1; i++)
  19.         if (!st[i]) {
  20.             puts("-1");
  21.             return;
  22.         }
  23.     int top = 0;
  24.     for (int i = 1; i < m + 1; i++) {
  25.         int c = 0;
  26.         for (int j = 1; j < n + 1; j++) c += a[j] == b[i][j];
  27.         top = max(top, c);
  28.     }
  29.     if (!top) {
  30.         puts("-1");
  31.         return;
  32.     }
  33.     printf("%d\n", n * 3 - 2 * top);
  34. }
  35. int main() {
  36.     ios::sync_with_stdio(false); cin.tie(nullptr);
  37.     int T;
  38.     cin >> T;
  39.     while (T--) solve();
  40.     return 0;
  41. }
复制代码
来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册