题解 | 牛客周赛 Round 130

参考代码放在最后面。

思路

A.红美铃的访客登记

按题意模拟即可。

B.爱丽丝的魔力零件分类

提供一种做法，如果找到一个点满足四连通有三个 * 则为 T，否则为 L。

C.博丽大结界的稳定轴心

由二叉树定义，存在度大于 $3$ 的点则不是二叉树。

对于每个轴心，其子节点个数为度的大小，否则子节点个数为度的大小 $-1$ ，由此可得度 $\le 2$ 的点都可以成为轴心。

时间复杂度为 $O(n)$

D.魔法人偶的十进制校准

提供一种构造方案。

特判 $b=0$ 和 $b=9$ 的情况。

当 $b=0$ 时，构造 $\frac{1}{10} 和$ \frac{1}{100} $即可。（特判$ a=\lg{y} $从而选不同的$ y$）
当 $b=9$ 时， $a$ 为奇数时构造 $\frac{10}{11}$ ，偶数时为 $\frac{1}{11}$
当 $b=1\sim 8$ 时，构造 $\frac{b}{9}$ 即可，记得化简。

E.爱丽丝的人偶圆舞曲

考虑动态规划，考虑枚举 $d$ ，记 $dp_{i,j}$ 为第 $i$ 为字母改成 $v_i=j$ 时，前缀合法最少需要的修改次数，得到 $dp_{i,j} = \min(dp_{i-1,j-d\bmod 26},dp_{i-1,j+d\bmod 26}) + [j=s_i]$ 。

时间复杂度为 $O(26dn)$ ，其中 $d$ 取 $[0,13]$ 即可。

F.红魔馆的微瑕序位

容易得出性质，最终的排列一定是 $n-2$ 个位置 $a_i=i$ ，剩余两个位置相邻且 $a_i=i+1,a_{i+1}=i$ 。

对于交换操作，我们将其复原成升序排列，设第 $i$ 个置换环大小为 $siz_i$ ，复原所需的步数为 $\Sigma siz_i - 1$ （置换环：可以理解成建图，按照 $i$ 号点建立一条指向 $a_i$ 的有向边，由于给定的是 $1\sim n$ 的排列，所以最后一定是若干个环）。

由上述性质，设互换的两个位置为 $i,i+1$ ，此时可以分两种情况讨论：

若 $i$ 和 $i+1$ 在同一个置换环，则我们可以减少 $1$ 次交换。
否则我们需要使用一次交换 $i$ 和 $i+1$ 。

可以用并查集或者记忆化搜索维护置换环个数，时间复杂度为 $O(n)$ 到 $O(n\alpha(n))$ 。

代码

A.红美铃的访客登记

void solve(){
    string s;
    cin >> s;
    bool tag = 1;
    for (char ch : s){
        if (ch == '0' && !tag) cout << ch;
        else if (ch != '0') {
            cout << ch;
            tag = 0;
        }
    }
}

B.爱丽丝的魔力零件分类

void solve(){
    int n;
    cin >> n;
    int cnt = 0;
    vector<vector<int>> mp(n+2,vector<int>(n+2));
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            char ch;
            cin >> ch;
            mp[i][j] = ch == '*';
             
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            int c = 0;
            c += mp[i][j];
            c += mp[i-1][j];
            c += mp[i+1][j];
            c += mp[i][j-1];
            c += mp[i][j+1];
            cnt = max(c,cnt);
        }
    }
    cout << (cnt == 4 ? "T" : "L") << "\n";
}

C.博丽大结界的稳定轴心

void solve(){
    int n;
    cin >> n;
    vector<int> deg(n+1);
    for (int i = 1;i < n;i++){
        int x,y;
        cin >> x >> y;
        deg[x]++,deg[y]++;
    }
    if (*max_element(deg.begin()+1,deg.end()) > 3){
        cout << "0" << "\n";
    } else {
        cout << n-count(deg.begin()+1,deg.end(),3) << "\n";
    }
}

