Codeforces Round 1020 (Div. 3)

嫁蝇 · 昨天 17:52

A. Dr. TC

为了测试病人的智力，TC 博士设计了如下测试：
首先，他会构造一个长度为 $n$ 的二进制字符串 $s$。然后，他会基于 $s$ 构造出 $n$ 个二进制字符串 $a_1, a_2, \dots, a_n$。构造方式如下：$a_i$ 是将 $s$ 复制一份后，把第 $i$ 个字符翻转（即 1 变成 0，0 变成 1）得到的。
构造完成后，他将这 $n$ 个字符串按行排列成一个网格，第 $i$ 行为 $a_i$。
例如：

如果 $s = 101$，则 $a = [001, 111, 100]$；

如果 $s = 0000$，则 $a = [1000, 0100, 0010, 0001]$。

病人的任务是在不到一秒的时间内，数出整个网格中出现了多少个字符 $1$。你能通过这项测试吗？

对于每一位，如果该位是 $1$，则贡献是 $n - 1$，否则是 $1$。
代码

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

复制代码

B. St. Chroma

给定一个长度为 $n$ 的排列 $p$，它包含了从 $0$ 到 $n-1$ 的所有整数。
St. Chroma 有一个长度为 $n$ 的条形区域（strip），她会按如下方式为每个格子染色：
第 $i$ 个格子会被染成颜色 $\text{MEX}(p_1, p_2, ..., p_i)$，即当前前缀的最小未出现的非负整数。
例如，若 $p = [1, 0, 3, 2]$，则每个格子的颜色依次为：
$\text{MEX}([1]) = 0$，
$\text{MEX}([1, 0]) = 2$，
$\text{MEX}([1, 0, 3]) = 2$，
$\text{MEX}([1, 0, 3, 2]) = 4$，
所以染色结果为：[0, 2, 2, 4]。
你现在给定两个整数 $n$ 和 $x$。因为 St. Chroma 非常喜欢颜色 $x$，你需要构造一个排列 $p$，使得染色后颜色为 $x$ 的格子数量最多。
请输出满足条件的一个排列。

想要让 $\operatorname{MEX}(x)$ 出现次数最多，就是把 $0$ 到 $x - 1$ 放到最前面，$x$ 放到最后面。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i < n + 1; i++) w[i] = i - 1;
if (m < n) swap(w[n], w[m + 1]);
for (int i = 1; i < n + 1; i++) printf("%d ", w[i]);
puts("");
}
return 0;
}

复制代码

C. Cherry Bomb

有两个长度为 $n$ 的整数数组 $a$ 和 $b$，当存在一个整数 $x$，使得对于所有 $1 \leq i \leq n$，都有 $a_i + b_i = x$ 时，我们称这两个数组是“互补的”。
例如，数组 $a = [2, 1, 4]$ 和 $b = [3, 4, 1]$ 是互补的，因为对于每个位置，$a_i + b_i = 5$。
但数组 $a = [1, 3]$ 和 $b = [2, 1]$ 就不是互补的。
Cow the Nerd 相信每个人都对数学感兴趣，于是他给了 Cherry Bomb 两个数组 $a$ 和 $b$。
已知 $a$ 和 $b$ 都是长度为 $n$ 的整数数组，所有元素都是不超过 $k$ 的非负整数。
但是，数组 $b$ 中有一些元素丢失了，丢失的位置用 $-1$ 表示。
现在你的任务是：帮助 Cherry Bomb 计算出有多少种可能的数组 $b$，满足以下两个条件：

数组 $a$ 和 $b$ 是互补的（即存在某个整数 $x$，使得 $a_i + b_i = x$ 对所有 $i$ 都成立）。

丢失的元素必须替换为不超过 $k$ 的非负整数（即 $0 \leq b_i \leq k$）。

请输出符合条件的 $b$ 数组的种数。

