KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)题解 ABCDE

A - 22222

题意：保留2

思路：模拟

// Code Start Here	
	string s;
	cin >>s;
	for(auto i : s){
		if(i == '2')cout << i;
	}
	cout << endl;
	return 0;

B - cat

题意：根据长度排序

思路：模拟

// Code Start Here	
	int n;
	cin >> n;
	vector<string> s(n);
	for(int i = 0;i<n;i++)cin >> s[i];
	sort(all(s),[&](string a,string b){return sz(a) < sz(b);});
	for(auto i :s)cout << i;

C - Debug

题意：不把最右边的WA变成AC，同时处理新的WA

思路：模拟

	string tar;
	cin >> tar;
	tar = " " + tar;
	for(int i = tar.size();i>=2;i--){
		if(tar[i] == 'A' && tar[i-1] == 'W'){
			tar[i] = 'C';
			tar[i-1] = 'A';
		}
	}
	for(int i = 1;i<=tar.size();i++){
		cout << tar[i];
	}

D - Colorful Bracket Sequence

题意：

给你一个由六种字符组成的字符串 SS ：(, ), [, ], <, >.

如果字符串 T 满足以下条件，则称为彩色括号序列：

可以通过重复以下操作任意次数(可能为零)将 T 变成空字符串：

如果 T 中存在()、[] 或 <> 中的连续子串，则选择一个这样的子串并删除它。
如果删除的子字符串位于 T 的开头或结尾，剩余部分将成为新的 T 。
否则，将删除子串之前的部分和删除子串之后的部分连接起来，成为新的 T 。

判断 S 是否为彩色括号序列。

思路：根据题目所给题意，不断消去一个成对的括号，边入边出，明显是个栈

// Code Start Here	
	string S;
	cin >> S;
	
	stack<char> st;
	for (char c : S) {
		if (c == '(' || c == '[' || c == '<') {
			st.push(c);
		} else {
			if (st.empty()){
				cout << "No";
				return 0;
			}
			char top = st.top();
			st.pop();
			if ((c == ')' && top != '(') ||
				(c == ']' && top != '[') ||
				(c == '>' && top != '<')) {
				cout << "No";
				return 0;
			}
		}
	}
	cout << (st.empty() ? "Yes" : "No");
	return 0;

E - Palindromic Shortest Path

题意：我们有一个有向图，图中有 N个顶点，图的边由一个 N×N的字符矩阵给出。矩阵中的字符代表从一个顶点到另一个顶点的有向边，字符是一个小写字母或 -（代表没有边）。我们的任务是，对于每一对顶点 i,j，找出从顶点 i 到顶点 j 的最短回文路径的长度，如果没有这样的路径，则返回 −1。

思路：回忆一下回文串的性质

根据题目定义，空字符串是回文路径，因此任何一个顶点到自身的路径（即 i→i/）默认是回文，长度为 0

对于每一条直接的边 i→j，如果该边存在，标签本身就是一个回文路径，长度为 1。

此外需要逐步扩展回文路径的长度，可以联想到bfs或者dijk

我们维护一个距离矩阵 dist[i][j]，表示从顶点 i到顶点 j 的最短回文路径的长度。初始化时，所有 dist[i][i]=0，即每个顶点到自身的路径为空字符串（回文路径，长度为 0）。对于每条边 i→j，我们设置 dist[i][j] = 1，即单一的边本身就是一个回文路径。

从一个状态 (u,v)（即从顶点 u 到顶点 v 的回文路径）出发，尝试通过在左端加一个边（x→u）和在右端加一个边（v→y），且这两条边的标签相同来扩展回文路径。最后，对于每一对顶点 i,j，如果 dist[i][j] 是未更新的（仍然为 INF），说明没有回文路径，输出 -1；否则输出最短回文路径的长度。

// Code Start Here	
	int n;
	cin >> n;
	vector<string> g(n);
	for (int i = 0; i < n; i++) {
		cin >> g[i];
	}
	vector<vector<pair<int, char>>> out(n), in(n);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			char c = g[i][j];
			if(c == '-')continue;
			else{
				out[i].pb({j, c});
				in[j].pb({i, c});
			}
		}
	}
	vector<vector<int>> dis(n, vector<int>(n, INF));
	auto dijk = [&](auto dijk)->void{
		queue<pair<int, int>> q;
		for (int i = 0; i < n; i++){
			if(dis[i][i] > 0){
				dis[i][i] = 0;
				q.push({i, i});
			}
		}
		for (int i = 0; i < n; i++){
			for(auto p : out[i]){
				int j = p.first;
				if(dis[i][j] > 1){
					dis[i][j] = 1;
					q.push({i, j});
				}
			}
		}
		while(!q.empty()){
			auto [u, v] = q.front();
			q.pop();
			int d = dis[u][v];
			for(auto u_ : in[u]){
				int x = u_.first;
				char tar = u_.second;
				for(auto v_ : out[v]){
					int y = v_.first;
					char now = v_.second;
                    //至于这里为什么是 + 2，左右各往外扩展一个
					if(tar == now && d + 2 < dis[x][y]){
						dis[x][y] = d + 2;
						q.push({x, y});
					}
				}
			}
		}
	};
	dijk(dijk);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if(dis[i][j] == INF)cout << "-1 ";
			else cout << dis[i][j] <<" ";
		}
		cout << endl;
	}

N<100，时间复杂度 On^4