牛客周赛 Round 134 题解

A

模拟即可

void solve() {
    int x;
    std::cin >> x;
    std::cout << (x < 1600 ? "Rated" : "Unrated") << "\n";
    return ;
}

C

题目条件等价于 个铜牌可以换一个金牌， 可以先把所有银牌换成铜牌方便计算
注意 的时候，最后一次兑换会缺少一块铜牌

void solve() {
    i64 a, b, c, x, y;
    std::cin >> a >> b >> c >> x >> y;
    c += b * x;
    a += c / (x * y - 1);
    c %= (x * y - 1);
    if (!c) {
        a--;
    }
    std::cout << a << "\n";
    return ;
}

C

不难发现，对于后 位，能构造的不同元素上限为
我们考虑从后往前dp
对于第 i 位，我们肯定希望填入和 中不同的元素
所以转移方程为
注意数字从0开始

 
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    std::vector<int> dp(n + 1);
    dp[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        dp[i] = std::min(dp[i + 1] + 1, a[i] + 1);
    }
    std::cout << dp[1] << "\n";
    return ;
}

D

对于从 1 到 n 的每一个 l，对应的 r 是单调不减的，因为删去 不会让后面元素的候选值域变小
而对于一个极长的合法区间，其所有子区间一定是合法的
考虑使用双指针找出全部合法区间，过程中统计以 l 为左端点的区间数计入答案
对于检验区间合法性有多种做法，这里选用了 st 表

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    SphereTable st(n);
    for (int i = 1; i <= n; i++) {
        st.a[i] = st.b[i] = a[i];
    }
    st.init();
    i64 ans = 0;
    for (int l = 1, r = 1; l <= n; l++) {
        while(r <= n && st.query_max(l, r) - st.query_min(l, r) <= 1) {
            r++;
        }
        ans += r - l;
    }
    std::cout << ans << "\n";
    return ;
}

E

手玩一下， 一共只有这些变化情况
0 0 0 -> 0 0 0
0 0 1 -> 0 1 1
0 1 0 -> 1 1 0
1 0 0 -> 1 0 1
1 1 0 -> 0 1 1
1 0 1 -> 1 1 0
0 1 1 -> 1 0 1
1 1 1 -> 0 0 0
发现只要一个长度为3的区间内有一个及以上的1，就能让这个区间有两个1，且能够决定1的位置
所以答案为
注意特判全0的情况

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    int cnt = 0;
    for (auto c : s) {
        cnt += c == '1';
    }
    if (!cnt) {
        std::cout << 0 << "\n";
        return ;
    }
    std::cout << std::max(cnt, n - 1) << "\n";
    return ;
}

F

套路的dp一下
下文的划分数指的是把前缀划分为若干回文串的方案数
考虑设计 表示前位的价值之和, 为前位的划分数
对于每一个, 我们枚举 , 得到所有可行划分点
对于每一个可行划分点 , 令 , 则 对 的贡献为前j - 1位的划分数
对划分数的贡献为
递推更新即可
对于判断是否为回文串，笔者采用的是正反哈希
funfact : 笔者拿两个不同模数的哈希写了半天才看出是哪里的问题

void solve() {
    int n;
    std::cin >> n;  
    std::string s;
    std::cin >> s; 
    std::string t = s;
    std::reverse(t.begin(), t.end());
    Hasher hx1(s), hx2(t);

    auto same = [&] (int l, int r) -> bool {
        return hx1.query(l, r) == hx2.query(n - r + 1, n - l + 1);
    };

    std::vector<mint> f(n + 1), g(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (same(j, i)) {
                mint len = i - j + 1;
                f[i] += f[j - 1];
                g[i] += g[j - 1] + f[j - 1] * len * len;
            }
        }
    }
    std::cout << g[n] << "\n";
    return ;
}

头文件

#include "bits/stdc++.h"

using i64 = long long;

