AtCoder Regular Contest 170（A~B）

A - Yet Another AB Problem

给你两个字符串S和T，你可以对S执行操作，选择两个字符，将前面的改为A，后面的改为B，最少操作几次可以把S改成T。如果改不成就输出-1。

从左往右一个一个改过去，分类讨论，如果是要把A改成B。

S：A->B

T：B

那么T中该位置前面一定要有一个A，否则无法修改。

如果要把B改成A。

S：B->A

T：A

那么T中该位置后面一定要有一个B，否则无法修改。

其中可以本次修改可以更优，即S中后面有一个A，对应T后面的B（一次修改，完成两次对应）

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;

int n,ans,a;
string s,t;

queue<int>q;
int b[N];

void solve(){
    cin>>n>>s>>t;
    per(i,0,n-1){
        if(t[i]=='B' and s[i]=='A')q.push(i);
    }
    rep(i,n-1,0){
        if(t[i]=='B')b[i]++;
        if(i>=1)b[i-1]=b[i];
    }
    per(i,0,n-1){
        if(t[i]=='A')a++;
        if(s[i]!=t[i]){
            if(s[i]=='A'){//需要改成B,前面至少有一个A
                if(!a){
                    cout<<-1<<endl;
                    return ;
                }
                ans++;
            }else{//需要改成A,后面至少有一个B
                if(!b[i+1]){
                    cout<<-1<<endl;
                    return;
                }
                ans++;
                while(!q.empty() and q.front()<i)q.pop();
                if(!q.empty()){
                    s[q.front()]='B';
                    q.pop();
                }
            }
        }
    }

    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

补题：B - Arithmetic Progression Subsequence

给你1e5个数，每个数是1~10。对于l和r区间，如果区间中有三个数（不管顺序）a[j]，a[k]，a[l]，满足1 2 3或3 2 1（差为1） 或者1 5 9，9 5 1（差为4）这种差相等的，说明l和r是一个好区间，号区间有几个。

思路：考虑差值最大只有可能是4，对于一个数a[i]，只需要枚举所有差值（sub：1~4），a[i]，a[i]+sub，a[i]+2*sub（注意也可以是减法），如果在a[i]之后存在这样的值，那么第三个数的下标及其以后都是好区间。所以只需要想一个算法维护每个数后面的1~10第一次出现的位置。