题解 | #本场比赛灵感来源于树状数组出题组#
本场比赛灵感来源于树状数组出题组
https://ac.nowcoder.com/acm/contest/120564/A
这是关于H,F题的个人看法
H|时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学
核心思路
- 预处理:计算网格中每个格子放置加农炮能消灭的总敌人数;
- 动态更新:给定 q 次增援操作,每次在格子 (x,y) 增加 z 个敌人,该增援会影响以 (x,y) 为中心、曼哈顿距离 ≤ 2 的所有格子的 “总消灭数”;
- 实时查询:每次增援后,输出当前能消灭最多敌人的加农炮放置位置(若有多个最大值,输出任意一个即可)。
代码展示
#include <bits/stdc++.h>
using namespace std;
int dx[13] = {0, 0, 1, 2, 0, 0, -1, -2, 1, 1, -1, -1, 0};
int dy[13] = {1, 2, 0, 0, -1, -2, 0, 0, 1, -1, 1, -1, 0};
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<long long>> a(n + 3, vector<long long>(m + 3, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
long long val;
cin >> val;
for (int k = 0; k < 13; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) {
a[ni][nj] += val;
}
}
}
}
long long max_val = -1;
int p1 = 1, p2 = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] > max_val) {
max_val = a[i][j];
p1 = i;
p2 = j;
}
}
}
while (q--) {
int x, y, z;
cin >> x >> y >> z;
for (int k = 0; k < 13; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
a[nx][ny] += z;
if (a[nx][ny] > max_val) {
max_val = a[nx][ny];
p1 = nx;
p2 = ny;
}
}
}
cout << p1 << " " << p2 << "\n";
}
return 0;
}
F|爱音的01串构造
将数量较多的字符均匀地 “插入” 到数量较少的字符之间,以避免长段连续字符:
- 判断数量:比较 0 和 1 的数量,决定以谁为主进行构造。
- 均匀分配: 如果 0 多(n > m),就把 0 均匀地分配到每个 1 的前后; 如果 1 多(m >= n),就把 1 均匀地分配到每个 0 的前后。
- 循环构造:在每一步,计算当前应输出的连续字符数量,输出后更新剩余计数,直到所有字符都被用完。
代码展示
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long a, b;
cin >> a >> b;
if (a > b) {
while (b > 0) {
long long num = a / (b + 1);
for (long long i = 0; i < num; ++i) cout << '0';
cout << '1';
a -= num;
b--;
}
while (a--) cout << '0';
} else {
while (a > 0) {
long long num = b / (a + 1);
for (long long i = 0; i < num; ++i) cout << '1';
cout << '0';
b -= num;
a--;
}
while (b--) cout << '1';
}
cout << '\n';
}
return 0;
}