题解 | 牛客周赛 Round 129

参考代码放在最后面。

思路

A.小红的大小判断

按照题意模拟即可，其实只要特判 是相等情况，其余都是 更大。

B.小红的大小再判断

按照题意模拟即可，可以使用 std::reverse 快速翻转。

C.小红的肥鹅健身房

把所有非空元素用 std::map 存储，然后遍历时每数量逢二进一即可。

时间复杂度

D.小红的神秘密码解锁

一个关键性质：区间内翻转并不会影响区间内相邻连通块数量，仅会影响区间边缘的连通块数量，例如 0[001110]1，区间内 001110 无论如何翻转不会影响连通块数量，只有 0[0 和 0]1 边缘有影响。

所以每个边缘只有三种情况：

• 连通块数量 。
• 连通块数量不变。
• 连通块数量 。

其中第二组情况存在且仅存在于字符串开头与结尾处。（即恰好为整个串）

于是我们遍历右端点时顺便求出对应左端点数量即可。

时间复杂度为 。

E.小红的多维空间冒险

考虑将每一维拆出来，当且仅当 时对距离有贡献。

所以贡献为 的 情况有 和 ，贡献为 的情况的有 和 。

对于 的情况，其方案有 ，由于 和 作为同一种情况，所以要最后除以 。

F.小红的魔法树探险

有题意可得，能量的链一定是从 号点出发形成的一条链。

我们可以考虑以 为根求解。

设到达点 的概率为 ，点 的度为 ，深度为 ，此时存在两种情况：

1. 下一个点到达之前已经到达过的点，则期望值增加 。
2. 下一个点到达之前未到达过的点，则以 继续讨论。

以上过程只需进行树上 dfs 即可。

代码

A.小红的大小判断

void solve(){
    int n;
    cin >> n;
    if (n == 1) cout << "equal";
    else cout << "right";
}

B.小红的大小再判断

void solve(){
    string a,b;
    cin >> a;
    b = a;
    reverse(b.begin(),b.end());
    if (a == b) cout << "equal";
    else if (a < b) cout << "right";
    else cout << "left";
}

C.小红的肥鹅健身房

void solve(){
    int n,m,k;
    cin >> n >> m >> k;
    map<int,int> mp;
    int cnt = 0,coin = 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            int x;
            cin >> x;
            if (x > 0) mp[x]++;
        }
    }
    for (auto [x,y] : mp){
        if (y > 1){
            mp[x+1] += y/2;
            cnt += y/2;
            if (x+1 >= k) coin += y/2;
        }
    }
    cout << cnt << " " << coin;
}

D.小红的神秘密码解锁

using i64 = long long;
void solve(){
    string s;
    cin >> s;
    int n = s.size();
    i64 ans = 1,add = 0;
    for (int i = 1;i < n-1;i++){
        if (s[i] == s[i-1]) add++;
        if (s[i] == s[i+1]) {
            ans += i-add;
        } else {
            ans += add;
        }
    }
    cout << ans << "\n";
}

E.小红的多维空间冒险

using Z = ModInt<1000000007>;
void solve(){
    int n;
    cin >> n;
    for (int k = 1;k <= n;k++){
        int x = n - k;
        cout << Z::Pow(2,n-1) * comb.C(n,k) << " \n"[k==n];
    }
}

F.小红的魔法树探险

using Z = ModInt<1000000007>;
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> G(n+1);
    for (int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> dep(n+1);
    Z ans = 0;
    auto dfs = [&](auto&& dfs,int u,int pa,Z p)->void {
        p /= G[u].size();
        dep[u] = dep[pa] + 1;
        for (int v : G[u]){
            if (v == pa) ans += dep[u] * p;
            else dfs(dfs,v,u,p);
        }
    };
    dfs(dfs,1,1,1);
    cout << ans << "\n";
}

模板

取模类与组合数

template <long long MOD>
struct ModInt{
    long long val = 0;
    ModInt(long long x = 0):val(norm(x)){}
    long long operator()(){ return val; }
    constexpr ModInt operator-() const {
        return ModInt(MOD - val);
    }
    constexpr ModInt operator~() const {
        assert(val != 0);
        return Pow(val,MOD-2);
    }
    constexpr ModInt& operator+=(ModInt x){
        return val += x(),val = norm(val),*this;
    }
    constexpr ModInt& operator-=(ModInt x){
        return val -= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator*=(ModInt x){
        return val *= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator/=(ModInt x){
        return val *= (~x)(),val = norm(val),*this;
    }
    constexpr ModInt& operator^=(long long y){
        return val = Pow(*this,y)(),*this;
    }
    constexpr ModInt& operator++(){
        return val ++,val = norm(val),*this;
    }
    constexpr ModInt operator++(int){
        ModInt v = *this;
        return val ++,val = norm(val),v;
    }
    constexpr ModInt& operator--(){
        return val --,val = norm(val),*this;
    }
    constexpr ModInt operator--(int){
        ModInt v = *this;
        return val --,val = norm(val),v;
    }
    constexpr friend ModInt operator+(ModInt x, ModInt y){
        return x += y;
    }
    constexpr friend ModInt operator-(ModInt x, ModInt y){
        return x -= y;
    }
    constexpr friend ModInt operator*(ModInt x, ModInt y){
        return x *= y;
    }
    constexpr friend ModInt operator/(ModInt x, ModInt y){
        return x /= y;
    }
    constexpr friend ModInt operator^(ModInt x, long long y){
        return x ^= y;
    }
    constexpr friend std::ostream& operator<<(std::ostream& os,ModInt x){
        return os << x();
    }
    constexpr friend std::istream& operator>>(std::istream& is,ModInt &x){
        is >> x.val, x.val = norm(x.val);
        return is;
    }
    constexpr static long long norm(long long x){
        return x < 0 ? (x % MOD + MOD) % MOD : x % MOD;
    }
    constexpr static ModInt Pow(ModInt x,long long y){
        ModInt ans = 1;
        for (;y; y >>= 1,x *= x)
            if (y & 1) ans *= x;
        return ans;
    }
};
template <long long MOD>
struct Combination{
    int siz = 0;
    using Z = ModInt<MOD>;
    std::vector<Z> fact,inv;
    Combination():siz(1),fact(1,1),inv(1,1){}
    void expend(int size){
        if (siz >= size) return;
        fact.resize(size),inv.resize(size);
        for (int i = siz;i < size;i++) fact[i] = fact[i-1] * i;
        inv[size-1] = 1 / fact[size-1];
        for (int i = size - 2;i >= siz;i--) inv[i] = inv[i+1] * (i+1);
        siz = size;
    }
    void check(int size){
        if (siz >= size) return;
        int n = siz;
        while(n < size) n <<= 1;
        n = std::min<unsigned int>(n,MOD);
        expend(n);
    }
    Z A(int n,int m){
        if (n < 0 || m < 0 || n < m) return 0;
        check(n+1);
        return fact[n]*fact[n-m];
    }
    Z C(int n,int m){
        if (n < 0 || m < 0 || n < m) return 0;
        if (n < MOD && m < MOD) {
            check(n+1);
            return fact[n] * inv[m] * inv[n - m];
        } else return C(n/MOD,m/MOD)*C(n%MOD,m%MOD);
    }
};
 
Combination<1000000007> comb;
 
using Z = ModInt<1000000007>;

主程序

#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;
}

/*
 | Code By Kendieer
 | Model Updated : 2025/12/09
 | Code With VSCode
*/

The End

这场难度还是比较简单的。