牛客周赛 Round 135 题解

A Add Three

模拟和直接计算均可。

模拟：

void solve() {
    int n;
    cin >> n;
    int p = 0;
    while (p + 3 <= n) p += 3;
    cout << p << endl;
}

直接计算：

void solve() {
    int n;
    cin >> n;
    cout << n / 3 * 3 << endl;
}

B Maximize The Count

a_i-a_j=p_i-p_j\Rightarrow a_i-p_i = a_j-p_j

记录一下每个数字值与下标之差，取最大即可。

void solve() {
    int n, mx = 0;
    cin >> n;
    unordered_map<int, int> c;
    for (int i = 1, x; i <= n; ++i) cin >> x, c[x - i]++;
    for (auto [u, v] : c) mx = max(mx, v);
    cout << mx << endl;
}

C Permutation Swapping

不难发现当 $n\geq 4$ 的时候可以选择任意 $k\neq i,k\neq i+1$ ，进行 $(i\ k)(i+1\ k)(i\ k) = (i\ i+1)$ 的置换，因此必然有解。

剩下的情况特判一下相等即可， $n=3$ 的时候还需要特判一下是否是逆序。

void solve() {
    int n;
    cin >> n;
    bool f = 1, nf = 1;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (x != i) f = 0;
        if (x != n - i + 1) nf = 0;
    }
    if (f || n >= 4 || n == 3 && nf)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

D Two Options

由于两个操作对于总值的影响分别为 $+1$ 和 $+0$ ，因此最终的和必然大于等于初始的 $sum$ ，那么最优解显然是取最终值为 $p = \lceil\frac{sum}{n}\rceil$ ，又因为必然大于等于，所以减少的次数一定小于增加的次数，于是我们可以把所有减少的次数都与增加的次数绑组，贪心修改即可。本题需要注意负数的上取整处理。

void solve() {
    int n;
    ll sum = 0;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i];
    ll p = sum > 0 ? (sum + n - 1) / n : sum / n, chg = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] < p) chg += p - a[i];
    }
    cout << chg << endl;
}

E Not Equal

我们需要求解序列 $a'$ ，使得对于所有 $1\leq i<n$ ，都有 $a'_i\neq a'_{i+1}$ ，修改的代价为：

如果 $a’_i>a_i$ ，由于每次加 $1$ 花费 $b_i$ ，总代价为 $(a'_i−a_i)\times b_i$ 。
如果 $a'_i<a_i$ ，由于每次减 $1$ 花费 $c_i$ ，总代价为 $(a_i−a’_i)\times c_i$ 。
如果 $a’_i=a_i$ ，代价为 $0$ 。

直观来看，修改某个数是为了让它避开与相邻元素的冲突。假设某位置的最优取值为 $a’_i$ ，如果它距离初始值 $a_i$ 非常远（例如 $∣a'_i−a_i∣\geq 3$ ），那么在离 $a_i$ 更近的方向上，比如正数区间 $max⁡(1,a_i−2)$ 到 $a_i+2$ 之间，必然存在某个值既不等于 $a’_{i−1}$ 也不等于 $a’_{i+1}$ ，因为这 $5$ 个数的候选区间里，左右相邻元素最多只会占据 $2$ 个名额，至少剩下 $3$ 个合法的候选值可选。

因此，将 $a’_i$ 调整到离 $a_i$ 更近的合法值，可以严格减小（或维持）修改该元素的代价，同时不破坏相邻不相同的约束。

根据以上结论，我们使用动态规划进行求解，用 $dp[i][j]$ 表示处理前 $i$ 个数，且第 $i$ 个数的最终值为 $v_i$ 中的第 $j$ 个候选值时，所需的最少总花费。有：

dp[i][j] = cost(i,v_i[j])+\min\{dp[i-1][k]\ |\ v_{i-1}[k]\neq v_i[j]\}

用滚动 $\text{dp}$ 实现。

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    array<ll, 5> v{}, dp{};
    int siz = 0;
    for (int i = 0; i < n; ++i) {
        array<ll, 5> nv{}, ndp{};
        int nsiz = 0;
        for (ll j = a[i] - 2; j <= a[i] + 2; ++j) {
            if (j >= 1) {
                nv[nsiz++] = j;
            }
        }

        for (int j = 0; j < nsiz; ++j) {
            ll V = nv[j], cost = 0;

            if (V > a[i])
                cost = (V - a[i]) * b[i];
            else if (V < a[i])
                cost = (a[i] - V) * c[i];

            if (i == 0) {
                ndp[j] = cost;
            } else {
                ll mn = INF;
                for (int k = 0; k < siz; k++) {
                    if (v[k] != V) {
                        mn = min(mn, dp[k]);
                    }
                }
                ndp[j] = mn + cost;
            }
        }

        for (int j = 0; j < nsiz; ++j) {
            v[j] = nv[j];
            dp[j] = ndp[j];
        }
        siz = nsiz;
    }

    ll ans = INF;
    for (int j = 0; j < siz; ++j)
        if (dp[j] < ans) ans = dp[j];
    cout << ans << endl;
}

