巅峰赛#19
2025-04-03 11:36:40
发布于：浙江
ACGO 巅峰赛#19 题解
本场巅峰赛的所有题目的难度评级为：
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 变色龙 | 入门 |
| T2 | 打印机 | 入门 |
| T3 | 机器人 | 普及- |
| T4 | 公告 | 普及+/提高- |
| T5 | 登塔 | 普及+/提高- |
| T6 | 24点 | 普及+/提高 |
题目解析
模拟
题目描述，给定两个 的矩阵，求两个矩阵中的有多少个相同位置的大小为 的二维矩阵是不同的,由于n,m比较小，因此可以直接枚举左上角的点，然后枚举两个矩阵相应位置的 矩阵的点，如果有不同就加入统计。
时间复杂度 O()
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> v1(n + 1), v2(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v1[i];
v1[i] = " " + v1[i];
}
for (int i = 1; i <= n; i++) {
cin >> v2[i];
v2[i] = " " + v2[i];
}
int t = 0;
//枚举左上角点的位置；
for (int i = 1; i <= n - m + 1; i++) {
for (int j = 1; j <= n - m + 1; j++) {
bool f = false;
for (int k = i; k <= i + m - 1; k++) {
for (int l = j; l <= j + m - 1; l++) {
if (v1[k][l] != v2[k][l]) t++, f = true;
if (f) break;
}
if (f) break;
}
}
}
cout << t << endl;
}
模拟
在处理试卷打印时，仅需考虑单面打印和双面打印这两种情形。对于双面打印，需要留意的是，若某页纸的正面或反面任意一面需要彩色打印，那么这一整张纸都要采用彩色打印。我们可以运用集合（set）来对最终结果加以统计。
时间复杂度 O()
代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
void solve() {
i64 a, b, c, d;
cin >> a >> b >> c >> d;
i64 n, m;
cin >> n >> m;
i64 mins = a * m + (n - m) * c;
set<int> s;
set<int> s2;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
s2.emplace(x);
x++;
s.emplace(x / 2);
}
mins = min(mins, (i64) (b * s.size() + ((n + 1) / 2 - s.size()) * d));
cout << mins << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t = 1;
while (t--) {
solve();
}
}
C- 机器人
二分
首先，机器人仅能沿横坐标与纵坐标方向移动。基于这一特性，我们可以分别按横坐标和纵坐标，对柱子的信息进行存储。考虑到坐标数值可能较大，使用map进行存储较为合适。
对于横、纵坐标上每个可能出现的点，我们将其存入对应的数组。完成数据存储后，每次机器人移动时，通过二分查找的方法，就能判断机器人当前位置与目标位置之间是否存在柱子。
时间复杂度 (O()
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
map<i64, vector<i64> > mpx;
map<i64, vector<i64> > mpy;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
mpx[x].emplace_back(y);
mpy[y].emplace_back(x);
}
for (auto &i: mpx) {
auto &[_,v] = i;
sort(v.begin(), v.end());
}
for (auto &i: mpy) {
auto &[_,v] = i;
sort(v.begin(), v.end());
}
i64 nowx = 0, nowy = 0;
auto sub = [&](vector<i64> &v, i64 x, i64 to) {
if (v.empty() || v.back() < x - to || v.front() > x) return x - to;
int l = 0, r = v.size() - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (v[mid] <= x) l = mid;
else r = mid - 1;
}
if (v[l] >= x - to ) return v[l] + 1;
return x - to;
};
auto add = [&](vector<i64> &v, i64 x, i64 to) {
if (v.empty() || v.front() > x + to || v.back() < x) return x + to;
int l = 0, r = v.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (v[mid] >= x) r = mid;
else l = mid + 1;
}
if (v[l] <= x + to) return v[l] - 1;
return x + to;
};
for (int i = 1; i <= m; i++) {
char c;
i64 z;
cin >> c >> z;
if (c == 'r') {
nowx = add(mpy[nowy], nowx, z);
} else if (c == 'l') {
nowx = sub(mpy[nowy], nowx, z);
} else if (c == 'w') {
nowy = add(mpx[nowx], nowy, z);
} else {
nowy = sub(mpx[nowx], nowy, z);
}
}
cout << nowx << " " << nowy << endl;
}
并查集
在解决当前问题时，正向处理存在较大难度，往往需要多次断边，才能成功去除某一连通块。既然直接删边操作复杂，不妨尝试采用离线算法来简化计算。
我们可以逆向思考，将删边操作转换为加边操作。从最后一次删边开始倒序处理，这样问题就转化为：给定一个图，逐步向图中添加边，并在每次加边后确定班长能够通知到的学生集合。我们可以通过并查集解决这个问题。
时间复杂度 O(n)
// #include <testlib.h>
// #include <testlib.h>
#include<bits/stdc++.h>
using namespace std;
const int limit = 1e9 + 1;
class DSU {
public:
DSU(int n, int m) : n(n), fa(n + 1), siz(n + 1) {
iota(fa.begin(), fa.end(), 0);
for (int i = 1; i <= m; i++)siz[i] = 1;
}
int find(int x) {
if (fa[x] != x)fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
fa[x] = y;
siz[y] += siz[x];
}
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool ishead(int x) {
return x == find(x);
}
int size(int x) {
return siz[find(x)];
}
private:
int n;
vector<int> fa;
vector<int> siz;
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<set<int> > edge(n + 1);
for (int i = 1; i <= m; i++) {
int k;
cin >> k;
for (int j = 1; j <= k; j++) {
int s;
cin >> s;
edge[s].emplace(i);
}
}
vector<pair<int, int> > ask(q);
for (auto &[i, j]: ask) {
cin >> i >> j;
edge[i].erase(j);
}
stack<int> ans;
DSU d(n + m + 1 , n);
for (int i = 1; i <= n; i++) {
for (const auto j: edge[i]) d.merge(i, j + n);
}
for (int i = q; i; i--) {
ans.emplace(n - d.size(1));
auto [u,v] = ask[i - 1];
d.merge(u, v + n);
}
while (!ans.empty()) {
auto t = ans.top();
ans.pop();
cout << t << endl;
}
}
动态规划
对于本题，我们先从常规思路入手，考虑从第 层向第 层的状态转移。设 表示处于第 层的第 个房间时所能取得的最大值。那么状态转移方程为 ，其中 且 。
从这个转移方程可以看出， 的转移核心在于找出第 层除第 个房间之外能取得的最大价值。假设第 层价值最大的房间编号为 ，那么在第 层中，除了第 号房间外，其他房间都可以从第 层的 号房间移动过来，从而获取最大价值。而第 层的 号房间，则可以从第 层价值次大的房间转移到达。
基于此，我们发现只需记录每一层价值最大的两个房间的编号，就能实现向下一层的状态转移。这种方法的时间复杂度为 。
注意 m == 1的状况他会被困在第一层
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<i64> > arr(n + 1, vector<i64>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
vector<priority_queue<pair<i64, int>, vector<pair<i64, int> >, greater<> > > f(n + 1);
f[0].emplace(0, 0);
for (int i = 1; i <= n; i++) {
if (f[i - 1].empty()) continue;
for (int j = 1; j <= m; j++) {
auto t = f[i - 1].top();
f[i - 1].pop();
if (!f[i - 1].empty() && f[i - 1].top().second != j) {
f[i].emplace(arr[i][j] + f[i - 1].top().first, j);
} else {
if (t.second != j)
f[i].emplace(arr[i][j] + t.first, j);
}
f[i - 1].emplace(t);
while (f[i].size() > 2) f[i].pop();
}
}
i64 maxs = 0;
for (int i = 1; i <= n; i++) {
while (!f[i].empty()) {
maxs = max(maxs, f[i].top().first);
f[i].pop();
}
}
cout << maxs << endl;
}
抽屉原理
许多同学尝试通过模拟的方法来解决这道题，然而在模拟实现的过程中，一个明显的问题浮现出来：一旦出现错误，检查和调试都极为困难。那么，我们能否通过深入观察题目的性质，来降低模拟的复杂程度呢？
首先，让我们思考这样一个问题：给定任意两个数，我们是否能够通过一定的运算构造出一个 3 的倍数呢？
假设这两个数为 和 。如果其中一个数本身就是 3 的倍数，那么将这两个数相乘即可得到 3 的倍数，这种情况较为简单，我们暂不深入讨论。接下来考虑两个数都不是 3 的倍数的情况，此时它们除以 3 的余数（即模 3 的结果）共有 4 种组合：、、、。经过分析不难发现，对于这四种组合，我们都可以通过加法或者减法运算，使它们得到的结果成为 3 的倍数。由此，我们证明了任意两个数都能够通过适当的运算得到 3 的倍数。
已知 ，此时问题就转化为：给定 4 个数，我们能否从中选取两个数，通过运算构造出 8 的倍数呢？为了简化问题，我们先排除这 4 个数中本身就包含 8 的倍数的情况。那么，当这 4 个数分别除以 8 取余数（即模 8 ）后，结果只会是 1、2、3、4、5、6、7 这 7 种情况。接下来我们思考，这 7 种余数情况中，哪些组合可以构成 8 的倍数呢？
通过计算可知，，，，，（24 也是 8 的倍数）。基于这些组合，我们可以将这 7 种余数情况划分成 3 个集合：，，。在这三个集合中，任意选取集合内的两个数，都可以通过相应的运算构成 8 的倍数。
由于我们一共有 4 个数，根据抽屉原理，这 4 个数中必然会有至少两个数的余数属于同一个集合。所以，我们可以先从这 4 个数中选取 2 个数，构造出 8 的倍数，再通过前面证明的方法构造出 3 的倍数，最后将得到的 8 的倍数和 3 的倍数相乘，就可以得到满足条件的结果。
综上所述，该算法的时间复杂度为 。
#include<bits/stdc++.h>
using namespace std;
string get(int a, int b, int x) {
if ((a + b) % x == 0) {
return "(" + to_string(a) + "+" + to_string(b) + ")";
}
if ((a - b) % x == 0) {
return "(" + to_string(a) + "-" + to_string(b) + ")";
} {
return "(" + to_string(a) + "*" + to_string(b) + ")";
}
};
string get(queue<int> &q, int x) {
int a = q.front();
q.pop();
int b = q.front();
q.pop();
if ((a + b) % x == 0) {
return "(" + to_string(a) + "+" + to_string(b) + ")";
}
if ((a - b) % x == 0) {
return "(" + to_string(a) + "-" + to_string(b) + ")";
} {
return "(" + to_string(a) + "*" + to_string(b) + ")";
}
};
void solve() {
vector<int> a(4);
string ans;
for (auto &i: a) {
cin >> i;
}
queue<int> q1, q2, q3, q4, q5;
for (auto i: a) {
if (i % 8 == 0)q1.emplace(i);
else if (i % 8 == 1 || i % 8 == 7) {
q2.emplace(i);
} else if (i % 8 == 2 || i % 8 == 4 || i % 8 == 6) {
q3.emplace(i);
} else
q4.emplace(i);
}
if (!q1.empty()) {
ans = to_string(q1.front());
q1.pop();
} else if (q2.size() >= 2) {
ans = get(q2, 8);
} else if (q3.size() >= 2) {
ans = get(q3, 8);
} else {
ans = get(q4, 8);
}
while (!q1.empty()) {
q5.emplace(q1.front());
q1.pop();
}
while (!q2.empty()) {
q5.emplace(q2.front());
q2.pop();
}
while (!q3.empty()) {
q5.emplace(q3.front());
q3.pop();
}
while (!q4.empty()) {
q5.emplace(q4.front());
q4.pop();
}
ans = ans + "*" + get(q5, 3);
while (!q5.empty()) {
ans = ans + "*" + to_string(q5.front());
q5.pop();
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
有帮助，赞一个