C. awoo's Favorite Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given two strings ss and tt, both of length nn. Each character in both string is 'a', 'b' or 'c'.
In one move, you can perform one of the following actions:
You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string ss to make it equal to string tt?
Input
The first line contains a single integer qq (1≤q≤1041≤q≤104) — the number of testcases.
The first line of each testcase contains a single integer nn (1≤n≤1051≤n≤105) — the length of strings ss and tt.
The second line contains string ss of length nn. Each character is 'a', 'b' or 'c'.
The third line contains string tt of length nn. Each character is 'a', 'b' or 'c'.
The sum of nn over all testcases doesn't exceed 105105.
Output
For each testcase, print "YES" if you can change string ss to make it equal to string tt by performing an arbitrary amount of moves (possibly, zero). Otherwise, print "NO".
Example
input
Copy
5 3 cab cab 1 a b 6 abbabc bbaacb 10 bcaabababc cbbababaac 2 ba ab
output
Copy
YES NO YES YES NO
=========================================================================
ab ->ba
bc->cb
第一个置换只能有两个作用,那就是aaaab把b放到前面,abbbb把a放在后面
第二个置换同理
很自然的贪心。我们从末尾往前扫描,如果相等那么继续,否则,如果b对a,往前找a, c对b,往前找b,找不到或者不是这种配对,那么就无解。做多了感觉瞬间来。
- # include
- # include
- # include
- # include
- # include
- # define mod 1000000007
-
- using namespace std;
- typedef long long int ll;
-
- int main()
- {
-
- int t;
- cin>>t;
-
- while(t--)
- {
- int n;
-
- cin>>n;
- string s,t;
-
- cin>>s>>t;
-
- int flag=0;
-
- for(int i=n-1;i>=0;i--)
- {
- if(s[i]==t[i])
- continue;
-
- if(s[i]=='b'&&t[i]=='a')
- {
-
- int j;
- for( j=i-1;j>=0;j--)
- {
- if(s[j]=='a'||s[j]=='b')
- {
- if(s[j]=='a')
- {
- swap(s[j],s[i]);
-
- break;
- }
- }
- else
- {
- flag=1;
-
- break;
-
- }
- }
-
- if(j==-1)
- flag=1;
-
-
- }
- else if(s[i]=='c'&&t[i]=='b')
- {
- int j;
- for( j=i-1;j>=0;j--)
- {
- if(s[j]=='c'||s[j]=='b')
- {
- if(s[j]=='b')
- {
- swap(s[j],s[i]);
-
- break;
- }
- }
- else
- {
- flag=1;
-
- break;
- }
- }
-
- if(j==-1)
- flag=1;
-
- }
- else
- {
- flag=1;
- break;
- }
- }
-
- if(flag)
- {
- cout<<"NO"<
-
- }
- else
- {
- cout<<"YES"<
- }
- }
-
-
- return 0;
- }
-
相关阅读:
Mac cocoapods 3分钟安装教程( 国内镜像源方法)
MySQL中如何计算时间相差的分钟数
Spring更简单的实现Bean对象的存取
5步带你玩转SpringBoot自定义自动配置那些知识点
CI/CD | 大型企业与开发团队如何进行持续集成与持续发布
第6章 威廉.詹姆斯——意识心理学
cv2.split函数与cv2.merge函数
Pwsh 配置 Oh My Posh
Django和jQuery,实现Ajax表格数据分页展示
java 大厂面试指南:性能优化 + 微服务 + 并发编程 + 开源框架 + 分布式
-
原文地址:https://blog.csdn.net/jisuanji2606414/article/details/126138522