当前位置: 首页 > article >正文

gesp(C++四级)(16)洛谷:B4069:[GESP202412 四级] 字符排序

gesp(C++四级)(16)洛谷:B4069:[GESP202412 四级] 字符排序

在这里插入图片描述

题目描述

小杨有 n n n 个仅包含小写字母的字符串 s 1 , s 2 , … , s n s_1,s_2,\ldots,s_n s1,s2,,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t t t。小杨希望最后构成的字符串 t t t 满足:

  • 假设 t i t_i ti 为字符串 t t t 的第 i i i 个字符,对于所有的 j < i j\lt i j<i 均有 t j ≤ t i t_j\le t_i tjti。两个字符的大小关系与其在字母表中的顺序一致,例如 e < g < p < s \texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s} e<g<p<s

小杨想知道是否存在满足条件的字符串排列顺序。

输入格式

第一行包含一个正整数 T T T,代表测试数据组数。

对于每组测试数据,第一行包含一个正整数 n n n,含义如题面所示。

之后 n n n 行,每行包含一个字符串 s i s_i si

输出格式

对于每组测试数据,如果存在满足条件的排列顺序,输出(一行一个) 1 \texttt{1} 1,否则输出(一行一个) 0 \texttt{0} 0

样例 #1

样例输入 #1

3
3
aa
ac
de
2
aac
bc
1
gesp

样例输出 #1

1
0
0

提示

样例解释

对于第一组测试数据,一种可行的排列顺序为 aa + ac + de \texttt{aa}+\texttt{ac}+\texttt{de} aa+ac+de,构成的字符串 t t t aaacde \texttt{aaacde} aaacde,满足条件。

对于全部数据,保证有 1 ≤ T , n ≤ 100 1\le T,n\le 100 1T,n100,每个字符串的长度不超过 10 10 10

AC代码(100分)

#include<bits/stdc++.h>
using namespace std;
/*思路: 
	1、满足题意的拼接字符串的可行思路为:
	   先将字符串数组按字典序升序排序,然后依次拼接 
	2、判断拼接后的字符串是否满足题意:
		将拼接后的字符串升序排序,看排序后的结果和原字符串是否相等  
*/
int t,n;
bool check(string s[]){
	//对字符串数组排序
	sort(s+1,s+n+1);
	//拼接字符串 
	string t="";
	for(int i=1;i<=n;i++){
		t+=s[i];
	} 
	//判断拼接后的字符串是符合要求
	string t2=t;//t2存原来的字符串 
	sort(t.begin(),t.end());
	if(t==t2) return true;//判断排序后的字符串和原来的字符串是否相等 
	else return false; 
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		string s[110]; 
		for(int i=1;i<=n;i++){
			cin>>s[i]; 
		}
		if(check(s)) cout<<1<<endl;
		else cout<<0<<endl;
	}
	return 0;
}

文末彩蛋:

点击王老师青少年编程主页有更多精彩内容


http://www.kler.cn/a/501381.html

相关文章:

  • 工业视觉2-相机选型
  • 二、BIO、NIO编程与直接内存、零拷贝
  • 一些计算机零碎知识随写(25年1月)-1
  • Wi-Fi Direct (P2P)原理及功能介绍
  • MySQL数据导出导入
  • spring cloud注册nacos并从nacos上拉取配置文件,spring cloud不会自动读取bootstrap.yml文件
  • Oracle 23ai新特性:表值构造函数
  • 《自动驾驶与机器人中的SLAM技术》ch7:基于 ESKF 的松耦合 LIO 系统
  • 全栈面试(一)Basic/微服务
  • 基于django车牌识别系统(源码+lw+部署文档+讲解),源码可白嫖!
  • C++实现设计模式---模板方法模式 (Template Method)
  • Git的master 分支和main分支的区别是什么?使用场景是什么?底层原理是什么?
  • nginx负载均衡-基于端口的负载均衡(一)
  • 提升 PHP 编码效率的 10 个实用函数
  • 基于改进粒子群优化的无人机最优能耗路径规划
  • 大数据环境搭建进度
  • C# 正则表达式完全指南
  • 2025年华数杯国际赛B题论文首发+代码开源 数据分享+代码运行教学
  • 无人机电池技术引领低空经济新篇章!
  • 【网络云SRE运维开发】2025第2周-每日【2025/01/12】小测-【第12章 rip路由协议】理论和实操考试题
  • 【黑灰产】假钱包推广套路
  • SpringBoot项目实战(41)--Beetl网页使用自定义函数获取新闻列表
  • Linux随记(十四)
  • R语言的正则表达式
  • ssh+frp+公网IP 实现远程访问家里的电脑
  • 力扣-数组-219 存在重复元素Ⅱ