template<typename T>
constexpr T inf = std::numeric_limits<T>::max() >> 1;

void solve() {
    
    return ;
}

int main() {
    std::cin.tie(nullptr) -> std::ios_base::sync_with_stdio(false);

    int t = 1;
    std::cin >> t;

    while (t-->0) {
        solve();
    }

    return 0;
}

字符串哈希

struct Hasher {
    static const int base = 1331;
    int mod;

    std::vector<int> h, p;

    static bool isPrime(int x) {
        if (x <= 1) return false;
        for (int i = 2; 1LL * i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }

    static int findPrime(int x) {
        while (!isPrime(x)) x++;
        return x;
    }

    Hasher(const std::string &str) {
        // std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
        // mod = findPrime(rng() % 900000000 + 100000000);
        mod = 1'000'000'009;

        std::string s = " " + str;  

        int n = str.size();
        h.resize(n + 1);
        p.resize(n + 1);

        p[0] = 1;

        for (int i = 1; i <= n; i++) {
            h[i] = (1LL * h[i - 1] * base + s[i]) % mod;
            p[i] = 1LL * p[i - 1] * base % mod;
        }
    }

    int query(int l, int r) const {
        return (h[r] - 1LL * h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    };
};

Modint

template<typename T>
constexpr T modpow(T a, i64 b) {
    T res {1};
    for (b; b; b >>= 1, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
};

template<i64 P> 
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}

    constexpr MInt(i64 x) : x {norm(x % getMod())} {}

    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }

    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }

    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }

    constexpr i64 val() const {
        return x;
    }

    constexpr MInt operator - () const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }

    constexpr MInt inv() const {
        return modpow(*this, getMod() - 2);
    }

    constexpr MInt & operator *= (MInt rhs) & {
        if (getMod() < (1ull << 31)) {
            x = x * rhs.x % int(getMod());
        } else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }

    constexpr MInt & operator += (MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }

    constexpr MInt & operator -= (MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }

    constexpr MInt & operator /= (MInt rhs) & {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator * (MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }

    friend constexpr MInt operator + (MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }

    friend constexpr MInt operator - (MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }

    friend constexpr MInt operator / (MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }

    friend constexpr std::istream & operator >> (std::istream & is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }

    friend constexpr std::ostream & operator << (std::ostream & os, const MInt &a) {
        return os << a.val();
    } 

    friend constexpr bool operator == (MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }

    friend constexpr bool operator != (MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MInt<0>::Mod = 998'244'353;

constexpr int P = 998'244'353;
using mint = MInt<P>;

ST表

template<typename T>
struct SphereTable {
    int n, m;
    std::vector<T> a, b;
    std::vector<std::vector<T>> max_val, min_val;

    SphereTable(int n) : n(n), a(n + 1), b(n + 1), m(std::__lg(n)) {
        max_val.resize(m + 1, std::vector<int>(n + 1));
        min_val.resize(m + 1, std::vector<int>(n + 1));
    }

    void init() {
        for (int i = 1; i <= n; i++) {
            max_val[0][i] = a[i];
            min_val[0][i] = b[i];
        }
        for (int i = 0, t = 1; i < m; i++, t <<= 1) {
            int ed = n - (t << 1) + 1;
            for (int j = 1; j <= ed; j++) {
                max_val[i + 1][j] = std::max(max_val[i][j], max_val[i][j + t]);
                min_val[i + 1][j] = std::min(min_val[i][j], min_val[i][j + t]);
            }
        }
    }

    T query_max(int l, int r) {
        if (l > r) {
            std::swap(l, r);
        }
        int m = std::__lg(r - l + 1);
        return std::max(max_val[m][l], max_val[m][r - (1 << m) + 1]);
    }

    T query_min(int l, int r) {
        if (l > r) {
            std::swap(l, r);
        }
        int m = std::__lg(r - l + 1);
        return std::min(min_val[m][l], min_val[m][r - (1 << m) + 1]);
    }
};