如果 $b$ 数组全都是 $-1$，则最多有 $m + 1$ 减去 $a$ 中最大值和最小值的差种方法，否则判断所有已经确定值的 $b_i$ 与 $a_i$ 的和是否相等，以及未确定值的 $b_i$ 是否可以分配到一个合法值。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
int a[N], b[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i < n + 1; i++) scanf("%d", a + i);
int c = 0;
for (int i = 1; i < n + 1; i++) scanf("%d", b + i), c += b[i] != -1;
if (!c) {
sort(a + 1, a + n + 1);
printf("%d\n", max(0, m - (a[n] - a[1]) + 1));
} else {
bool flag = 0;
int v;
for (int i = 1; i < n + 1; i++)
if (b[i] != -1) {
v = a[i] + b[i];
break;
}
for (int i = 1; i < n + 1; i++) {
if (b[i] == -1) flag |= v - a[i] < 0 || v - a[i] > m;
else flag |= a[i] + b[i] != v;
}
puts(flag ? "0" : "1");
}
}
return 0;
}

复制代码

D. Flower Boy

Flower boy 有一个由 $n$ 朵花组成的花园，这个花园可以用一个整数序列 $a_1, a_2, \dots, a_n$ 表示，其中 $a_i$ 是从左到右第 $i$ 朵花的美丽值。
Igor 想要采摘恰好 $m$ 朵花。为此，他会从左到右走过整个花园，并决定是否采摘当前位置的花。被采摘的第 $i$ 朵花，其美丽值必须不小于 $b_i$。
Igor 发现，有时无法在花园中找到 $m$ 朵满足要求的花。所以，在开始采摘前，他可以选择一个整数 $k$，用他的魔法棒生成一朵美丽值为 $k$ 的新花，并把它插入到花园中的任意位置（可以是两朵花之间、第一朵花前、或最后一朵花后）。
由于魔力有限，这种操作最多只能使用一次。
你的任务是输出 Igor 为了保证能采摘到符合要求的 $m$ 朵花，所需选择的最小整数 $k$：

如果不需要插入任何花就能完成采摘，则输出 $0$；

如果即使插入了一朵花也无法采摘到满足条件的 $m$ 朵花，则输出 $-1$；

