A

模拟即可

void solve() {
    std::string s;
    std::cin >> s;
    for (auto &c : s) {
        c = tolower(c);
    }
    std::cout << (s == "ovo" ? "YES" : "NO") << "\n";
    return ;
}

B

模拟即可
注意读入要读完, 不要读一半 $return$

void solve() {
    int n;
    std::cin >> n;
    std::deque<int> que;
    for (int i = 1; i <= n; i++) {
        que.emplace_back(i);
    }
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        if (que.front() == x) {
            que.pop_front();
        } else if (que.back() == x) {
            que.pop_back();
        } else {
            std::cout << "NO" << "\n";
            return ;
        }
    }
    std::cout << "YES" << "\n";
    return ;
}

C

如果当前数字能接在已有序列末尾, 那我们一定让它接上去, 这一定是最优的
维护一下当前接到第几个即可

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    int cur = 2;
    for (int i = 2; i <= n; i++) {
        if (a[i] % cur == 0) {
            cur++;
        }
    }
    std::cout << --cur << "\n";
    return ;
}

D

显然不合法的情况是, 糖果不能被平分, 或者某人的糖果数量和平均值的差超过1
又因为每个人只能传递一次糖果, 所以 $2\ 2\ 1\ 0\ 0$ 这样, 有两个糖果要经过 3 传到右边的情况, 也是不合法的
所以合法情况一定是 $+1\ ...\ -1\ ...\ +1...\ -1$ 这样的
断环, 记录当前是多的还是少的, 遍历同时判断即可

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    i64 sum = std::accumulate(a.begin() + 1, a.end(), 0ll);
    if (sum % n) {
        std::cout << "NO" << '\n';
        return ;
    }
    i64 ave = sum / n;
    for (int i = 1; i <= n; i++) {
        if (std::abs(a[i] - ave) > 1) {
            std::cout << "NO" << "\n";
            return ;
        }
    }
    for (int i = 1; i <= n; i++) {
        a.emplace_back(a[i]);
    }
    int pos = 1;
    while (pos <= n && a[pos] != ave + 1) {
        pos++;
    }
    if (pos == n + 1) {
        std::cout << "YES" << "\n";
        return ;
    }
    int cur = 1;
    for (int i = pos + 1; i <= pos + n; i++) {
        if (a[i] > ave) {
            if (cur) {
                std::cout << "NO" << "\n";
                return ;
            }
            cur ^= 1;
        } else if (a[i] < ave) {
            if (!cur) {
                std::cout << "NO" << "\n";
                return ;
            }
            cur ^= 1;
        }
    }
    std::cout << "YES" << "\n";
    return ;
}

E

注意到, 不能存在局部最大值, 也就是 $a[i]$ $>$ $a[i - 1]$ $and$ $a[i]$ $>$ $a[i + 1]$ 的情况
这样的话, 我们就可以按值从大往小删除元素
-~~太菜了不会证~~-

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
            std::cout << "No" << "\n";
            return ;
        }
    }
    std::cout << "Yes" << "\n";
    return ;
}

F

首先, 我们考虑判断在给定条件下是否存在解
因为题目要求最后的序列单调不降, 所以对于每个节点, 我们把他的儿子按照从小到大排序后遍历一定最优, 否则一定不合法
按照这样排列之后, 我们模拟一次操作, 判断是否存在有解
然后我们考虑计算答案
不难发现, 这个合法的 $b$ 序列是唯一的, 因此我们只能改变相同元素的排列顺序
对于一个节点, 他的贡献为儿子中每种元素的个数的全排列除以他儿子的个数的全排列

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<std::vector<int>> edge(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        edge[u].emplace_back(v);
        edge[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) {
        std::sort(edge[i].begin(), edge[i].end(), [&] (auto &x, auto &y) {
            return a[x] < a[y];
        });
    }
    std::vector<int> tmp, f(n + 1);
    tmp.reserve(n);
    auto dfs = [&] (auto &&self, int p, int fa) -> void {
        tmp.emplace_back(a[p]);
        f[p] = fa;
        for (auto c : edge[p]) {
            if (c != fa) {
                self(self, c, p);
            }
        }
    };
 
    dfs(dfs, 1, 0);
     
    for (int i = 1; i < n; i++) {
        if (tmp[i] < tmp[i - 1]) {
            std::cout << 0 << "\n";
            return ;
        }
    }
    Z ans = 1;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        std::map<int, int> mp;
        for (auto c : edge[i]) {
            if (c != f[i]) {
                mp[a[c]]++;
                cnt++;
            }
        }
        for (auto [u, v] : mp) {
            ans *= comb.fac(v);
        }
        ans /= comb.fac(cnt);
    }
    std::cout << ans << "\n";
    return ;
}

缺省源, modint和comb

#include "bits/stdc++.h"

using u32 = unsigned int;
using u64 = unsigned long long;

using i64 = long long;
using i128 = __int128_t;

namespace ranges = std::ranges;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 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<>
int MInt<0>::Mod = 1;
 
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
 
constexpr int P = 998244353;
using Z = MInt<P>;

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        m = std::min(m, Z::getMod() - 1);
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }

    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }

    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

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

牛客周赛 Round 142 题解

A

B

C

D

E

F

缺省源, modint和comb