当前位置：首页 > news >正文

AtCoder Regular Contest 170（A~B）

news 2025/7/25 9:30:07

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,前面至少有一个Aif(!a){cout<<-1<<endl;return ;}ans++;}else{//需要改成A,后面至少有一个Bif(!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是一个好区间，号区间有几个。

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

思路2：找到一个好区间之后就可以无限左右扩展，还需要去判断内部是否有好空间，如果内部有一个好空间，那么外部也都是好空间，所以不应该是从每一个数开始枚举，应该枚举好空间序列长度，从3开始往上扩展。

正确思路：正难则反，只会出现1~10的数，尝试构建无解的情况，从差为0开始往上，如果差重复了就必然有解，如1 1 2 4 8，几乎就没别的数可以填了，就会开始重复了。

AC代码

#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=1e5+5;int n,a[N],ans;bool check(int l,int r){//约1~100次查询per(i,l,r){per(j,i+1,r){per(k,j+1,r){if(a[j]-a[i]==a[k]-a[j])return true;}}}return false;
}void solve(){cin>>n;per(i,1,n)cin>>a[i];per(i,1,n){per(j,i+1,n){//i和j差到10以内就必然有解,复杂度是带系数的O(n),check比较烂总体约1e9if(check(i,j)){ans+=n-j+1;break;}}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t=1;while(t--)solve();return 0;
}

顺带一提不开long long见祖宗。