Atcoder ABC 394

倒着处理

CPP

#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

经典栈处理括号匹配问题

CPP

#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

做法：

先把所有的 $(i,i)$ 放入队列
再把所有的 $s_{i,j} \neq$ -的 $(i,j)$ 放入队列
$bfs$ 的时候 $n^2$ 枚举 $i,j$ ，去尝试拓展即可。

CPP

#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--)

CPP

#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;
}

文章操作

相关推荐

评论

Atcoder ABC 394