Codeforces Round 1006 Div3 A-E

A

题目描述

夏目章人（Natsume Akito）刚刚在一个新世界苏醒，便立即收到了他的第一个任务！系统为他提供了一个包含 n 个零的数组 a，以及两个整数 k 和 p。在每次操作中，章人需要选择两个整数 i 和 x（满足 1≤i≤n 且 −p≤x≤p），然后执行赋值操作 ai​=x。

章人仍未完全适应如何控制他的新身体，因此请你帮他计算使数组所有元素之和等于 k 所需的最少操作次数，或者告诉他这是不可能的。

输入格式

第一行输入包含一个整数 t（1≤t≤1000）—— 测试用例的数量。

每个测试用例的唯一一行包含三个整数 n, k, p（1≤n≤50，−2500≤k≤2500，1≤p≤50）—— 分别表示数组长度、目标总和以及可替换数值的范围边界。

输出格式

对于每个测试用例，输出使数组最终总和为 k 所需的最少操作次数；若无法达成，则输出 −1。

输入输出样例

输入 #1复制

8
21 100 10
9 -420 42
5 -7 2
13 37 7
10 0 49
1 10 9
7 -7 7
20 31 1

输出 #1复制

10
-1
4
6
0
-1
1
-1

说明/提示

第五个样例中，数组初始总和为零，因此无需任何操作。

第六个样例中，数组能达到的最大总和为 9（将唯一元素赋值为 9），因此无法通过任何操作得到总和 10。

第七个样例中，仅需一次操作 a3​=−7 即可达成目标。

翻译由 DeepSeek R1 完成

#include <bits/stdc++.h>#define ll long long
#define PII pair<int, int>
#define Tu tuple<int, int, int>using namespace std;int t;
int n, k, p;void solve()
{cin >> n >> k >> p;if(n * p < abs(k)){cout << -1 << endl;return;}cout << abs(k) / p + (abs(k) % p != 0) << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> t;while(t --){solve();}return 0;
}

B

题目描述

完成第一个任务后，章人（Akito）离开了初始洞穴。不久后，他偶然发现了一个哥布林村落。

由于章人无处可居，他想了解房屋的价格。众所周知，哥布林将数字写作由字符 '-' 和 '_' 组成的字符串，字符串 s 所表示的数值等于其所有等于字符串 "-_-" 的不同子序列 ∗ 的数量（这与哥布林的面部特征非常相似）。

例如，字符串 s= "-_--_-" 表示的数值为 6，因为它包含 6 个 "-_-" 子序列：

1. s1​+s2​+s3​
2. s1​+s2​+s4​
3. s1​+s2​+s6​
4. s1​+s5​+s6​
5. s3​+s5​+s6​
6. s4​+s5​+s6​

最初，哥布林在回答章人的问题时随机写了一个字符串数值 s，但随后他们意识到想要从旅行者身上获取尽可能多的黄金。为此，他们要求你重新排列字符串 s 中的字符，使得该字符串所表示的数值最大化。

∗ 字符串 a 的子序列是指通过删除 a 中若干（可能为 0）个字符后得到的字符串 b。若两个子序列是通过删除不同位置的字符得到的，则它们被视为不同的子序列。

输入格式

第一行包含一个整数 t（1≤t≤104）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 n（1≤n≤2⋅105）—— 哥布林所写字符串的长度。

每个测试用例的第二行包含一个长度为 n 的字符串 s，仅由字符 '-' 和 '_' 组成——哥布林所写的字符串。

保证所有测试用例的 n 之和不超过 2⋅105。

输出格式

对于每个测试用例，输出一个整数——在最优重排字符串 s 后，等于字符串 "-_-" 的子序列的最大数量。

输入输出样例

输入 #1复制

8
3
--_
5
__-__
9
--__-_---
4
_--_
10
_-_-_-_-_-
7
_------
1
-
2
_-

输出 #1复制

1
0
27
2
30
9
0
0

说明/提示

第一个测试用例中，最优方案是将字符重排为 "-_-"。这是唯一一个长度为 3 且至少包含一个 "-_-" 子序列的字符串。

第二个测试用例中，只有一个字符 "-"，而构成子序列 "-_-" 至少需要两个 "-"。这意味着无论如何重排，答案都是 0。

第七和第八个测试用例中，字符串长度 n<3，这意味着长度为 3 的子序列不存在。

翻译由 DeepSeek R1 完成

最优方案一定是把 "_" 全部放中间， “-” 放两边。答案就是左边的板子数 * 中间的板子数 * 右边的板子数，中间的板子数一定是确定的，那么考虑一下两边放多少数量，其实就是一个基本不等式，尽量让两边板子数相等

代码

#include <bits/stdc++.h>#define ll long long
#define PII pair<int, int>
#define Tu tuple<int, int, int>using namespace std;int t, n;void solve()
{cin >> n;int up = 0, down = 0;for(int i = 0;i < n;i ++){char ch;cin >> ch;if(ch == '_') down ++;else up ++;}if(up < 2 || down < 1){cout << 0 << endl;return;}ll ans = 0;if(up & 1) ans = (ll)up / 2 * (up / 2 + 1) * down;else ans = (ll)up / 2 * up / 2 * down;cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> t;while(t --){solve();}return 0;
}

C

题目描述

Akito 仍然无处可住，而小房间的价格却居高不下。为此，Akito 决定在银行找一份为存储设备创建密钥的工作。

在这个魔法世界中，一切都与众不同。例如，代码为 (n,x) 的存储设备的密钥是一个满足以下条件的长度为 n 的数组 a：

• a1​∣a2​∣a3​∣…∣an​=x，其中 a∣b 表示数 a 和 b 的按位或运算。
• MEX({a1​,a2​,a3​,…,an​}) ∗ 在所有满足条件的数组中达到最大值。

Akito 勤奋地工作了几个小时，但突然头痛发作。请代替他工作一小时：对于给定的 n 和 x，创建任意一个满足代码为 (n,x) 的存储设备的密钥。

∗ MEX(S) 是满足以下条件的最小非负整数 z：z 不在集合 S 中，且所有满足 0≤y<z 的 y 都在集合 S 中。

输入格式

第一行包含一个数 t（1≤t≤104）——测试用例的数量。

每个测试用例的唯一一行包含两个数 n 和 x（1≤n≤2⋅105，0≤x<230）——数组的长度和按位或运算的目标值。

保证所有测试用例的 n 之和不超过 2⋅105。

输出格式

对于每个测试用例，输出 n 个整数 ai​（0≤ai​<230）——满足所有条件的密钥数组元素。

如果存在多个符合条件的数组，输出其中任意一个即可。

翻译由 DeepSeek R1 完成

输入输出样例

输入 #1复制

9
1 69
7 7
5 7
7 3
8 7
3 52
9 11
6 15
2 3

输出 #1复制

69
6 0 3 4 1 2 5
4 1 3 0 2
0 1 2 3 2 1 0
7 0 6 1 5 2 4 3
0 52 0
0 1 8 3 0 9 11 2 10
4 0 3 8 1 2
0 3

这题属于想到一眼出，想不到卡很久。

思路：贪心，由于求最大的mex，所以从 0 - n 去枚举，每一次检查 i 是否会对异或值产生影响，也就是 x | i == i 才行，最后如果异或值不等于 x 把最后一位改成 x 即可

代码

#include <bits/stdc++.h>#define ll long long
#define PII pair<int, int>
#define Tu tuple<int, int, int>using namespace std;int T, n, w;int lowbit(int x)
{return x & -x;
}void solve()
{cin >> n >> w;if(n == 1){cout << w << endl;return;}vector<int> ans(n);int s = 0;for(int i = 0;i < n;i ++) if((i | w) == w){ans[i] = i;s |= i;}if(s != w) ans[n - 1] = w;for(auto x : ans)cout << x << " ";cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> T;while(T --){solve();}return 0;
}

D

题目描述

Akito 厌倦了在银行当普通锁匠的工作，因此他决定进入魔法学院并成为世界上最强的巫师！然而，为了入学，他需要解决考试中的唯一一道题目，而这位雄心勃勃的英雄却未能成功。

题目给出一个长度为 n 的数组 a。Akito 需要在使用恰好一次咒语后，使数组中的逆序对数量 ∗ 最小化。咒语的使用方式很简单：Akito 必须选择两个数 l 和 r（满足 1≤l≤r≤n），并对子数组 [l,r] 进行一次向左循环移位。

更正式地说，Akito 选择子数组 [l,r] 并按以下方式修改数组：

• 原始数组为 [a1​,a2​,…,al−1​,al​,al+1​,…,ar−1​,ar​,ar+1​,…,an−1​,an​]，修改后的数组变为 [a1​,a2​,…,al−1​,al+1​,al+2​,…,ar−1​,ar​,al​,ar+1​,…,an−1​,an​]。

Akito 渴望开始他的学习，但他仍未通过考试。请帮助他入学并解决这道题目！

∗ 在长度为 m 的数组 b 中，逆序对被定义为满足 1≤i<j≤m 且 bi​>bj​ 的索引对 (i,j)。例如，在数组 b=[3,1,4,1,5] 中，逆序对为索引对 (1,2)、(1,4) 和 (3,4)。

输入格式

输入的第一行包含一个数 t（1≤t≤104）——测试用例的数量。

每个测试用例的第一行包含一个数 n（1≤n≤2000）——数组 a 的长度。

每个测试用例的第二行包含 n 个数 ai​（1≤ai​≤2000）——数组 a 的元素。

保证所有测试用例的 n2 之和不超过 4⋅106。

输出格式

对于每个测试用例，输出两个数 l 和 r（1≤l≤r≤n）——选择的子数组边界，使得应用咒语后数组的逆序对数量最小。

如果存在多个符合条件的边界对，可以输出其中任意一个。

