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