F Alone

我们先考虑任意一个格子 $(i,j)$ ，如果它是孤立点，那么剩下的 $(n-1)\times(m-1)$ 的格子能够自由染色。这些格子组成了独立于第 $i$ 行和第 $j$ 列的一个大矩形。因此，有 $2^{(n-1)\times(m-1)}$ 种方法来填充这部分。

然后我们考虑预设点：

对于我们选定的 $(i, j)$ ：

如果某个预设点 $(x, y)$ 位于第 $i$ 行或第 $j$ 列，但不是 $(i, j)$ 本身，那么它与 $(i, j)$ 的孤立配置是矛盾的。这种情况下， $(i, j)$ 永远不可能成为孤立点，贡献为 $0$ 。
如果所有 $k$ 个预设点都不与 $(i, j)$ 的孤立配置矛盾，那么这些预设点就必须满足它们各自的条件。
- 每个位于 $(n-1)\times (m-1)$ 自由区域内的预设点，都必须是黑色。这个要求将该区域的自由度减半。
- 如果 $(i, j)$ 本身就是一个预设点，它的黑色要求与孤立配置一致，不产生矛盾。

设有 $xx$ 个不同行， $yy$ 个不同列有预设点。

对于每一个不是预设点的格子，一共有 $(n-xx)\times (m-yy)$ 个格子。对于其中任何一个格子 $(i, j)$ ，它的孤立配置与 $k$ 个预设点都不矛盾。这 $k$ 个点全部落在 $(n-1)\times (m-1)$ 的自由区域内。为了满足这 $k$ 个点的黑色要求，自由区域的填法从 $2^{(n-1)\times(m-1)}$ 种减少到了 $2^{(n-1)\times(m-1) - k}$ 种。

此部分贡献 $= (n-xx) \times (m-yy) \times 2^{(n-1)\times (m-1) - k}$ 。

对于每一个是预设点，且不冲突的格子，记一共有 $K$ 个这样的格子。它的孤立配置与其他的 $k-1$ 个预设点都不矛盾。这 $k-1$ 个点全部落在 $(n-1)\times (m-1)$ 的自由区域内。为了满足这 $k-1$ 个点的黑色要求，自由区域的填法从 $2^{(n-1)\times (m-1)}$ 种减少到了 $2^{(n-1)\times (m-1) - (k-1)}$ 种。

此部分贡献 $= K \times 2^{(n-1)\times (m-1) - k + 1} = K \times 2\times 2^{(n-1)\times (m-1) - k}$

总贡献即为： $((n-xx)\times(m-yy)+K \times 2)\times 2^{(n-1)\times (m-1) - k}$ 。

其中 $(n-1)\times(m-1)$ 可能达到 $10^{18}$ 量级，需要用费马小定理进行优化。

a^{p-1}\equiv 1\pmod p

所以

a^e=a^{k(p-1)+r}=(a^{p-1})^ka^r\equiv a^r\pmod p

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<PII> a(k);
    unordered_map<int, int> X, Y;
    for (int i = 0; i < k; ++i) cin >> a[i].fi >> a[i].se, X[a[i].fi]++, Y[a[i].se]++;
    int xx = X.size(), yy = Y.size();
    int K = 0;
    for (auto [x, y] : a)
        if (X[x] == 1 && Y[y] == 1) K++;
    ll mod = 998244352;
    cout << (Z(1) * (n - xx) * (m - yy) + Z(2) * K) * ksm(Z(2), ((n - 1) * (m - 1) % mod - k + mod) % mod) << 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 135