AT_arc170_a [ARC170A] Yet Another AB Problem 题解
这道题做了我七天
(同时也是我第一到通过的 ARC 题)
太酷了
其实还是比较好理解的
原题题干
输出 \(-1\) 的情况:
- 在第一个更换的 \(B~A\) (即 \(S_i\) 位)之前有 \(A~B\) (即 \(S_j\) 位)的更换
- 在最后更换的 \(A~B\) (即 \(S_j\) 位)之后有 \(B~A\) (即 \(S_i\) 位)的更换
- 在 \(S_1\) 与 \(S_2\)不相等的情况下,无 \(S_i\) 或无 \(S_j\)
核心思路
if(s1[i]=='B'&&s2[i]=='A'){
suma++;//B~A的个数
}
if(s1[i]=='A'&&s2[i]=='B'){
if(suma==0){
ans++;//若A~B的个数已归零,则ans直接加(与之前的A~A换)
}
else{
suma--;//否则顺便换一个B~A
ans++;
}
}
未归零的 \(A~B\) 的个数则和后面的 \(B~B\) 换;
即 \(ans\) 加未归零的 \(A~B\) ( \(suma\) )的个数
cout<<ans+suma;
另一个问题是怎样找 \(S_i\) 及 \(S_j\) 的可操作区间
我的做法是
l=-1,r=-1; //方便检测是否有Si和Sj
for(int i=0;i<n;i++){
if(s2[i]=='A'){ \\找A~A或B~A
l=i;
break;
}
if(s1[i]=='A'&&s2[i]=='B'){ //即第一种情况在第一个更换的B~A(即Si位)之前有A~B(即Sj位)的更换
cout<<"-1";
return 0;
}
}
if(l==-1){ //第三种情况无Si
cout<<"-1";
return 0;
}
for(int i=n-1;i>l;i--){
if(s2[i]=='B'){ //找B~B或A~B
r=i;
break;
}
if(s1[i]=='B'&&s2[i]=='A'){ //即第二种情况在最后更换的A~B(即Sj位)之后有B~A(即Si位)的更换
cout<<"-1";
return 0;
}
}
if(r==-1){ //第三种情况无Sj
cout<<"-1";
return 0;
}
找出可以进行的“安全区间”进行操作
此为主代码(仅供参考)
#include<bits/stdc++.h> //万能头万岁。。。
#define seq(q,w,e) for(int q=w;q<=e;q++)
#define ll long long
using namespace std;
string s1,s2;
int n,ans,suma,l,r;
int main(){
scanf("%d",&n);
cin>>s1>>s2; //输入字符串
if(s1==s2){ //判断是否相等
cout<<"0";
return 0;
}
l=-1,r=-1;
for(int i=0;i<n;i++){
if(s2[i]=='A'){ \\找A~A或B~A
l=i;
break;
}
if(s1[i]=='A'&&s2[i]=='B'){ //即第一种情况在第一个更换的B~A(即Si位)之前有A~B(即Sj位)的更换
cout<<"-1";
return 0;
}
}
if(l==-1){
cout<<"-1"; //第三种情况无Si
return 0;
}
for(int i=n-1;i>l;i--){
if(s2[i]=='B'){ //找B~B或A~B
r=i;
break;
}
if(s1[i]=='B'&&s2[i]=='A'){ //即第二种情况在最后更换的A~B(即Sj位)之后有B~A(即Si位)的更换
cout<<"-1";
return 0;
}
}
if(r==-1){ //第三种情况无Sj
cout<<"-1";
return 0;
}
seq(i,l,r){ //循环找更换次数
if(s1[i]=='B'&&s2[i]=='A'){
suma++;
}
if(s1[i]=='A'&&s2[i]=='B'){
if(suma==0){
ans++;
}
else{
suma--;
ans++;
}
}
}
cout<<ans+suma; //若若B~A的个数已归零,则ans直接加剩余的A~B的个数(与之后的B~B换)
return 0;
}
本蒟蒻第一次发题解,不好之处见谅 (汗)