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

news/2025/2/23 21:35:08

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


http://www.niftyadmin.cn/n/5863787.html

相关文章

【论文带读(1)】《End-to-End Object Detection with Transformers》论文超详细带读 + 翻译

目录 前言 Abstract 一、Introduction 二、Related work&#xff08;相关工作&#xff09; 2.1 Set Prediction&#xff08;设置预测&#xff09; 2.2 Transformers and Parallel Decoding&#xff08;Transformer和并行解码&#xff09; 2.3 Object detection&#xf…

【NLP 31、预训练模型的发展过程】

人的行为&#xff0c;究竟是人所带来的思维方式不同还是与机器一样&#xff0c;刻在脑海里的公式呢&#xff1f; 只是因为不同的人公式不同&#xff0c;所以人的行为才不同&#xff0c;可这又真的是人引以为傲的意识吗&#xff1f; 人脑只是相当于一个大型、驳杂的处理器&#…

S8711A UXM5G 测试应用软件

苏/州/新/利/通 S8711A UXM 5G 测试应用软件 简述 Keysight S8711A UXM 5G 测试应用软件是一款交互式实时测试工具&#xff0c;适用于从早期原型测试一直到集成和验证的整个芯片和设备开发工作流程。 它提供了全套网络仿真、射频测试和功能测试工具&#xff0c;能够高度自…

docker独立部署milvus向量数据库

milvus镜像&#xff1a;国外封锁&#xff0c;国内源也不好用。基本上所有源都不能用 首先想到阿里云服务&#xff0c;但是阿里云国外服务器便宜的300~400呢。 基于成本考虑终于装上心心念念的milvus(*^▽^*) 安装 Milvus 安装 Milvus 独立版 wget https://raw.githubuserco…

MySQL的Union和OR查询

这里写目录标题 **1. 创建表和索引****2. 编写 UNION 查询****3. 使用 EXPLAIN 分析查询****4. 分析 EXPLAIN 结果****可能的结果分析**&#xff1a; **5. 验证索引合并****总结****1. UNION 操作的分析****为什么使用临时表&#xff1f;** 2. OR 条件的分析为什么使用索引合并…

javaEE-14.spring MVC练习

目录 1.加法计算器 需求分析: 前端页面代码: 后端代码实现功能: 调整前端页面代码: 进行测试: 2.用户登录 需求分析: 定义接口: 1.登录数据校验接口: 2.查询登录用户接口: 前端代码: 后端代码: 调整前端代码: 测试/查错因 后端: 前端: lombok工具 1.引入依赖…

【第四节】C++设计模式(创建型模式)-Builder(建造者)模式

目录 引言 一、Builder 模式概述 二、Builder 模式举例 三、Builder 模式的结构 四、Builder 模式的实现 五、Builder 模式的优缺点 六、总结 引言 Builder 模式是一种创建型设计模式&#xff0c;旨在将复杂对象的构建过程与其表示分离。通过一步步构建对象&#xff0c;…

解锁ApplicationContext vs BeanFactory: 谁更具选择性?

目录 一、聚焦源码回顾 &#xff08;一&#xff09;源码分析和理解 &#xff08;二&#xff09;简短的回顾对比建议 二、ApplicationContext vs BeanFactory特性对比 &#xff08;一&#xff09;主要特性总结 &#xff08;二&#xff09;直接建议 三、案例简单说明 &am…