526互联

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

发布时间 2023-11-28 22:02:40作者: potential-star

看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了

题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？
实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。
只要还没过最后一个B，那么最后一个B之前的所有A就会被反转。真正无效的部分是开头就是B，以及末尾的A，所以我们只需要找到第一个A，最后一个B即可，这两之间的所有位置都会被颠倒

// Problem: B. AB Flipping
// Contest: Codeforces - CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1896/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];

void solve(){
	cin>>n;
	string s;
	cin>>s;
	int st=-1,ed=n;
int len=s.length();
for(int i=0;i<len;i++){
	if(s[i]=='A'){
	st=i;
	break;
	}
}
for(int i=len-1;i>=0;i--){
	if(s[i]=='B'){
	ed=i;
	break;
	}
}
if(st==-1||ed==n||st>ed)cout<<"0"<<endl;
else cout<<ed-st<<endl;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   cin>>t;

    while (t--) {
solve();
    }
    return 0;
}

D题是一个很典的题的变形，考虑再开一个专题来说这一类题，放个链接