$A$ . 小红的 $red$

直接枚举就好

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;


void solve()
{
    std::string s; std::cin >> s;
    for (char c : s)
    {
        if (c != 'r' && c != 'e' && c != 'd')
        {
            std::cout << "No" << endl;
            return;
        }
    }
    std::cout << "Yes" << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int _t = 1;
    // std::cin >> _t;
    while (_t--) solve();

    return 0;
}

$B$ .小红的矩阵构造

构造

我们就让前2个不同就好了，可以发现只有1行或者1列的情况可以，其他就不行了，也要注意 $n == 1$ $and$ $m == 1$ 的情况，特判一下就好了

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;


void solve()
{
    int n = 0, m = 0; std::cin >> n >> m;
    if ((n != 1 && m != 1) || (n * m == 1))
    {
        std::cout << -1 << endl; return;
    }
    if (n == 1)
    {
        std::cout << "10";
        for (int i = 1; i <= m - 2; i++) std::cout << "0";
    }
    else
    {
        std::cout << "1" << endl;
        std::cout << "0" << endl;
        for (int i = 1; i <= n - 2; i++) std::cout << "0" << endl;
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int _t = 1;
    // std::cin >> _t;
    while (_t--) solve();

    return 0;
}

$C$ .小红的数据结构

模拟

直接分别用一个 $stack$ 和一个 $queue$ 去模拟整个过程，并记录弹出的数，一共就这四种情况

都能和 $a$ 数组匹配上就是 $both$
都匹配不上就是 $-1$
$stack$ 能匹配上就是 $stack$
$queue$ 能匹配上就是 $queue$

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;


void solve()
{
    int n = 0, q = 0; std::cin >> n >> q;
    std::stack<int> stk;
    std::queue<int> que;
    std::vector<int> a(n, 0), stk_vec, que_vec;
    for (int i = 0; i < n; i++) std::cin >> a[i];
    for (int i = 1; i <= q; i++)
    {
        int op; std::cin >> op;
        if (op == 1)
        {
            int v; std::cin >> v;
            stk.push(v); que.push(v);
        }
        else
        {
            int top_stk = stk.top();
            int que_stk = que.front();
            stk.pop(); que.pop();
            stk_vec.push_back(top_stk);
            que_vec.push_back(que_stk);
        }
    }
    bool stk_ok = true, que_ok = true;
    for (int i = 0; i < n; i++) if (stk_vec[i] != a[i]) {stk_ok = false; break;}
    for (int i = 0; i < n; i++) if (que_vec[i] != a[i]) {que_ok = false; break;}
    if (stk_ok == false && que_ok == false) {std::cout << -1 << endl; return;}
    if (stk_ok == true && que_ok == true) {std::cout << "both" << endl; return;}
    if (stk_ok == true) {std::cout << "stack" << endl; return;}
    if (que_ok == true) {std::cout << "queue" << endl; return;}
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _t = 1;
    // std::cin >> _t;
    while (_t--) solve();
    return 0;
}

$D.$ 小红的部分字符串

并查集 快速幂

限制条件中相同的字符可以看作一个连通块，这部分可以通过并查集实现
接下来就是组合数学中的染色问题，每个连通块都有 $26$ 种选择

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

int qpower(int y, int x)
{
    int r = 1;
    while(x)
    {
        if (x & 1) r = r * y % mod;
        y = y * y % mod;
        x >>= 1;
    }
    return r;
}

int faz[200010];

int find(int x)
{
    if (faz[x] == x) return x;
    return faz[x] = find(faz[x]);
}

void Merge(int x, int y)
{
    int prex = find(x), prey = find(y);
    faz[prey] = prex;
}

void solve()
{
    int n = 0, k = 0;
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) faz[i] = i;
    for (int i = 1; i <= k; i++)
    {
        int su, sv; std::cin >> su >> sv;
        Merge(su, sv);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (faz[i] == i) cnt++;
    }
    std::cout << qpower(26, cnt) % mod;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int _t = 1;
    // std::cin >> _t;
    while (_t--) solve();

    return 0;
}

$E$ . 小红的树权值

树的最小点覆盖 树形 $dp$

剩余的所有联通块大小都为 $1$ $\rightarrow$ 删完以后，图里不能再有任何边。因为只要还有一条边连着两个点，那这两个点就在同一个连通块里，这个连通块大小至少是 $2$ ，不符合要求。

所以“所有连通块大小都为 $1$ 等价于：

剩下的每个点都是孤立点
任意两个剩余点之间都没有边

这个本质上就是 树上的最小点覆盖：选最少的点，使得每条边都被覆盖

那么就变成了一个树形 $dp$ 的板子题

$dp[u][0]$ ：在 $u$ 的子树中，保留 $u$ 时，使这棵子树满足要求的最小删除数
$dp[u][1]$ ：在 $u$ 的子树中，删除 $u$ 时，使这棵子树满足要求的最小删除数

最后： $ans[u] = \min(dp[u][0], dp[u][1])$ 就是 $u$ 这棵子树的权值。

设 $u$ 的儿子是 $v$ 。

如果 $u$ 保留：`dp[u][0]`

因为 $u$ 没删，那么边 $u-v$ 不能留下。

所以对于每个儿子 $v$ ，必须删掉 $v$ 。

因此： $dp[u][0] = \sum dp[v][1]$

如果 $u$ 删除：`dp[u][1]`

那边 $(u-v)$ 自然消失了。

这时候每个儿子 $v$ 就自由了：

可以删
也可以不删

只要它自己的子树内部合法就行。

