牛客周赛 Round 134 题解

A Nowcoder Weekly Contest

直接判断一下即可。

void solve() {
    int x;
    cin >> x;
    cout << (x <= 1599 ? "Rated" : "Unrated") << endl;
}

B ICPC Medal

模拟，先处理铜 $\rightarrow$ 银，再处理银 $\rightarrow$ 金，直到铜的数量小于 $x$ 并且银的数量小于 $y$ 。

void solve() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    while (c >= x || b >= y) {
        int t = c / x;
        b += t;
        c = c % x;
        t = b / y;
        a += t;
        b = b % y;
        c += t;
    }
    cout << a << endl;
}

C Unique Number

由于前缀修改，必然有修改后前面的元素大于等于后面的元素，所以我们先把限制序列转换为单调不升的序列。然后从后往前进行判断，已经占用了 $cnt$ 个不同数字后，下一个 $d$ 必然需要大于 $cnt$ 才能有空余的数字进行放置。

void solve() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
        if (i > 0) {
            d[i] = min(d[i - 1], d[i]);
        }
    }

    int cnt = 0;
    for (int i = n - 2; i >= 0; --i)
        cnt = min(d[i], cnt + 1);

    cout << cnt + 1 << endl;
}

D Balanced Array

我们可以维护一个滑动窗口进行判断，滑动窗口内最多有 $2$ 个值，我们用两个双端队列去存储这两个值对应的下标，先把破坏单调性的值弹出，然后将 $a[r]$ 加入，检查窗口的差值是否 $>1$ ，动态维护一下即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    deque<int> q1, q2;
    ll ans = 0;
    int l = 0;
    for (int r = 0; r < n; ++r) {
        while (q1.size() && a[q1.back()] <= a[r])
            q1.pob();
        q1.pb(r);

        while (q2.size() && a[q2.back()] >= a[r])
            q2.pob();
        q2.pb(r);
        while (a[q1.front()] - a[q2.front()] > 1) {
            l++;
            if (q1.size() && q1.front() < l)
                q1.pof();
            if (q2.size() && q2.front() < l) {
                q2.pof();
            }
        }
        ans += (r - l + 1);
    }
    cout << ans << endl;
}

E Maximize The Sum

如果初始数组是全 $0$ ，无论怎么进行操作，数字都不会发生变化，所以结果还是 $0$ 。

当进行一次修改后，三个值的异或和会变为 $(x\oplus y)\oplus(y\oplus z)\oplus(z\oplus x)=0$ ，也就是说，修改后三个值必然不能同时等于 $1$ 。所以如果目标数组的所有数字全为 $1$ ，由于其中任何一个长度为 $3$ 的连续子串异或和都为 $1$ ，它绝对不可能由其他任何状态通过操作得到。

因此，除非初始数组本身就是全 $1$ ，否则我们无论如何都不可能得到全 $1$ 的数组，此时最大可能的 $1$ 的数量最多只能是 $n−1$ 。

当遇到某个长为 $3$ 的区间恰好只有一个 $1$ （例如 $100$ 、 $010$ 或 $001$ ）时，对该区间进行操作，它必然会变成含有两个 $1$ 的区间（例如 $100 \rightarrow 101，010 \rightarrow 110$ ）。这一步直接让整个数组的 $1$ 的数量增加了 $1$ 。
如果数组中尚有多个 $0$ 但没有恰好包含一个 $1$ 的区间时，操作那些含有两个 $1$ 的区间（如 $110 \rightarrow 011$ ），相当于让 $0$ 的位置在 $1$ 中移动。两个 $0$ 在游走过程中只要一靠近，必然能结合形成诸如 $010$ 这样的单 $1$ 区间。随后触发上一步规律，变成两个 $1$ 的区间。
不断重复这一过程，只要数组中还存在至少两个 $0$ ，它们就能移动、碰撞并消除一个 $0$ 。最终，整个数组必定能化简到只剩一个 $0$ ，即得到 $n−1$ 个 $1$ 。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    bool f1 = 1, f0 = 1;
    for (auto v : s) {
        if (v == '1')
            f0 = 0;
        if (v == '0')
            f1 = 0;
    }
    if (f0)
        cout << 0 << endl;
    else if (f1)
        cout << n << endl;
    else
        cout << n - 1 << endl;
}

F Palindromic Value

我们用两个 $dp$ 数组进行计算， $dp1$ 表示前缀 $s[1…i]$ 的所有合法回文分割方案总数， $dp1$ 表示前缀 $s[1…i]$ 的所有合法回文分割方案的价值总和。

我们依次计算从 $i=1$ 到 $n$ 的结果，在算到 $i$ 时，我们枚举最后一段回文串的起始位置前一个字符 $j∈[0,i−1]$ ：

如果子串 $s[j+1…i]$ 是一个回文串（可以通过中心扩展法预处理得到），那么：

这个回文子串可以追加在所有 $s[1…j]$ 的合法分割方案之后。因此前缀 $s[1…i]$ 的分割方案数要加上 $s[1…j]$ 的方案数： $dp1[i] = dp1[i] + dp1[j]$
对于 $s[1…j]$ 的每一种分割方案，追加这个长度为 $i−j$ 的回文子串后，每种方案的价值都会增加 $(i−j)^2$ 。由于共有 $dp1[j]$ 种方案，所以增加的总价值为 $dp1[j]\times (i−j)^2$ ；再加上这 $dp1[j]$ 种方案本身原来的价值总和 $dp2[j]$ ，就可以得到由 $j$ 转移过来的部分价值总和： $dp2[i] = dp2[i] + dp2[j]+dp1[j]\times (i-j)^2$

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

    vector<vector<bool>> flag(n + 1, vector<bool>(n + 1));
    for (int i = 0; i < n; ++i) {
        int l = i, r = i;
        while (l >= 0 && r < n && s[l] == s[r]) {
            flag[l + 1][r + 1] = 1;
            l--, r++;
        }
        l = i, r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r]) {
            flag[l + 1][r + 1] = 1;
            l--, r++;
        }
    }

    vector<Z> dp1(n + 1), dp2(n + 1);
    dp1[0] = 1, dp2[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (flag[j + 1][i]) {
                dp1[i] += dp1[j];
                dp2[i] += dp2[j] + dp1[j] * (i - j) * (i - j);
            }
        }
    }

    cout << dp2[n] << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

constexpr int MOD = 998244353;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * 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 istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(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 <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

题解 | 牛客周赛 Round 134