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;
- }
复制代码 来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |