2022-2023 ICPC NERC (NEERC)
A. Absolutely Flat
题目描述
爱丽丝是四条腿桌子的主人，她希望自己的桌子是平的。爱丽丝认为，如果四条腿的长度相等，桌子就是平的。
爱丽丝测量了桌子目前的桌腿长度，得到了 \(a_1, a_2, a_3\) 和 \(a_4\) 。她还有一个长度为 \(b\) 的垫子。爱丽丝可以将垫子固定在其中一条桌腿上，这样该桌腿的长度将增加 \(b\) 。她也可以决定不安装垫子，在这种情况下，两条腿的长度不会改变。请注意，爱丽丝只有一个垫子，因此她既不能在同一条腿上贴两次垫子，也不能在两条不同的腿上贴垫子。
求爱丽丝能否把桌子做平。
输入
输入包含五个正整数 \(a_1, a_2, a_3, a_4\) 和 \(b\) ，每个整数单独一行，分别是桌子腿的长度，以及爱丽丝拥有的垫子的长度（ \(1 \le a_i, b \le 100\) ）。
输出
如果爱丽丝能将桌子铺平，则打印 \(1\) ，否则打印 \(0\) 。
题解
简单签到
AC 代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
array<int, 4> a;
for (int i = 0; i < 4; i++) {
cin >> a[i];
}
int add;
cin >> add;
sort(a.begin(), a.end());
if (a[0] == a[3]) {
cout << "1\n";
return;
}
a[0] += add;
if (a[0] == a[1] && a[1] == a[2] && a[2] == a[3]) {
cout << "1\n";
} else {
cout << "0\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
N.New Time
题目描述
尼古拉的数字时钟以 24 小时制显示时间，显示两个整数：小时(从 \(00\) 到 \(23\) )和分钟(从 {8879646} 到 \(59\) )。例如，时钟可以显示 00:00、18:42 或 23:59。
时钟有两个按钮可用于手动调整：
- 按钮 A 将时钟向前拨 \(1\) 分钟。例如，05:33 变成 05:34，16:59 变成 17:00，23:59 变成 00:00。
- 按钮 B 将时钟向前拨 \(1\) 小时。例如，01:42 变成 02:42，23:14 变成 00:14。
尼古拉注意到时钟上的时间看起来不对。他想尽量少按按钮，将时钟调到正确的时间。
请找出调整时钟所需的最少按键次数。
输入
第一行包含时钟上显示的时间，格式为 hh:mm（ \(00 \le \mathtt{hh} \le 23\) ; \(00 \le \mathtt{mm} \le 59\) ）。
第二行包含相同格式的正确时间。
输出
打印一个整数--尼古拉调整时钟时间所需的最小按键次数。
题解
简单签到，但是如果考虑对分钟和时钟的数值进行分类讨论的话还是比较容易出错的。注意到只能把时间往前调，所以不存在策略选择问题。可以直接把两个时间转换为分钟数，取其差值 \(\Delta t\)， 可知需要拨动时钟 \(\Delta t / 60\) 次，分钟 \(\Delta t mod 60\) 次。
AC 代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
int h1 = (s[0] - '0') * 10 + s[1] - '0', m1 = (s[3] - '0') * 10 + s[4] - '0';
int time1 = h1 * 60 + m1;
cin >> s;
int h2 = (s[0] - '0') * 10 + s[1] - '0', m2 = (s[3] - '0') * 10 + s[4] - '0';
int time2 = h2 * 60 + m2;
if (time2 < time1) {
time2 += 24 * 60;
}
int addH = (time2 - time1) / 60;
int addM = (time2 - time1) % 60;
cout << addH + addM << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
C.Computer Network
题目描述
Cupa 正在使用 \(n\) 台计算机和一个集线器构建一个连接网络。
计算机的编号从 \(1\) 到 \(n\) 。每台电脑 \(i\) 都有一条外线，可以在 \(d_i\) 毫秒内将一位数据传输到另一端。
集线器有 \(k\) 个端口，计算机的电线可以连接到这些端口，每台计算机有一个端口。
Cupa 要求每台计算机的电线都要连接到某个端口--要么是集线器中的端口，要么是另一台计算机中的端口。此外，每台计算机还可以直接或通过其他计算机向集线器发送数据。
每台计算机 \(i\) 的网络延迟 \(t_i\) 定义为从计算机 \(i\) 向集线器发送一位数据所需的时间。我们假设，中间计算机将接收到的数据重定向到自己的出线不需要时间。
网络建成后，Cupa 将计算每台计算机 \(i\) 的网络延迟 \(t_i\) 。他希望所有计算机的总网络延迟（即 \(t_1 + t_2 + \ldots + t_n\) ）越小越好。
请帮助 Cupa 以最小化总网络延迟的方式构建网络。
输入
第一行包含两个整数 \(n\) 和 \(k\) - 计算机数量和集线器端口数量（ \(1 \leq k \leq n \leq 100\) ）。
第二行包含 \(n\) 个整数 \(d_1, d_2, \ldots, d_n\) - 通过每台计算机的线路传输数据的时间列表（ \(1 \leq d_i \leq 100\) ）。
*输出
打印一个整数--可能的最小总网络延迟。
题解
考虑每台计算机向 hub 发送数据的过程，要么这台计算机直接连接在 hub 上，要么计算机首先连接到另一台计算机，随后经过零次或若干个其他计算机到达 hub。直观上，越靠近 hub 的计算机应当时延越小，否则无法最小化总体时延
容易构造出最优策略如下：首先选出时延最小的 \(k\) 个计算机，分别接在 hub 的 \(k\) 个直连口上。对于剩下的计算机，按时延从小到大依次处理，每次把当前计算机接在时延最小的计算机口上，然后更新这个接口的时延并累计总时间即可。
AC 代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int sum = 0;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < k; i++) {
sum += a[i];
pq.push(a[i]);
}
int p = k;
while (p < n) {
sum += pq.top() + a[p];
pq.push(a[p] + pq.top());
pq.pop();
p++;
}
cout << sum << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
L.Limited Swaps
题目翻译
莉娜正在玩摆成一排的 \(n\) 立方体。每个立方体上都写有一个从 \(1\) 到 \(n\) 的整数。从 \(1\) 到 \(n\) 的每个整数都正好出现在一个立方体上。
最初，立方体上从左到右的数字是 \(a_1, a_2, \ldots, a_n\) 。丽娜希望立方体上从左到右的数字是 \(b_1, b_2, \ldots, b_n\) 。
丽娜可以交换任意两个相邻的立方体，但前提是这两个立方体上的数字之差至少为 \(2\) 。这个操作最多可以进行 \(20\,000\) 次。
请找出能将立方体上数字的初始配置转化为所需配置的任何交换序列，否则就报告说这是不可能的。
输入
第一行包含一个整数 \(n\) 。- 立方体的个数（ \(1 \le n \le 100\) ）。
第二行包含 \(n\) 个不同的整数 \(a_1, a_2, \ldots, a_n\) - 从左往右依次是立方体上的初始数字（ \(1 \le a_i \le n\) ）。
第三行包含 \(n\) 个独立整数 \(b_1, b_2, \ldots, b_n\) - 立方体上从左到右的期望数字（ \(1 \le b_i \le n\) ）。
输出
如果无法从初始立方体上获得所需的数字配置，则打印一个整数 \(-1\) 。
否则，请在第一行打印一个整数 \(k\) - 序列中的交换次数（ \(0 \le k \le 20\,000\) ）。
在第二行中，打印 \(k\) 个整数 \(s_1, s_2, \ldots, s_k\) 以描述操作顺序（ \(1 \le s_i \le n - 1\) ）。整数 \(s_i\) 表示 "将左边的 \(s_i\) -th 立方体与左边的 \((s_i + 1)\) -th 立方体交换"。
不必找到最短的解。任何满足约束条件的解都会被接受。
题目
如果忽略交换的约束，这就是一个冒泡排序的过程，一定可以在 \(O(n^2)\) 时间复杂度排序成功，所需要的 swap 次数明显低于 \(20\,000\)。
因此关键问题是在约束条件下，什么情况是不能完成交换的。显然，这个约束可以等价要求 \(a_i\) 和 \(a_{i + 1}\) 之间位置关系不能变化。
赛时，我用拓扑排序来处理这个关系。利用数组 \(a\) 建立一个图，对每个 \(a_i\)，若它前面出现了 \(a_i - 1\) 或 \(a_i + 1\)，就连接一条从 \(a_i - 1\) 或 \(a_i + 1\) 出发，指向 \(a_i\) 的边。
按照数组 \(b\) 处理这个图，枚举到 \(b_i\) 时检查它的入度，若不为零则说明破坏了 \(a\) 构造的限制，输出 \(-1\) 并退出程序即可；否则将它的所有出边去除，更新对应点的入度。
AC 代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<vector<int>> edges(n + 1);
vector<int> a(n);
vector<int> idx(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
idx[a[i]] = i;
}
bitset<101> vis;
vector<int> indeg(n + 1);
for (int i = 0; i < n; i++) {
int pre = a[i] - 1, nxt = a[i] + 1;
if (vis[pre]) {
edges[pre].push_back(a[i]);
indeg[a[i]]++;
} else if (vis[nxt]) {
edges[nxt].push_back(a[i]);
indeg[a[i]]++;
}
vis[a[i]] = true;
}
vis.reset();
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> b[i];
}
for (int i = 0; i < n; i++) {
if (indeg[b[i]] == 0) {
vis[b[i]] = true;
for (int j : edges[b[i]]) {
indeg[j]--;
}
} else {
cout << "-1\n";
return;
}
}
bool allSame = false;
vector<int> ans;
while(!allSame) {
allSame = true;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
allSame = false;
for (int j = i + 1; j < n; j++) {
if (a[j] == b[i]) {
for (int k = j; k > i; k--) {
swap(a[k], a[k - 1]);
ans.push_back(k);
}
}
}
break;
}
}
}
cout << ans.size() << '\n';
for (int i : ans) {
cout << i << ' ';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
赛后总结，实际上按照这道题的数据范围，我可以直接枚举所有的 \(a_i\) 和 \(a_i + 1\)，并直接在 \(a\) 和 \(b\) 中检查位置关系是否一致：
AC 代码 - 简化判断
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
int PointerA = -1, PointerB = -1, NextA = -1, NextB = -1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[j] == i) PointerA = j;
if (a[j] == i + 1) NextA = j;
if (b[j] == i) PointerB = j;
if (b[j] == i + 1) NextB = j;
}
if ((PointerA > NextA) != (PointerB > NextB)) {
cout << "-1\n";
return;
}
}
bool allSame = false;
vector<int> ans;
while (!allSame) {
allSame = true;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
allSame = false;
for (int j = i + 1; j < n; j++) {
if (a[j] == b[i]) {
for (int k = j; k > i; k--) {
swap(a[k], a[k - 1]);
ans.push_back(k);
}
}
}
break;
}
}
}
cout << ans.size() << '\n';
for (int i : ans) {
cout << i << ' ';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
B.Bricks in the Wall
题目描述
鲍勃正在用砖块装饰一面阁楼式长方形墙壁。这面墙由 \(n \times m\) 个单元格组成。有些单元格已被砖块占据，而其余单元格是空的。
鲍勃想在这堵墙上再增加两块砖。新砖的宽度必须等于 \(1\) 个单元，长度可以是任意正整数。每块砖只能水平或垂直放置，因此每块新砖将占据一行或一列中的几个连续的空单元格。此外，这两块砖不能相交，即占据同一个单元格。
鲍勃最多可以在这面墙中添加两块新砖，那么这两块新砖的最大长度总和是多少？
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\) ( \(1 \le t \le 10^4\) )。测试用例说明如下。
每个测试用例的第一行包含两个整数 \(n\) 和 \(m\) --墙的高度和宽度（ \(1 \le n, m\) ; \(n \cdot m \le 10^6\) ）。
接下来的 \(n\) 行分别包含 \(m\) 个字符，描述了墙的情况。占用的单元格用 "#"表示，空单元格用". "表示。
保证所有测试用例中 \(n \cdot m\) 的总和不超过 \(10^6\) 。
输出
对于每个测试用例，打印一个整数 - 最多两个新砖的长度之和的最大可能值。