ACGO巅峰赛#19题解简评
2025-04-05 23:27:56
发布于：北京
8阅读
2回复
1点赞
T1 - 变色龙
完整代码
#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; break; }
if (f) break;
}
cout << t << endl;
}
深度分析
关键公式
子矩阵枚举范围：
[
i \in [1, n - m + 1], \quad j \in [1, n - m + 1]
]
常见错误
- 子矩阵范围错误：写成
i <= n导致越界。 - 字符比较错误：直接比较
v1[k][l]和v2[k][l]的 ASCII 值而非字符。
改进建议
- 哈希优化：预处理每个子矩阵的哈希值，比较哈希值而非逐字符。
- 提前终止：当子矩阵左上角不同时，跳过整个区域。
- 输入验证：添加
if (m > n)处理无效输入。
T2 - 打印机
完整代码
#include<bits/stdc++.h>
using namespace std;
void solve() {
long long a, b, c, d; cin >> a >> b >> c >> d;
long long n, m; cin >> n >> m;
long long mins = a*m + (n-m)*c;
set<int> s, s2;
for (int i=1; i<=m; i++) {
int x; cin >> x;
s2.insert(x);
x++;
s.insert(x/2);
}
mins = min(mins, 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();
}
深度分析
关键公式
双面打印纸张数：
[
\text{pages} = \left\lceil \frac{m}{2} \right\rceil
]
常见错误
- 奇数页处理错误：
x/2未考虑向上取整。 - 边界条件遗漏：未处理
m=0或n=0。
改进建议
- 数学简化：直接计算
(m + 1) // 2代替集合操作。 - 逻辑优化：比较单面和双面成本时，统一使用整数运算。
- 测试用例：添加
m=0、n=0和m=1的测试。
T3 - 机器人
完整代码
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m; cin >> n >> m;
map<long long, vector<long long>> mpx, mpy;
for (int i=1; i<=n; i++) {
int x, y; cin >> x >> y;
mpx[x].push_back(y);
mpy[y].push_back(x);
}
for (auto &[_,v]: mpx) sort(v.begin(), v.end());
for (auto &[_,v]: mpy) sort(v.begin(), v.end());
auto sub = [&](vector<long long> &v, long long x, long long to) {
if (v.empty() || v.back() < x - to) 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;
}
return v[l] >= x - to ? v[l]+1 : x - to;
};
auto add = [&](vector<long long> &v, long long x, long long to) {
if (v.empty() || v.front() > x + to) 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;
}
return v[l] <= x + to ? v[l]-1 : x + to;
};
long long nowx=0, nowy=0;
for (int i=1; i<=m; i++) {
char c; long long 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;
}
深度分析
关键公式
移动后的坐标：
[
\text{new_x} = \begin{cases}
\text{障碍物右侧第一个空位} & \text{向右} \
\text{障碍物左侧第一个空位} & \text{向左} \
\text{障碍物上侧第一个空位} & \text{向上} \
\text{障碍物下侧第一个空位} & \text{向下}
\end{cases}
]
常见错误
- 二分查找方向错误：
add函数中未正确比较v[mid] >= x。 - 坐标越界：未处理移动后超出网格范围的情况。
改进建议
- 二分优化：使用
lower_bound和upper_bound替代手写二分。 - 边界限制：添加
nowx和nowy的范围约束。 - 代码复用：合并
add和sub函数为通用移动逻辑。
T4 - 公告
完整代码
#include<bits/stdc++.h>
using namespace std;
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]; }
int size(int x) { return siz[find(x)]; }
private:
int n;
vector<int> fa, 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].insert(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 (auto j: edge[i]) d.merge(i, j + n);
for (int i=q; i; i--) {
ans.push(n - d.size(1));
auto [u,v] = ask[i-1];
d.merge(u, v + n);
}
while (!ans.empty()) cout << ans.top() << endl, ans.pop();
}
深度分析
关键公式
并查集合并：
[
\text{size}[y] += \text{size}[x]
]
常见错误
- 节点编号混淆：学生和边的编号未正确区分。
- 逆向处理错误：未正确恢复边的状态。
改进建议
- 节点编号设计：将学生和边的编号范围明确划分（如学生
1~n，边n+1~n+m）。 - 离线处理优化：使用栈记录合并操作，逆向时撤销合并。
- 空间优化：改用
vector<vector<int>>存储边。
T5 - 登塔
完整代码
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<long long>> arr(n+1, vector<long long>(m+1));
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
cin >> arr[i][j];
vector<priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>>> f(n+1);
f[0].push({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].push({arr[i][j] + f[i-1].top().first, j});
else if (t.second != j)
f[i].push({arr[i][j] + t.first, j});
f[i-1].push(t);
while (f[i].size() > 2) f[i].pop();
}
}
long long 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;
}
深度分析
关键公式
状态转移方程：
[
f[i][k] = \max_{j \neq k} f[i-1][j] + a[i][k]
]
常见错误
- 极值维护错误：优先队列未正确维护前两大值。
- 特殊情况处理：未处理
m=1时无法移动的情况。
改进建议
- 极值优化：直接记录每一层的最大值和次大值，而非依赖优先队列。
- 边界处理：在
m=1时，直接输出arr[1][1]。 - 动态规划优化：将状态压缩为两个数组（当前层和前一层）。
T6 - 24点
完整代码
#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) + ")";
}
void solve() {
vector<int> a(4);
for (auto &i: a) cin >> i;
queue<int> q1, q2, q3, q4, q5;
for (auto i: a) {
if (i % 8 == 0) q1.push(i);
else if (i % 8 == 1 || i % 8 == 7) q2.push(i);
else if (i % 8 == 2 || i % 8 == 4 || i % 8 == 6) q3.push(i);
else q4.push(i);
}
string ans;
if (!q1.empty()) ans = to_string(q1.front()), q1.pop();
else if (q2.size() >= 2) ans = get(q2.front(), q2.back(), 8), q2.pop(), q2.pop();
else if (q3.size() >= 2) ans = get(q3.front(), q3.back(), 8), q3.pop(), q3.pop();
else ans = get(q4.front(), q4.back(), 8), q4.pop(), q4.pop();
while (!q1.empty()) q5.push(q1.front()), q1.pop();
while (!q2.empty()) q5.push(q2.front()), q2.pop();
while (!q3.empty()) q5.push(q3.front()), q3.pop();
while (!q4.empty()) q5.push(q4.front()), q4.pop();
ans += "*" + get(q5, 3);
while (!q5.empty()) 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();
}
深度分析
关键公式
8的倍数构造：
[
\begin{cases}
1 + 7 = 8 \
3 + 5 = 8 \
2 \times 4 = 8 \
2 + 6 = 8 \
4 \times 6 = 24
\end{cases}
]
常见错误
- 余数分类遗漏：未处理
i=0的情况。 - 表达式构造错误：未考虑除法。
改进建议
- 余数分类完善：添加
i=0的处理逻辑。 - 表达式验证：生成表达式后计算结果，确保等于24。
- 除法实现：添加除法判断逻辑，处理整除情况。
全题改进总结
- 算法优化：优先使用哈希、并查集等高效数据结构。
- 边界处理：重视输入范围和特殊情况（如
m=0、n=1）。 - 代码规范：拆分复杂函数，添加注释，避免冗余逻辑。
- 数学思维：加强模运算、抽屉原理等数学方法的应用。
- 测试覆盖：针对不同数据范围和边界条件设计测试用例。
致歉：
部分LaTeX & Markdown公式无法在ACGO上完整显示，对于公式显示不全导致您阅读困难的情况，深表歉意😣
写法支持：
Markdown的常用语法讲解
LaTeX数学公式的常用语法讲解
鸣谢：
各位大佬有什么意见就在评论区提，很感谢也很期待各位大佬们的指正
有帮助，赞一个