题解 | #本场比赛灵感来源于树状数组出题组#

本场比赛灵感来源于树状数组出题组

https://ac.nowcoder.com/acm/contest/120564/A

这是关于H,F题的个人看法

H|时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

核心思路

  1. 预处理:计算网格中每个格子放置加农炮能消灭的总敌人数;
  2. 动态更新:给定 q 次增援操作,每次在格子 (x,y) 增加 z 个敌人,该增援会影响以 (x,y) 为中心、曼哈顿距离 ≤ 2 的所有格子的 “总消灭数”;
  3. 实时查询:每次增援后,输出当前能消灭最多敌人的加农炮放置位置(若有多个最大值,输出任意一个即可)。

代码展示

#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串构造

将数量较多的字符均匀地 “插入” 到数量较少的字符之间,以避免长段连续字符:

  1. 判断数量:比较 0 和 1 的数量,决定以谁为主进行构造。
  2. 均匀分配: 如果 0 多(n > m),就把 0 均匀地分配到每个 1 的前后; 如果 1 多(m >= n),就把 1 均匀地分配到每个 0 的前后。
  3. 循环构造:在每一步,计算当前应输出的连续字符数量,输出后更新剩余计数,直到所有字符都被用完。

代码展示

#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;
}
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务