当前位置:网站首页>C. awoo‘s Favorite Problem--Educational Codeforces Round 130 (Rated for Div. 2)
C. awoo‘s Favorite Problem--Educational Codeforces Round 130 (Rated for Div. 2)
2022-08-03 21:03:00 【秦小咩】
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:
- choose an occurrence of "ab" in ss and replace it with "ba";
- choose an occurrence of "bc" in ss and replace it with "cb".
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 <iostream>
# include<algorithm>
# include<cstring>
# include<vector>
# include<queue>
# 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"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
return 0;
}
边栏推荐
猜你喜欢
面试官:为什么 0.1 + 0.2 == 0.300000004?
XSS漏洞复现
简单又有效的基本折线图制作方法
Power button - 203 - remove the list elements linked list
如何使用 Jmeter获取登录token并设置为全局变量?
用 setTimeout 来实现 setInterval
Markdown语法
Likou 707 - Design Linked List - Linked List
【kali-漏洞扫描】(2.1)Nessus解除IP限制、扫描快无结果、插件plugins被删除(中)
业界新标杆!阿里开源自研高并发编程核心笔记(2022 最新版)
随机推荐
基于DMS的数仓智能运维服务,知多少?
461. 汉明距离
【使用 Pytorch 实现入门级的人工神经网络】
ES6简介及let、var、const区别
Markdown语法
leetcode refers to Offer 58 - II. Left Rotate String
leetcode 16.01. Swap numbers (swap the values of 2 numbers without using temporary variables)
XSS线上靶场---Warmups
chartjs自定义柱状图插件
基于data.table的tidyverse?
CheckBox列表项选中动画js特效
Lecture topics and guest blockbuster, TDengine developers conference to promote data technology "broken"
华为设备配置VRRP与BFD联动实现快速切换
【kali-漏洞利用】(3.2)Metasploit基础(上):基础知识
XSS线上靶场---haozi
Orcad Capture Cadence 新建原理图多部分smybol和Homogeneous、Heterogeneous类型介绍教程
《QDebug 2022年7月》
《富爸爸,穷爸爸》思维导图和学习笔记
leetcode 1837. The sum of the digits in the K-base representation
华为设备配置VRRP负载分担