否则，输出 Igor 必须选择的最小整数 $k`，使得插入之后一定可以成功采摘到 $m$ 朵满足要求的花。

维护 $a$ 中每一个前缀能够匹配到的 $b$ 的最长前缀，$a$ 中每一个后缀能够匹配到的 $b$ 的最长后缀，如果一个位置的最长匹配后缀与它前一个位置的最长匹配前缀的和为 $m - 1$，那么 $k$ 可以取到剩下的那一朵花的美丽值。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];
int a[N], b[N], l[N], r[N];
void solve() {
int res = INF;
r[n + 1] = m + 1;
for (int i = 1; i < n + 1; i++) l[i] = l[i - 1] + (l[i - 1] != m && a[i] >= b[l[i - 1] + 1]);
for (int i = n; i; i--) r[i] = r[i + 1] - (r[i + 1] != 1 && a[i] >= b[r[i + 1] - 1]);
if (l[n] == m) res = 0;
if (l[n] == m - 1) res = min(b[m], res);
for (int i = 1; i < n + 1; i++)
if (r[i] - l[i - 1] == 2)
res = min(res, b[l[i - 1] + 1]);
printf("%d\n", res == INF ? -1 : res);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i < n + 1; i++) scanf("%d", a + i);
for (int i = 1; i < m + 1; i++) scanf("%d", b + i);
solve();
}
return 0;
}

复制代码

E. Wolf

Wolf 找到了一群共有 $n$ 只羊，它们的美味值组成了一个排列 $p_1, p_2, \dots, p_n$。现在 Wolf 想在数组 $p$ 上使用二分查找来找到美味值为 $k$ 的羊。但数组 $p$ 可能不是有序的。
对区间 $[l, r]$ 上的 $k$ 进行二分查找是否成功，用函数 $f(l, r, k)$ 表示，定义如下：

如果 $l > r$，则 $f(l, r, k)$ 失败；

否则，令 $m = \lfloor \frac{l + r}{2} \rfloor$，并且：

如果 $p_m = k$，则 $f(l, r, k)$ 成功；

如果 $p_m < k$，则 $f(l, r, k) = f(m+1, r, k)$；

如果 $p_m > k$，则 $f(l, r, k) = f(l, m-1, k)$。

Cow the Nerd 决定帮助 Wolf。他收到了 $q$ 个查询，每个查询给出三个整数 $l$、$r$ 和 $k$。
在执行搜索之前，Cow the Nerd 可以选择一个非负整数 $d$，以及 $d$ 个索引 $1 \le i_1 < i_2 < \dots < i_d \le n$，并且要求这些位置上 $p_{i_j} \ne k$ 对所有 $1 \le j \le d$。然后，他可以任意重新排列这些位置上的元素。
对于每个查询，请你输出 Cow the Nerd 至少需要选择的最小整数 $d$，使得执行 $f(l, r, k)$ 的搜索一定成功。如果无论怎么做都不可能使搜索成功，则输出 $-1$。
注意：每个查询是相互独立的，且这些重排实际上并不会真的被执行。

如果 $x$ 所在的位置不在 $[l, r]$ 中则无解，否则考虑模拟二分的过程，如果当前 $p_m < x$，若 $x$ 的位置在 $[m + 1, r]$ 内，则不需要交换 $x$，否则需要将 $p_m$ 与任意一个大于 $x$ 的数交换，对于 $p_m > x$ 的情况同理。最后统计过程中使用到的大于 $x$ 的数及小于 $x$ 的数的数量是否合法。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N], id[N];
void solve() {
while (m--) {
int pl, pr, x;
scanf("%d%d%d", &pl, &pr, &x);
if (id[x] > pr || id[x] < pl) {
printf("-1 ");
continue;
}
int l = pl, r = pr, c = 0;
int maxc = 0, minc = 0, a = 0, b = 0;
while (l < r) {
int mid = l + r >> 1;
if (w[mid] == x) break;
else if (w[mid] < x) {
if (id[x] < mid) maxc++, r = mid - 1;
else l = mid + 1, a++;
} else {
if (id[x] > mid) l = mid + 1, minc++;
else r = mid - 1, b++;
}
}
if (maxc + b <= n - x && minc + a <= x - 1) printf("%d ", max(maxc, minc) * 2);
else printf("-1 ");
}
puts("");
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i < n + 1; i++) scanf("%d", w + i), id[w[i]] = i;
solve();
}
return 0;
}

复制代码

F. Goblin

TC 博士有一个新病人，叫 Goblin。他想测试 Goblin 的智商，但他已经对自己以前的标准测试感到厌倦了，于是他决定让测试变得更难一点。
首先，他创建了一个长度为 $n$ 的二进制字符串 $s$。然后，他创建了 $n$ 个二进制字符串 $a_1, a_2, \dots, a_n$。已知 $a_i$ 是通过复制字符串 $s$，再将第 $i$ 位字符翻转（1 变成 0，0 变成 1）得到的。
接下来，他将这些字符串排成一个 $n \times n$ 的网格 $g$，其中 $g_{i,j} = a_{i,j}$。
定义一个大小为 $k$ 的整数对集合 $S=\{(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\}$ 是好集合，当且仅当满足以下条件：

对于所有 $1 \le i \le k$，都有 $1 \le x_i, y_i \le n$；

对于所有 $1 \le i \le k$，都有 $g_{x_i,y_i} = 0$；

对于任意两个整数 $i$ 和 $j$（$1 \le i, j \le k$），坐标 $(x_i, y_i)$ 可以通过一系列相邻格子（上下左右方向相邻，且值为 0）连通到坐标 $(x_j, y_j)$。

Goblin 的任务是找出好集合 $S$ 的最大可能大小。
因为 TC 博士这次大发慈悲，给了 Goblin 两秒钟的时间来找出答案，而不是一秒钟。但 Goblin 可不是个诚实的人，于是他来找你帮忙作弊。

手玩一下可以观察到，对于某个 $s_i = 0$，$g$ 中第 $i$ 列是上面 $i - 1$ 个 $0$，中间 $1$ 个 $1$，下面 $n - i$ 个 $0$，相邻列之间上半部分的 $0$ 连通，下半部分的 $0$ 连通，并且上半部分的 $0$ 永远无法与下半部分的 $0$ 连通，而对于 $s_i = 1$，其唯一的 $0$ 连通的是前一列的下半部分，下一列的上半部分。因此可以维护上半部分的 $0$ 的数量与下半部分的 $0$ 的数量。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N], id[N];
char s[N];
void solve() {
res = 0;
ll t = 0, d = 0;
for (int i = 1; i < n + 1; i++) {
if (s[i] == '1') t = d, d = 0, t++;
else t += i - 1, d += n - i;
res = max({ res, t, d });
}
printf("%lld\n", res);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
scanf("%s", s + 1);
solve();
}
return 0;
}

复制代码

G1. Baudelaire (easy version)

这是这个问题的简单版本。简单版与困难版唯一的区别在于：在这个版本中，保证每个节点都与节点 1 相邻。
这是一个交互题。
Baudelaire 非常富有，所以他买下了一棵大小为 $n$ 的树，这棵树以某个未知节点为根。此外，树上的每个节点的值要么是 $1$，要么是 $-1$。在这个版本中，每个节点都与节点 $1$ 相邻。但请注意，节点 $1$ 不一定是树的根节点。
Cow the Nerd 看到了这棵树并深深地爱上了它。然而，计算机科学的收入不足以让他买得起。于是 Baudelaire 决定和他玩一个游戏，如果他赢了，就把树送给他。
Cow the Nerd 不知道哪一个节点是树的根，也不知道每个节点的初始值是多少。但他可以向 Baudelaire 发出两种类型的询问：

1 k u₁ u₂ ... uₖ：设 $f(u)$ 表示从树的根到节点 $u$ 的路径上所有节点值的和。Cow the Nerd 可以选择一个整数 $k$（$1 \le k \le n$）和 $k$ 个节点 $u_1, u_2, \dots, u_k$，他将得到 $f(u_1) + f(u_2) + \dots + f(u_k)$ 的值。

2 u：Baudelaire 会切换节点 $u$ 的值。如果原本是 $1$，则变成 $-1$；如果是 $-1$，则变成 $1$。

Cow the Nerd 胜利的条件是：在总共不超过 $n+200$ 次查询的前提下，正确猜出所有节点的最终值（即在所有切换操作之后每个节点的值。
你能帮他赢下这棵树吗？

分类讨论，先查询节点 $1$，若查询到的值的绝对值为 $1$，此时节点 $1$ 为根。若查询到的值的绝对值为 $2$，此时节点 $1$ 不为根且节点 $1$ 与根的值相同，将节点 $1$ 的值翻转后其与根的权值和为 $0$，此时查询节点 $1$ 以外的节点的结果就是该点的值。若查询到的值为 $0$，需要先将节点 $1$ 翻转一次来确认节点 $1$ 的初始值，然后再将节点 $1$ 翻转使得其与根的权值和为 $0$。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 4000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N], id[N];
int ask1(vector<int>& v) {
printf("? 1 %d ", v.size());
for (auto u : v) printf("%d ", u);
puts("");
fflush(stdout);
int res;
scanf("%d", &res);
return res;
}
int ask1(int x) {
printf("? 1 1 %d\n", x);
fflush(stdout);
int res;
scanf("%d", &res);
return res;
}
void ask2(int x) {
printf("? 2 %d\n", x);
fflush(stdout);
}
void solve() {
int v1 = ask1(1);
if (abs(v1) == 1) {
w[1] = v1;
for (int i = 2; i < n + 1; i++) w[i] = ask1(i) - w[1];
} else if (v1) {
if (v1 == 2) w[1] = -1;
else w[1] = 1;
ask2(1);
for (int i = 2; i < n + 1; i++) w[i] = ask1(i);
} else {
ask2(1);
int x = ask1(1);
if (x == 2) w[1] = -1;
else w[1] = 1;
ask2(1);
for (int i = 2; i < n + 1; i++) w[i] = ask1(i);
}
printf("! ");
for (int i = 1; i < n + 1; i++) printf("%d ", w[i]);
puts("");
fflush(stdout);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
int a, b;
for (int i = 1; i < n; i++) scanf("%d%d", &a, &b);
solve();
}
return 0;
}

复制代码

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

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

Codeforces Round 1020 (Div. 3)

浏览过的版块

签约作者