Atcoder ABC 394

· · 题解

C - Debug

倒着处理

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == 'A' && s[i - 1] == 'W'){
            s[i] = 'C'; 
            s[i - 1] = 'A';
        }
    }
    cout << s << endl;
    return 0;
}

D - Colorful Bracket Sequence

经典栈处理括号匹配问题

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
    cin >> s;
    stack<char>stk;
    map<char, char>mp;
    mp[')'] = '(';
    mp[']'] = '[';
    mp['>'] = '<';

    for(int i = 0; i < s.size(); i++){
        if(s[i] == '(' || s[i] == '[' || s[i] == '<')
            stk.push(s[i]);
        else{
            if(!stk.size() || stk.top() != mp[s[i]]){
                puts("No");
                return 0;
            }
            stk.pop();
        }
    }
    if(stk.empty())
        puts("Yes");
    else
        puts("No");
    return 0;
}

E - Palindromic Shortest Path

思路：考虑回文的本质，如果i->j的路径是回文串，那么就一定满足i->x->y->j，其中x->y的路径是回文串，i->x 和y->j是字母相同的边。我们肯定是先计算出x->y的路径，才能扩展出i->j的路径，本质上就是bfs的过程。

每次拓展会让回文串的长度+2

做法：

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
string s[N];
int dis[N][N];//dis[i][j] -> i到j的最短回文路径长度
int main(){
    memset(dis, -1, sizeof(dis));
    int n; 
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    queue<pair<int, int>> que;
    for(int i = 0; i < n; i++){ //自己到自己
        dis[i][i] = 0;
        que.push({i, i});
    }
    for(int i = 0; i < n; i++){ //任意2个点 
        for(int j = 0; j < n; j++){
            if(i == j)continue;
            if (s[i][j] != '-')
                dis[i][j] = 1, que.push({i, j});
        }
    }
    while (!que.empty()){
        auto cur = que.front();
        int x = cur.first, y = cur.second;
        que.pop();
        for (int i = 0; i < n; i++)//枚举(i,j) 表示从 i->x 和从y->j
            for (int j = 0; j < n; j++)
                if (s[i][x] != '-' && s[i][x] == s[y][j] && dis[i][j] == -1)
                    dis[i][j] = dis[x][y] + 2, que.push({i, j});
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cout << dis[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

F - Alkane

节点u为根的子树,有j个儿子节点. 整棵子树满足要求的话，这棵子树，至少也要5个节点。

记f[u][j]表示以u有j个儿子时，满足条件的子树的大小；

答案：若f[u][1]>=5,ans = max(f[u][1], f[u][4]), 否则 ans = f[u][4]

设v是u的某个子节点，u与v的连接贡献给u一个度，所以v的儿子只能是0个或者是3个。

综上：f[u][j] = max(f[u][j - 1] + max(f[v][0], f[v][3]))

这是一棵树，先计算子节点，再处理父节点，需要递归处理。

注意：计算时，这里j的顺序应该是for(int \ j = 4; j >= 1; j--)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, f[N][5], ans = -1;
vector<int> g[N];
void dfs(int u, int fa){
    f[u][0] = 1;
    for (auto v : g[u])if (v != fa){
        dfs(v, u);
        for(int j = 4; j >= 1; j--)// v分支只能选一次，所以逆序 
            f[u][j] = max(f[u][j], f[u][j - 1] + max(f[v][0], f[v][3]));
        //printf("u = %d v = %d:\n", u, v);
        //for(int j = 4; j >= 1; j--)
        //  printf("  j = %d : %d\n", j, f[u][j]); 
    }

    //更新u是根节点的答案
    if (f[u][1] >= 5) ans = max(ans, f[u][1]);
    ans = max(ans, f[u][4]);
}
int main(){
    cin >> n;
    for (int i = 1, x, y; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(f, -0x3f, sizeof f);
    dfs(1, 0);

    cout << ans << endl;
    return 0;
}