圣宠宠物网站建设,上海贸易公司排名,网站策划书格式及范文1000字免费,wordpress 推酷A - Yet Another AB Problem
给你两个字符串S和T#xff0c;你可以对S执行操作#xff0c;选择两个字符#xff0c;将前面的改为A#xff0c;后面的改为B#xff0c;最少操作几次可以把S改成T。如果改不成就输出-1。
从左往右一个一个改过去#xff0c;分类讨论#x…A - Yet Another AB Problem
给你两个字符串S和T你可以对S执行操作选择两个字符将前面的改为A后面的改为B最少操作几次可以把S改成T。如果改不成就输出-1。
从左往右一个一个改过去分类讨论如果是要把A改成B。
SA-B
TB
那么T中该位置前面一定要有一个A否则无法修改。
如果要把B改成A。
SB-A
TA
那么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 N2e55;int n,ans,a;
string s,t;queueintq;
int b[N];void solve(){cinnst;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(i1)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-1endl;return ;}ans;}else{//需要改成A,后面至少有一个Bif(!b[i1]){cout-1endl;return;}ans;while(!q.empty() and q.front()i)q.pop();if(!q.empty()){s[q.front()]B;q.pop();}}}}coutansendl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t1;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 99 5 1差为4这种差相等的说明l和r是一个好区间号区间有几个。
思路1考虑差值最大只有可能是4对于一个数a[i]只需要枚举所有差值sub1~4a[i]a[i]suba[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 N1e55;int n,a[N],ans;bool check(int l,int r){//约1~100次查询per(i,l,r){per(j,i1,r){per(k,j1,r){if(a[j]-a[i]a[k]-a[j])return true;}}}return false;
}void solve(){cinn;per(i,1,n)cina[i];per(i,1,n){per(j,i1,n){//i和j差到10以内就必然有解,复杂度是带系数的O(n),check比较烂总体约1e9if(check(i,j)){ansn-j1;break;}}}coutansendl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t1;while(t--)solve();return 0;
}
顺带一提不开long long见祖宗。
