1103 字
3 分钟
Atcoder_Beginner_Contest_460(A~D题)
2026-06-01
ABC题解
浏览量 83 · 访客 16

缘结甘神家式神！

题目链接：https://atcoder.jp/contests/abc460/tasks

A - Mod While Positive#

数据比较小，我们直接按题意写一个循环并记录循环结束时次数即可。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


void solved() {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    while(m){
        int x = n % m;
        m = x;
        cnt++;
    }
    cout << cnt << endl;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while(_--){
        solved();
    }
    return 0;
}

B - Two Rings#

高中知识，求两个坐标圆是否有交点。也就是dd(两圆心之间的距离) <= r1r1 + r2r2或者dd + r1r1(较小的半径) >= r2r2(较大的半径)。这两个条件就可以满足相切和相交的所有情况了。此外还要注意特判两个是完全相同的圆的情况。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


void solved() {
    ll t;
    cin >> t;
    while(t--){
        ll x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1>>  x2 >> y2 >> r2;
        if(x1 == x2 && y1 == y2 && r1 == r2) {cout << "Yes" << endl; continue;}
        if((sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) <= r1 + r2)
        && sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) + min(r1, r2) >= max(r1, r2)){
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while(_--){
        solved();
    }
    return 0;
}

C - Sushi#

这里我们从小到大排序饭和配料。我这里以配料为基准，然后判断每个饭能否满足条件(配料重量 <= 2×2 \times 饭重量)。然后用xx表示目前配对的饭的下标。如果当前的配料和对应xx的饭满足条件我们就结果cntcnt加11，否则我们就继续看这个配料能否和下一个饭(xx++)配对。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


ll a[200010];
ll b[200010];


void solved() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= m;i++) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    int x = 1;
    int cnt = 0;
    for(int i = 1; i <= m && x <= n;i++){
        if(b[i] <= 2 * a[x]) cnt++;
        else i--; x++;
    }
    cout << cnt << endl;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while(_--){
        solved();
    }
    return 0;
}

D - Repeatedly Repainting#

这题我们首先需要发现一个规律，经过一定次数的操作之后我们的这种翻转染色的趋势会因为变色的范围是88邻域而不断扩散，最终整个网格都会被覆盖。然后最终的图像会变成奇数一种图，偶数就是颜色翻转的另一种图。并且最终一定是这样的结果。（奇偶变图，因为操作次数为1010010^{100}，足以保证完全扩散到整个网格）
那么我们就可以先模拟这个扩散的过程，然后将每一个一开始就能够进行扩散的黑格（周围八格有白格才能扩散）作为源点不断向外标记状态。举个例子，初始黑格的周围八格如果有一个白格，一次操作后这个白格就会变为黑格，原来的黑格就会变成白格。然后变黑的那一个白格会继续扩散，它周围未探索过的白格在第二次操作后就会变成黑色，而初始为黑格的会重新由白变黑。（被探索过的格子已经进入奇偶振荡，不受新的扩散源点影响，这很关键）但这里我们发现一个问题，如果我们直接记录对应的格子最终结果状态为黑或白会非常混乱。我们不妨再观察一下格子变化的规律：
我们以初始源点(初始黑格)为基准，设定距离。源点距离为00，源点周围88格距离为11，然后周围八格的八格的距离为22。我们尝试模拟一下就可以发现，距离我们源点距离为偶数的最终结果就是黑色，奇数的就是白色。由此我们可以根据我们的初始源点探索出未探索的每一个格子的距离是多少，确定最终的每个格子状态。同时根据前面我们的观察可知，最终格子的振荡趋势只跟第一次到达该格的源点变化趋势有关。（也就是该格的距离只需要记录第一次记录的值即可）我们完全可以使用bfsbfs直接记录相应每个格子的距离最近源点的最短路。然后经过操作1010010^{100}次，也就是偶数次的结果网格和初始是一样的，（初始操作为00次也是偶数次）所以我们按照距离表格，偶数输出′#′'\#'，奇数输出′.′'.'即是答案了。
这里还要注意的一点是，如果一个黑格没有办法作为源点的话我们就默认为−1-1(距离数组的初始值)即可，因为当它第一次变成白色之后就永远是白格了，并且它的距离在一次搜索时就会被设置为11，也就是白格，不会干扰结果。而对于全是白格和黑格的网格直接输出白格即可，因为这两种图都无法进行扩散和变换。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


int dx[9] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
int dy[9] = {0, -1, 0, 1, -1, 1, -1, 0, 1};


void solved() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h + 1);


    int black_cnt = 0;
    for(int i = 1; i <= h;i++){
        cin >> grid[i];
        grid[i] = " " + grid[i];
        for(char c : grid[i]) if(c == '#') black_cnt++;
    }
    //全白或着全黑就直接输出全白表格
    if(black_cnt = 0 || black_cnt == h * w){
        for (int i = 0; i < h;i++){
            cout << string(w, '.') << endl;
        }
        return;
    }
    //距离数组
    vector<vector<int>> dist(h + 1, vector<int>(w + 1, -1));
    queue<pii> q;
    //找出所有的源点黑格加入队列中
    for (int i = 1; i <= h;i++){
        for (int j = 1; j <= w;j++){
            if(grid[i][j] == '#'){
                bool has_white = false;
                for (int k = 1; k <= 8;k++){
                    int ni = i + dx[k], nj = j + dy[k];
                    if(ni >= 1 && ni <= h && nj >= 1 && nj <= w){
                        if(grid[ni][nj] == '.'){
                            has_white = true;
                            break;
                        }
                    }
                }
                if(has_white){
                    dist[i][j] = 0;
                    q.emplace(i, j);
                }
            }
        }
    }
    //bfs，模拟扩散过程然后记录每个格距离源点的最短距离
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for (int i = 1; i <= 8; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 1 && nx <= h && ny >= 1 && ny <= w && dist[nx][ny] == -1){
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }
    //根据距离表格，奇数输出白格，偶数输出黑格
    for (int i = 1; i <= h;i++){
        for (int j = 1; j <= w;j++){
            cout << (dist[i][j] & 1 ? '.' : '#');
        }
        cout << endl;
    }
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while(_--){
        solved();
    }
    return 0;
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

Atcoder_Beginner_Contest_460(A~D题)
https://mkrari.cn/posts/abc_460/
作者
Mkrari
发布于
2026-06-01
许可协议
CC BY-NC-SA 4.0
Atcoder_Beginner_Contest_461(A~D题)
moectf2025_pwn_part.4(详细审计_14~18)
© 2026 Mkrari. All Rights Reserved. /RSS /Atom /Sitemap
Powered byAstro &Mizuki  Version 8.2