A 小苯的ovo3.0

知识点：字符串、大小写转换

把输入字符串统一转成小写后，判断是否等于 $\texttt{ovo}$ 即可。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    string s, tar = "ovo";
    cin >> s;
    auto tolow = [&](char c) -> char {
        if ('A' <= c && c <= 'Z') return c + 32;
        return c;
    };
    for (int i = 0; i < 3; ++i) {
        if (tolow(s[i]) != tar[i]) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

B 小苯的双端队列

知识点：双端队列、模拟

初始双端队列为 $1,2,\dots,n$。如果数组 $a$ 可以作为出队序列，那么每一步要取出的 $a_i$ 必须等于当前队首或队尾。

因此直接模拟：若 $a_i$ 等于队首则弹队首，等于队尾则弹队尾，否则无解。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;
    deque<int> b(n);
    iota(all(b), 1);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) {
        if (b.front() == a[i])
            b.pof();
        else if (b.back() == a[i])
            b.pob();
        else {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

C 小苯的整除序列

知识点：贪心、子序列

设当前已经选出了长度为 $ans$ 的合法子序列，那么下一个要选的数必须满足能被 $ans+1$ 整除。

从左到右扫描数组，遇到第一个满足 $a_i \bmod (ans+1)=0$ 的数就选它。这样做一定不劣，因为越早选中当前位置，留给后续选择的元素越多。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, ans = 0;
    cin >> n;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x % (ans + 1) == 0) ans++;
    }
    cout << ans << endl;
}

D 小苯的幼儿园

知识点：前缀和、环形差分、构造判定

设最终每个人都有 $k$ 颗糖，则必须满足 $\sum a_i$ 能被 $n$ 整除，且 $k=\frac{\sum a_i}{n}$。

记每个人相对目标值的差为 $a_i-k$，沿环做前缀和 $s$。一次给糖相当于让相邻位置之间产生 $0/1$ 的流量差，因此所有前缀和只允许落在两个相邻的值之间。

所以只需判断前缀和最大值与最小值之差是否不超过 $1$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, sum = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i];
    if (sum % n) {
        cout << "NO" << endl;
        return;
    }
    int k = sum / n, s = 0, mx = 0, mn = INF;
    for (auto v : a) s += v - k, mx = max(mx, s), mn = min(mn, s);
    cout << (mx - mn <= 1 ? "YES" : "NO") << endl;
}

E 小苯的区间操作

知识点：构造判定、局部极值

一次操作只能选择两端相等且中间不小于端点的区间整体减一，本质上可以削掉“谷底上的一层”。

如果存在严格峰值，即某个位置比左右相邻都大，那么它无法通过合法区间被单独削平，因此无解。边界同理，若 $a_1>a_2$ 或 $a_n>a_{n-1}$ 也无解。

反之，若不存在这样的峰值，序列可以按高度从低到高逐层消去，最终变成全 $0$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    if (n == 1) {
        cout << (a[0] == 0 ? "Yes" : "No") << endl;
        return;
    }
    bool f = (a[0] > a[1]) | (a[n - 1] > a[n - 2]);
    for (int i = 1; i < n - 1; ++i) f |= (a[i] > a[i - 1] && a[i] > a[i + 1]);
    cout << (f ? "No" : "Yes") << endl;
}

F 小苯的DFS

知识点：树形 DFS、区间排序、概率计数

对每棵子树，记录其中权值的最小值和最大值。若 DFS 序列要单调不降，则对于任意节点 $u$：

首先必须有子树内所有点权都不小于 $a_u$，否则访问完 $u$ 后进入子树时一定下降。

其次，$u$ 的若干子树之间必须能排成一个顺序，使得前一棵子树的最大值不超过后一棵子树的最小值。把每棵子树看成区间 $[mn,mx]$，按 $mn$ 排序后检查相邻区间是否满足 $mx_i\le mn_{i+1}$。

若可行，合法访问顺序只来自完全相同区间之间的任意排列。若当前节点有 $k$ 个子节点，其中相同区间分组大小为 $c_1,c_2,\dots$，则当前节点贡献概率为：

$$\frac{\prod c_i!}{k!}$$

所有节点贡献相乘即为答案。

时间复杂度 $\mathcal{O}(n\log n)$。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    Z ans = 1;
    auto dfs = [&](auto &&self, int u, int fa) -> PII {
        int mn = a[u], mx = a[u];
        vector<PII> child;

        for (auto v : g[u]) {
            if (v == fa) continue;
            auto [vmn, vmx] = self(self, v, u);

            if (ans == 0) return {0, 0};

            child.pb({vmn, vmx});
            cmin(mn, vmn);
            cmax(mx, vmx);
        }

        if (mn < a[u]) {
            ans = 0;
            return {0, 0};
        }

        if (child.size()) {
            sort(child);

            int k = child.size();

            for (int i = 0; i < k - 1; i++) {
                if (child[i].se > child[i + 1].fi) {
                    ans = 0;
                    return {0, 0};
                }
            }

            Z ways = 1;
            int cnt = 1;
            for (int i = 1; i < k; i++) {
                if (child[i] == child[i - 1]) {
                    cnt++;
                } else {
                    ways *= C.fac(cnt);
                    cnt = 1;
                }
            }

            ans *= ways * C.fac(cnt) / C.fac(k);
        }

        return {mn, mx};
    };
    dfs(dfs, 1, 0);
    cout << ans << endl;
}