[牛客周赛 Round 139]题目解析（部分）

前记

由于本蒟蒻比较菜，F题没有做出来，这里先不写，后续会追加F题题解，同时，本人语文不好，如果看不懂的地方请见谅，可以向我提问。

A.小红的red

1.思路

作为这场比赛的签到题，不难发现，只需要判断每一个字符是否为r、e、d中的任意一个即可，如果是，则输出Yes，否则输出No。

2.AC Code

#include<bits/stdc++.h>
using namespace std;
signed main(){
    string s;
    cin >> s;
    for(auto x : s){
        if(x != 'r' && x != 'e' && x != 'd'){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

B.小红的矩阵构造

1.思路

这题是个结论题，我们先来分析一下。先考虑特殊情况，如果 $n = 1$ 且 $m = 1$ ，无法产生不同，直接输出 $-1$ 。

一般情况下，对于矩阵的一个位置，它至少能产生一个上下方向的不同和一个左右方向的不同，也就是在矩阵的四个顶点位置可以产生最小的不同个数。

但是题目要求只能产生一个不同，所以我们要考虑去掉一个上下方向的不同或一个左右方向的不同，既 $n = 1$ 或 $m = 1$ ，构造方法也十分简单，一个1后面跟上若干个0，否则就是-1。

2.AC Code

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int n,m;
    cin >> n >> m;
    if((n > 1 && m > 1) || (n == 1 && m == 1)) cout << -1;
    else if(n == 1){
        cout << 1;
        while(--m) cout << 0;
    }
    else if(m == 1){
        cout << 1;
        while(--n) cout << endl << 0;
    }
}

C.小红的数据结构

1.思路

这题思维难度不高，就是一道裸暴力，直接模拟栈和队列的输出列表进行比较即可。

2.AC Code

#include<bits/stdc++.h>
using namespace std;
int a[200005];
stack<int> stk;
queue<int> p;
signed main(){
    int n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++) cin >> a[i];
    bool fstk = 1,fq = 1;
    int pos = 1;
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x;
            cin >> x;
            stk.push(x);
            p.push(x);
        }
        else{
            if(stk.top() != a[pos]){
                fstk = 0;
            }
            if(p.front() != a[pos]){
                fq = 0;
            }
            stk.pop();
            p.pop();
            pos++;
        }
    }
    if(fstk && fq) cout << "both";
    else if(!fstk && !fq) cout << -1;
    else if(fstk) cout << "stack";
    else cout << "queue";
}

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

1.思路

这题可以抽象成一个图论题，就是问你有多少个连通块，如果有k个连通块，那么答案就是 $26^k$ 。

这个不难推吧，因为一个连通块中的所有位置可以取的字符都是一样的（一个位置也是连通块），对于一个连通块，所以考虑对于每个条件建双向边，遍历图即可。

2.AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v[200005];
const int mod = 998244353;
bool f[200005];
void dfs(int x){
    f[x] = true;
    for(auto k : v[x]){
        if(f[k]) continue;
        dfs(k);
    }
}
signed main(){
    int n,m;
    cin >> n >> m;
    int ans = 1;
    for(int i = 1;i <= m;i++){
        int x,y;
        cin >> x >> y;
        if(x == y) continue;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1;i <= n;i++){
        if(f[i]) continue;
        dfs(i);
        ans = ans * 26;
        ans %= mod;
    }
    cout << ans;
}

E.小红的部分相同字符串

1.思路

这题求的是对于一棵树，取若干个点删去，使得最后没有两个节点有一条直接的边相连。

乍一看，这不就是没有上司的舞会吗？甚至是弱化版（快去双倍经验吧）

设 $f_{i,1/0}$ 表示删/不删这个节点。如果删去这个节点，则这个节点的所有子节点可以选择删/不删；但是如果不删这个节点，那么所有子节点都必须会被删去，否则就会产生一条直接连接两个节点的边。林一个结点的儿子的为 $a_{1…m}$ 状态转移式如下：

\begin{array} \\ f_{i,0}=\sum_{j=1}^mf_{a_j,1} \\ f_{i,1}=1+\sum_{j=1}^m\min(f_{a_j,0},f_{a_j,1}) \end{array}

2.AC Code

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100005];
int f[100005][2];
void dfs(int x,int fa){
    int ans = INT_MAX;
    f[x][1] = 1;
    for(auto k : v[x]){
        if(k == fa) continue;
        dfs(k,x);
        f[x][1] = f[x][1] + min(f[k][0],f[k][1]);
        f[x][0] = f[x][0] + f[k][1];
    }
}
void init(int n){
    for(int i = 1;i <= n;i++){
        f[i][0] = f[i][1] = 0;
        v[i].clear();
    }
}
signed main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        init(n);
        for(int i = 1;i < n;i++){
            int x,y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1,0);
        for(int i = 1;i <= n;i++) cout << min(f[i][1],f[i][0]) << " ";
        cout << endl;
    }
}