比赛链接：https://ac.nowcoder.com/acm/contest/131539#question

A. 小红的red#

模拟即可

1
import sys
2
input = sys.stdin.readline
3
a = ['r','e','d']
4
s = input().strip()
5
for i in range(len(s)):
6
    if s[i] not in a:
7
        print("No")
8
        exit()
9
print("Yes")

B. 小红的矩阵构造#

只有n = 1或者 m = 1才可以，n = 1横着放，m = 1 竖着放

1
n, m = map(int,input().split())
2
if n == 1 and m >= 2:
3
    print("01",end='')
4
    for i in range(m - 2):
5
        print('1',end='')
6
elif n >= 2 and m == 1:
7
    print("0")
8
    print("1")
9
    for i in range(n - 2):
10
        print('1')
11
else:
12
    print(-1)

C. 小红的数据结构#

我们维护一个队列一个栈，如果中途不成立就记录，最后根据成立情况判断

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    int n, Q;cin >> n >> Q;
10
    vector<int> a(n + 1);
11
    for(int i = 1;i <= n; ++i) cin >> a[i];
12
    int cur = 1;
13
    queue<int> q;
14
    stack<int> st;
15
    bool okq = 1,okst = 1;
16
    while(Q--){
17
        int op;cin >> op;
18
        if(op == 1){
19
            int x;cin >> x;
20
            q.push(x);
21
            st.push(x);
22
        }
23
        else{
24
            int nq = q.front();q.pop();
25
            int nst = st.top();st.pop();
26
            if(nq != a[cur]) okq = 0;
27
            if(nst != a[cur]) okst = 0;
28
            cur++;
29
        }
30
    }
31
    if(okq && okst) cout << "both\n";
32
    else if(okq) cout << "queue\n";
33
    else if(okst) cout << "stack\n";
34
    else cout << "-1\n";
35
}
36
signed main(){
37
    std::ios_base::sync_with_stdio(false);
38
    std::cin.tie(nullptr);
39
    int t = 1;
40
    // cin>>t;
41
    while(t--){
42
        solve();
43
    }return 0;
44
}

D. 小红的部分相同字符串#