输入输出样例

输入 #1复制

9
7
1 4 3 2 5 3 3
6
1 4 3 2 5 3
8
7 6 5 8 4 3 2 1
10
1 1 1 5 1 1 5 6 7 8
2
1337 69
4
2 1 2 1
3
998 244 353
3
1 2 1
9
1 1 2 3 5 8 13 21 34

输出 #1复制

2 7
2 4
1 8
4 6
1 2
1 4
1 3
2 3
5 5

说明/提示

在第一个示例中，数组 [1,4,3,2,5,3,3] 将变为 [1,3,2,5,3,3,4]。其中的逆序对为 (2,3)、(4,5)、(4,6) 和 (4,7)。可以证明无法获得少于 4 个逆序对。

在第二个示例中，数组 [1,4,3,2,5,3] 将变为 [1,3,2,4,5,3]。其中的逆序对为 (2,3)、(4,6) 和 (5,6)。选择 l=2 和 r=6 同样有效，此时数组变为 [1,3,2,5,3,4]，其中也有 3 个逆序对：(2,3)、(4,5) 和 (4,6)。可以证明无法获得少于 3 个逆序对。

在第四个示例中，选择 l=4 和 r=6 将数组变为 [1,1,1,1,1,5,5,6,7,8]。该数组已排序，因此没有逆序对。

在最后一个示例中，数组初始时已排序，因此对长度至少为 2 的段进行任何操作只会增加逆序对的数量。

翻译由 DeepSeek R1 完成

这个数据范围直接暴力就行

代码

#include <bits/stdc++.h>#define ll long long
#define PII pair<int, int>
#define Tu tuple<int, int, int>using namespace std;int T, n;void solve()
{cin >> n;vector<int> a(n);for(auto &x : a)cin >> x;int cnt = 0, l = -1, r = -1;for(int i = 0;i < n - 1;i ++){int t = 0, ed;for(int j = i + 1;j < n;j ++){if(a[j] < a[i]) t ++, ed = j;else if(a[j] > a[i]) t --;if(t > cnt){cnt = t;l = i, r = ed;}}}if(l == -1) cout << 1 << " " << 1 << endl;else cout << l + 1 << " " << r + 1 << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> T;while(T --){solve();}return 0;
}

E

题目描述

Akito 决定学习一个强大的新咒语。由于这个咒语拥有无可估量的力量，它必然需要大量空间和精心准备。为此，Akito 来到了一片空地。我们将这片空地表示为一个笛卡尔坐标系。

为了施展咒语，Akito 需要在空地的不同整数坐标处放置 0≤n≤500 根法杖，使得恰好存在 k 对 (i,j) 满足 1≤i<j≤n 且 ρ(i,j)=d(i,j)。

这里，对于两个整数坐标点 a=(xa​,ya​) 和 b=(xb​,yb​)，定义 ρ(a,b)=(xa​−xb​)2+(ya​−yb​)2​ 且 d(a,b)=∣xa​−xb​∣+∣ya​−yb​∣。

输入格式

输入的第一行包含一个数 t（1≤t≤1000）——测试用例的数量。

每个测试用例的唯一一行包含一个数 k（0≤k≤105）——满足 ρ(i,j)=d(i,j) 的法杖对数要求。

输出格式

对于每个测试用例，输出的第一行应包含一个数 n（0≤n≤500）——放置的法杖数量。

接下来的 n 行中，每行应输出两个整数 xi​,yi​（−109≤xi​,yi​≤109）——第 i 根法杖的坐标。所有法杖的坐标点必须互不相同。

翻译由 DeepSeek R1 完成

输入输出样例

输入 #1复制

3
0
2
5

输出 #1复制

6
69 52
4 20
789 9308706
1337 1337
-1234 -5678
23456178 707
10
-236 -346262358
273568 6435267
2365437 31441367
246574 -45642372
-236 56
4743623 -192892 
10408080 -8173135
-237415357 31441367
-78125638 278
56 143231
5
1 1
2 1
1 5
3 5
1 10

画个坐标轴，可以发现当两个坐标 x1 == x2 || y1 == y2 就一定符合，那么只要这个知道了，剩下也是暴力（官解写的那个递归有点复杂了，没必要）

参照一下数据范围，可以自己推推为什么每次是枚举到 500 就可以了，那如果在把数据范围调大的话，可以用二分优化

代码

#include <bits/stdc++.h>#define ll long long
#define PII pair<int, int>
#define Tu tuple<int, int, int>using namespace std;int T, k;void solve()
{cin >> k;if(k == 0){cout << 0 << endl;return;}vector<PII> ans;int x = 1, y = 1;while(k > 0){for(int i = y;i <= 500;i ++){int id = i - y + 1;if(k >= id - 1){k -= id - 1;ans.push_back({x, i});}else{y = i;break;}}x ++;}cout << ans.size() << endl;for(auto [x, y] : ans)cout << x << " " << y << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> T;while(T --){solve();}return 0;
}

加油