题解 | 牛客周赛 Round 130

2026-02-09 01:00:43 栏目：最新资讯 4 阅读

A 红美铃的访客登记

可以根据题意进行去前置零的操作

或是直接输入数字，会自动去掉前置零

void solve(){
    string a;
    cin >> a;

    int f = 0;
    for(int i = 0; i < a.size(); ++i) {
        if(a[i] == '0' && f) cout  << '0';
        else if(a[i] != '0'){
            cout << a[i];
            f = 1;
        }
    }
}

void solve() {
    int x;
    cin >> x;
    cout << x << endl;
}

B 爱丽丝的魔力零件分类

检查是否有一个为‘*’的点周围有三个同样为‘*’的点即可

void solve(){
    int n;
    cin >> n;

    vector a(n + 2);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = '.' + a[i] + '.';
    }
    a[0] = "................................";
    a[n + 1] = "................................";

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            int ans = 0;
            if(a[i][j] == '*') {
                if(a[i + 1][j] == '*') ans++;
                if(a[i - 1][j] == '*') ans++;
                if(a[i][j - 1] == '*') ans++;
                if(a[i][j + 1] == '*') ans++;

                if(ans >= 3) {
                    cout << 'T' << endl;
                    return;
                }
            }
        }
    }
    cout << "L" << endl;
}

C 博丽大结界的稳定轴心

先进行建树

当一个节点的子节点个数为1或者是2是，则说明此节点可以为根节点

但是当书中有一个节点的子节点个数超过3，则说明不能构成二叉树则输出0

void solve(){
    int n;
    cin >> n;

    vector> g(n + 1);
    for(int i = 1; i < n; ++i) {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        if(g[i].size() == 1 || g[i].size() == 2)
        ans++;
        if(g[i].size() > 3) {
            cout << 0 << endl;
            return;
        }
    }
    cout << ans << endl;
}

D 魔法人偶的十进制校准

当 i >0 && i < 9 时构造无限循环小数即可

其他特判即可

void solve(){
    int n, m;
    cin >> n >> m;

    if(m == 0) {
        if(n == 1) cout << 1 << ' ' << 100 << endl;
        else cout << 1 << ' ' << 2 << endl;
    }
    else if(m == 1) cout << 1 << ' ' << 9 << endl;
    else if(m == 2) cout << 2 << ' ' << 9 << endl;
    else if(m == 3) cout << 1 << ' ' << 3 << endl;
    else if(m == 4) cout << 4 << ' ' << 9 << endl;
    else if(m == 5) cout << 5 << ' ' << 9 << endl;
    else if(m == 6) cout << 2 << ' ' << 3 << endl;
    else if(m == 7) cout << 7 << ' ' << 9 << endl;
    else if(m == 8) cout << 8 << ' ' << 9 << endl;
    else if(m == 9) {
        if(n % 2 == 1) cout << 10 << ' ' << 11 << endl;
        else cout << 1 << ' ' << 11 << endl;
    }

}

E 爱丽丝的人偶圆舞曲

枚举d可能得情况

后进行动态规划

f[i][j] = min(f[i - 1][(j - d + 26) % 26], f[i - 1][(j + d) % 26]) + (j != t) 即可

void solve(){
    string a;
    cin >> a;
    int n = a.size();
    a = " " + a;

    int ans = 1e9;
    for(int d = 0; d < 26; ++d) {
        vector> f(n + 1, vector (26, 1e9));
        for(int i = 0; i < 26; ++i) {
            if(i == a[1] - 'a') f[1][i] = 0;
            else f[1][i] = 1;
        }

        for(int i = 2; i <= n; ++i) {
            int t = (a[i] - 'a');
            for(int j = 0; j < 26; ++j) {
                f[i][j] = min(f[i - 1][(j - d + 26) % 26], f[i - 1][(j + d) % 26]) + (j != t);
            }
        }
        for(int i = 0; i < 26; ++i)
        ans = min(ans, f[n][i]);
    }
    cout << ans << endl;
}

F 红魔馆的微瑕序位

因为S 为 2

则说明只能有相邻两个的数在对方位置上

先算出置换环的数量（不了解置换环的同学先学习置换环的原理）

后计算出将这个数组排为严格升序的操作次数为 ans = n - cnt;

如果有两个相邻的数且在同一个置换环里则说明减少一次操作直接得到符合题意的数组；

否则还要在进行一次操作才能得到符合题意的数组

void solve(){
    int n;
    cin >> n;

    int op = 0;
    vector a(n + 1), vis(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        op++;
        int j = i;
        while(!vis[j]) {
            vis[j] = op;
            j = a[j];
        }
    }

    int ans = n - op + 1;
    for(int i = 1; i < n; ++i) {
        if(vis[i] == vis[i + 1]) {
            ans -= 2;
            break;
        }
    }

    cout << ans << endl;
}

有任何问题欢迎大家指出^-^

本文地址：https://www.yitenyun.com/6977.html

上一篇：PART4 前缀和

下一篇：Linux apt 命令434