我们用并查集找出有几个依然还能改变的点，如果两个点相等就联通，我们用并查集刚好可以统计有几个连通块

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int INF = 0x3f3f3f3f3f3f3f3f;
5
const int mod = 998244353;
6
const int mx = 202020;
7
int fac[mx+1],invfac[mx+1];
8
int fa[mx+1];
9
int find(int x){
10
    if(fa[x] == x) return x;
11
    return fa[x] = find(fa[x]);
12
}
13
void merge(int x,int y){
14
    int fx = find(x),fy = find(y);
15
    if(fx != fy){
16
        fa[fx] = fy;
17
    }
18
}
19
int fastpow(int x,int p){
20
    int ans = 1;
21
    while(p){
22
        if(p & 1) ans = ans * x % mod;
23
        x = x * x % mod;
24
        p >>= 1;
25
    }
26
    return ans % mod;
27
}
28
int inv(int x){
29
    return fastpow(x,mod - 2);
30
}
31
int c(int a,int b){
32
    if (b < 0 || b > a) return 0;
33
    return fac[a] * invfac[b] % mod * invfac[a-b] % mod;
34
}
35
void init(){
36
    fac[0] = 1;
37
    for(int i = 1;i <= mx; i++) fac[i] = fac[i-1] * i % mod;
38
    invfac[mx] = fastpow(fac[mx], mod - 2);
39
    for (int i = mx - 1; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod;
40
    for(int i = 1;i < mx; i++) fa[i] = i;
41
}
42
void solve(){
43
    int n, k;cin >> n >> k;
44
    int cnt = 0;
45
    for(int i = 1;i <= k; ++i){
46
        int u, v; cin >> u >> v;
47
        merge(u,v);
48
    }
49
    for(int i = 1;i <= n; ++i){
50
        if(fa[i] == i) cnt++;
51
    }
52
    cout << fastpow(26,cnt) <<"\n";
53
}
54
signed main(){
55
    std::ios_base::sync_with_stdio(false);
56
    std::cin.tie(nullptr);
57
    init();
58
    int t = 1;
59
    // cin>>t;
60
    while(t--){
61
        solve();
62
    }return 0;
63
}

E. 小红的树权值#

详细见cf每日中没有上司的舞会

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7

8
void solve(){
9
    int n;
10
    cin >> n;
11
    vector<vector<int>> e(n + 1);
12
    for(int i = 1;i <= n - 1; ++i){
13
        int u, v;
14
        cin >> u >> v;
15
        e[u].push_back(v);
16
        e[v].push_back(u);
17
    }
18
    vector<int> w(n + 1);
19
    vector<bool> vis(n + 1);
20
    auto dfs = [&](auto dfs,int u,int fa)->void{
21
        if(e[u].size() == 1 && u != 1){
22
            w[fa] = 1;
23
            vis[fa] = 1;
24
            w[u] = 0;
25
            return;
26
        }
27
        for(auto i : e[u]){
28
            if(i == fa) continue;
29
            dfs(dfs, i, u);
30
        }
31
        w[fa] = w[u] + (!vis[u]);
32
    };
33
    dfs(dfs, 1 , 0);
34
    for(int i = 1;i <= n; ++i){
35
        cout << w[i] << ' ';
36
    }
37
    cout<<"\n";
38
}
39
signed main(){
40
    std::ios_base::sync_with_stdio(false);
41
    std::cin.tie(nullptr);
42
    int t = 1;
43
    cin>>t;
44
    while(t--){
45
        solve();
46
    }return 0;
47
}

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

基环树染色问题，对于不断不相等的点，我们最终可以连接成一个环，而且不可能只形成一条链，每个点一定会有一条边连接，我们用并查集维护这个环，环的染色公式是 $(q-1)^n + (-1)^n(q-1)$ ，然后再乘上剩余的点即可

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define ld long double
5
#define debug(x) cerr << #x << ": " << x << '\n';
6
const int INF = 0x3f3f3f3f3f3f3f3f;
7
const int mod = 998244353;
8
const int N = 2e5 + 10;
9
int fa[N];
10
int fastpow(int x,int p){
11
    int ans = 1;
12
    while(p){
13
        if(p & 1) ans = ans * x % mod;
14
        x = x * x % mod;
15
        p >>= 1;
16
    }
17
    return ans % mod;
18
}
19
int find(int x){
20
    if(fa[x] == x) return x;
21
    return fa[x] = find(fa[x]);
22
}
23
void merge(int x,int y){
24
    int fx = find(x),fy = find(y);
25
    if(fx != fy){
26
        fa[fx] = fy;
27
    }
28
}
29
void init(){
30
    for(int i = 1;i < N; i++) fa[i] = i;
31
}
32
void solve(){
33
    int n;
34
    cin >> n;
35
    vector<int> a(n + 1);
36
    int ans = 1, cnt = 0;
37
    for(int i = 1;i <= n; ++i){
38
        cin >> a[i];
39
        if(find(i) == find(a[i])){
40
            int l = 1;
41
            int cur = a[i];
42
            while(cur != i){
43
                cur = a[cur];
44
                l++;
45
                if(cur == i) break;
46
            }
47
            cnt += l;
48
            if(l & 1) ans = ans * (fastpow(25, l) - 25 + mod) % mod;
49
            else ans = ans * (fastpow(25, l) + 25) % mod;
50
        }
51
        else merge(i, a[i]);
52
    }
53
    ans = ans * fastpow(25, n - cnt) % mod;
54
    cout << ans << "\n";
55
}
56
signed main(){
57
    std::ios_base::sync_with_stdio(false);
58
    std::cin.tie(nullptr);
59
    init();
60
    int t = 1;
61
    // cin>>t;
62
    while(t--){
63
        solve();
64
    }return 0;
65
}