所以每个儿子取最优： $dp[u][1] = 1 + \sum \min(dp[v][0], dp[v][1])$

前面的 1 是因为删掉了 (u) 本人。

叶子节点会怎样？

如果 $u$ 是叶子：

保留它：不用删任何点， $dp[u][0]=0$
删除它：删 1 个点， $dp[u][1]=1$

所以： $ans[u] = \min(0,1)=0$

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

std::vector<int> g[100010];

void solve()
{
    int n = 0; std::cin >> n;
    for (int i = 1; i <= n; i++) g[i].clear();
    std::vector<std::array<int, 2>> dp(n + 1, {0, 0});
    for (int i = 1; i < n; i++)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // dp[u][0] 保留u
    // dp[u][1] 删掉u
    auto dfs = [&](auto&& dfs, int s, int fa) -> void
    {   
        dp[s][0] = 0;
        dp[s][1] = 1;
        for (int v : g[s])
        {
            if (v == fa) continue;
            dfs(dfs, v, s);
            dp[s][0] += dp[v][1];
            dp[s][1] += std::min(dp[v][0], dp[v][1]);
        }
    };
    dfs(dfs, 1, 0);
    for (int i = 1; i <= n; i++)
    {
        std::cout << std::min(dp[i][0], dp[i][1]) << endl;
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int _t = 1;
    std::cin >> _t;
    while (_t--) solve();

    return 0;
}

$F$ .小红的部分不同字符串

把位置看成点，把限制 s_i != s_{a_i} 看成一条边，那么题目就变成了：

用 26 种颜色给图染色
要求每条边两端颜色不同
求合法染色方案数

这张图的特殊之处在于：每个点恰好连向一个点 a_i，所以它是一个 函数图。
函数图的每个连通块一定是：

一个环 + 若干棵挂在环上的树

所以整题只需要拆成两部分考虑：

环外的树怎么贡献
环本身怎么贡献

环外的树很好算。

设某个点 u 不在环上，它只需要满足： $s_u != s_{a_u}$

如果 a_u 的颜色已经确定，那么 u 就有 25 种可选颜色。

所以：每个非环点都会给答案贡献一个 25

如果总共有 cnt 个非环点，那么它们总贡献就是: $25^{cnt}$

真正麻烦的是环。

设一个环长为 c，有 q 种颜色时，环的合法染色数是经典公式： $(q-1)^c + (-1)^c (q-1)$

这题里 q = 26，所以长度为 c 的环贡献为： $25^c + (-1)^c \cdot 25$

即：

c 为奇数：25^c - 25
c 为偶数：25^c + 25

所以整题答案就是：

先乘上所有非环点的贡献 25^{cnt}
再对每个环乘上对应的环染色贡献

也就是：

ans = 25^{cnt} \times \prod_{\text{每个环}} \left(25^{len} + (-1)^{len}\cdot 25\right)

剩下的问题只有一个：怎么找环？

做法是 拓扑剥叶子：

统计每个点的入度
把所有入度为 0 的点入队
不断删除这些点，并让它指向的点入度减一
新出现入度为 0 的点继续入队

这样做的原因是：

入度为 0 的点一定不在环上
不断剥掉这些点后，最后剩下的点一定都在环上

于是：

被剥掉的点 = 非环点
没被剥掉的点 = 所有环上的点

再顺着 a[i] 跑一圈，就能求出每个环的长度。

神奇的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int mod = 998244353;

int qpower(int y, int x)
{
    int r = 1;
    while(x)
    {
        if (x & 1) r = r * y % mod;
        y = y * y % mod;
        x >>= 1;
    }
    return r;
}

void solve()
{
    int n = 0; std::cin >> n;
    std::vector<int> a(n + 1, 0), in(n + 1, 0), del(n + 1, 0), vis(n + 1, 0);
    for (int i = 1; i <= n; i++) 
    {
        std::cin >> a[i];
        in[a[i]]++;
    }
    std::queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        // 入度为0, 说明在链首，这里可能不止有一个连通块
        if (in[i] == 0) q.push(i);
    }

    int cnt = 0; // 非环点个数

    while (!q.empty()) // 把链上的点摘干净
    {
        int u = q.front();
        q.pop();
        del[u] = 1;
        cnt++;
        int v = a[u];
        in[v]--;
        if (in[v] == 0) q.push(v);
    }
    
    int ans = qpower(25, cnt);

    // 开始处理环上的点
    for (int i = 1; i <= n; i++)
    {
        if (del[i] || vis[i]) continue;

        int len = 0;
        int u = i;
        while(!vis[u])
        {
            vis[u] = 1;
            len++;
            u = a[u];
        }

        int now = qpower(25, len);
        if (len & 1) now = (now - 25 + mod) % mod;
        else now = (now + 25) % mod;
        ans = ans * now % mod;
    }

    std::cout << ans % mod << endl;
    
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _t = 1;
    // std::cin >> _t;
    while (_t--) solve();
    return 0;
}

题解 | #牛客周赛Round139#

. 小红的

.小红的矩阵构造

.小红的数据结构

小红的部分字符串

. 小红的树权值

如果 保留：dp[u][0]

如果 删除：dp[u][1]

叶子节点会怎样？

.小红的部分不同字符串

$A$ . 小红的 $red$

$B$ .小红的矩阵构造

$C$ .小红的数据结构

$D.$ 小红的部分字符串

$E$ . 小红的树权值

如果 $u$ 保留：`dp[u][0]`

如果 $u$ 删除：`dp[u][1]`

$F$ .小红的部分不同字符串