D.魔法人偶的十进制校准

void solve(){
    int a,b;
    cin >> a >> b;
    if (b == 9){
        if (a & 1) cout << 10 << ' ' << 11 << '\n';
        else cout << 1 << ' ' << 11 << '\n';
    } else if (b == 0){
        if (a == 1) cout << 1 << ' ' << 100 << '\n';
        else cout << 1 << ' ' << 10 << '\n';
    } else {
        int x = b,y = 9;
        int cd = gcd(x,y);
        x /= cd,y /= cd;
        cout << x << ' ' << y << '\n';
    }
}

E.爱丽丝的人偶圆舞曲

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    int ans = n;
    for (int d = 0;d <= 13;d++){
        vector<int> dp(26,1);
        dp[s[0]-'a'] = 0;
        for (int i = 1;i < n;i++){
            int t = s[i] - 'a';
            vector<int> dp2(26,n);
            for (int j = 0;j < 26;j++){
                for (int lst : {(j+d)%26,(j+26-d)%26}){
                    dp2[j] = min(dp2[j],dp[lst]+(t != j));
                }
            }
            swap(dp,dp2);
        }
        ans = min(ans,*min_element(dp.begin(),dp.end()));
    }
    cout << ans << "\n";
}

F.红魔馆的微瑕序位

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    DSU dsu(n);
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for (int i = 1;i <= n;i++){
        int j = a[i];
        while (dsu[a[i]] != dsu[i]){
            dsu(a[j],i);
            j = a[j];
        }
    }
    int ans = n,cnt = 0;
    for (int i = 1;i <= n;i++){
        if (dsu[i] == i) cnt += dsu.size(i) - 1;
    }
    ans = cnt + 1;
    for (int i = 2;i <= n;i++){
        if (dsu[i] == dsu[i-1]) ans = cnt - 1;
    }
    cout << ans << "\n";
}

模板

并查集

struct Disjoint{
    std::vector<int> fa,siz;
    int cnt=0;
    Disjoint(int n = 0){
        init(n);
    }
    void init(int n = 0){
        fa.resize(n+1);
        siz.assign(n+1,1);
        std::iota(fa.begin(),fa.end(),0);
        cnt = n;
    }
    void operator()(int head,int ele){ // merge
        head = root(head),ele = root(ele);
        if (head == ele) return;
        siz[head]+=siz[ele];
        fa[ele]=head;
    }
    int operator[](int index){return root(index);}
    int size(int x){return siz[root(x)];}
private:
    int root(int x){
        return fa[x] = fa[x] == x ? x : root(fa[x]);
    }
};
using DSU = Disjoint;

主程序

#include<bits/stdc++.h>
#if __has_include("tool/local.hpp")
#include "tool/local.hpp"
#include "grader.hpp"
#else
#define Testcases(T) while(T--) solve();
    #ifndef ONLINE_JUDGE
    #define listen(...) freopen("data.in","r",stdin),freopen("data.out","w",stdout);
    #else
    #define listen(...)
    #endif
#endif
using namespace std;
// Base type
using ll = long long;
using ld = long double;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using p32 = std::array<int,2>;
using p64 = std::array<i64,2>;

// mt19937_64 rnd(time(0));

void solve(){
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr),std::cout.tie(nullptr);
    listen(_TIMER,_FILE,_CHECKER);
    int T = 1;
    std::cin >> T;
    Testcases(T);
    return 0;
}

题解 | 牛客周赛 Round 130

思路

A.红美铃的访客登记

B.爱丽丝的魔力零件分类

C.博丽大结界的稳定轴心

D.魔法人偶的十进制校准

E.爱丽丝的人偶圆舞曲

F.红魔馆的微瑕序位

代码

A.红美铃的访客登记

B.爱丽丝的魔力零件分类

C.博丽大结界的稳定轴心

D.魔法人偶的十进制校准

E.爱丽丝的人偶圆舞曲

F.红魔馆的微瑕序位

模板

并查集

主程序

The End