牛客周赛Round31

A.小红小紫替换

判断即可

$code:$

void solve() {
    std::string s;
    std::cin >> s;   
    std::cout << (s == "kou" ? "yukari" : s) << '\n';
    
}

B.小红的因子数

看到数据范围为 $1e13$，$\sqrt{1e13} \approx 3e6$ 所以直接枚举根号以内的素因子即可

复杂度 $O(\sqrt{n})$

$code:$

void solve() {
    i64 x;
    std::cin >> x;
    
    int ans = 0;
    for(int i = 2; i <= x / i; i ++ ) {
        if(x % i == 0) {
            while(x % i == 0) {
                x /= i;
            }
            ans ++;
        }
    }
    
    ans += x > 1;
    std::cout << ans << '\n';
}

C.小红的字符串中值

首先观察到，中值左右俩边的字符数量一定相等，然后我们只需要枚举$S$中每一个等于询问字符的位置，然后计算左右两边能取到多少即可

void solve() {
    int n;
    char o;
    std::cin >> n >> o;
    
    std::string s;
    std::cin >> s;
    
    i64 ans = 0;
    for(int i = 0; i < n; i ++ ) {
        if(s[i] == o) {
            i64 l = i, r = n - i - 1;
            ans += std::min(l, r) + 1;
        }
    }
    std::cout << ans << '\n';
}

D.小红数组操作

模拟链表即可，每个数维护一个节点，记录左右相连的值，模拟操作

void solve() {
    int q;
    std::cin >> q;
    std::map<int, int> l, r;
    r[0] = -1;
    int siz = 0;
    while(q -- ) {
        int op, x, y;
        std::cin >> op;
        if(op == 1) {
            std::cin >> x >> y;
            r[x] = r[y];
            l[x] = y;
            l[r[y]] = x;
            r[y] = x;
            siz ++;
        } else {
            std::cin >> x;
            r[l[x]] = r[x];
            l[r[x]] = l[x];
            siz --;
        }
    }
    
    std::cout << siz << '\n';
    int now = r[0];
    while(now != -1) {
        std::cout << now << ' ';
        now = r[now];
    }
}

E.小红数组操作

因为数据范围比较小，我们能想到 $dp$，我们定义 $dp_i$ 表示的是所有元素和为 $i$ 时选择的元素数量最小为多少，对于每个数字有选和不选俩种情况，记录选择上一位选完的状态为 $dp$ ，当前位的状态为 $_dp$ ，当前状态能由上一位推出，并且没有影响，我们枚举上一位有的情况，然后对于 $a_i$ 选和不选俩种情况更新 $_dp$，实际上就是滚动数组，也可以记录位置，用二维 $dp$ ，同理 $$ 选：_dp[i - a[pos]] = std::min(_dp[i - a[pos]], dp[i] + 1) \newline 不选：_dp[i + a[pos]] = std::min(_dp[i + a[pos]], dp[i]); \newline 注意：这里如果 _dp 中没有这个元素就直接更新 $$ $code:$

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }
    
    std::map<int, int> dp;
    dp[0] = 0;
    for(int i = 0; i < n; i ++ ) {
        std::map<int, int> _dp;
        for(auto [v, y] : dp) {
            if(!_dp.count(v - a[i])) {
                _dp[v - a[i]] = y + 1;
            } else {
                _dp[v - a[i]] = std::min(_dp[v - a[i]], y + 1);
            }
            if(!_dp.count(v + a[i])) {
                _dp[v + a[i]] = y;
            } else {
                _dp[v + a[i]] = std::min(_dp[v + a[i]], y);
            }
        }
        dp = _dp;
    }
    std::cout << (dp.count(0) ? dp[0] : -1) << '\n';
}

F.小红的连续段

$code:$

void solve() {
    int x, y;
    std::cin >> x >> y;
    
    static constexpr int P = 1e9 + 7;
    std::vector<i64> fac(1001), invfac(1001), inv(1001);
    fac[0] = invfac[0] = fac[1] = invfac[1] = inv[1] = 1;
    for(int i = 2; i <= 1000; i ++ ) {
        inv[i] = (P - P / i * inv[P % i] % P) % P;
        fac[i] = fac[i - 1] * i % P;
        invfac[i] = invfac[i - 1] * inv[i] % P;
    }
    
    auto C = [&](i64 n, i64 m) -> i64 {
        if(m > n) return 0;
        return fac[n] * invfac[n - m] % P * invfac[m] % P;
    };
    
    std::vector<i64> ans(x + y + 1);
    for(int i = 1; i <= x - 1; i ++ ) {
        ans[2 * i + 1] = (ans[2 * i + 1] + C(x - 1, i) * C(y - 1, i - 1) % P) % P;
    }
    for(int i = 0; i <= x - 1; i ++ ) {
        ans[2 * i + 2] = (ans[2 * i + 2] + C(x - 1, i) * C(y - 1, i) % P) % P;
    }
    
    for(int i = 1; i <= y - 1; i ++ ) {
        ans[2 * i + 1] = (ans[2 * i + 1] + C(y - 1, i) * C(x - 1, i - 1) % P) % P;
    }
    for(int i = 0; i <= x - 1; i ++ ) {
        ans[2 * i + 2] = (ans[2 * i + 2] + C(y - 1, i) * C(x - 1, i) % P) % P;
    }
    
    for(int i = 1; i <= x + y; i ++ ) {
        std::cout << ans[i] << '\n';
    }
}