首页 > 其他分享 >ARC 170_A

ARC 170_A

时间:2024-02-18 19:00:12浏览次数:29  
标签:s2 s1 ARC && ans 更换 suma 170

AT_arc170_a [ARC170A] Yet Another AB Problem 题解

这道题做了我七天
(同时也是我第一到通过的 ARC 题)
太酷了

其实还是比较好理解的
原题题干

原题题干(洛谷)

输出 \(-1\) 的情况:

  1. 在第一个更换的 \(B~A\) (即 \(S_i\) 位)之前有 \(A~B\) (即 \(S_j\) 位)的更换
  2. 在最后更换的 \(A~B\) (即 \(S_j\) 位)之后有 \(B~A\) (即 \(S_i\) 位)的更换
  3. 在 \(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;
}

本蒟蒻第一次发题解,不好之处见谅 (汗)

标签:s2,s1,ARC,&&,ans,更换,suma,170
From: https://www.cnblogs.com/adsd45666/p/18019824

相关文章

  • NewStarCTF 2023 WEEK2|REVERSE SMC 使用IDApython静态解决SMC
    先来一篇IDApyhotn的指令教程https://www.cnblogs.com/zydt10/p/17676018.html*自己编的这题对应的expa=[0x11,0x22,0x33,0x44]foriinrange(38):result=a[i&3]ida_bytes.patch_byte(0x403040+i,get_wide_byte(0x403040+i)^result)在IDA中运行完exp之后,......
  • [ARC122E] Increasing LCMs 题解
    Description给定长度为\(N\)的正整数序列\(\{A_i\}\),满足\(A_i\)单调升。问是否能将\(\{A_i\}\)重排为序列\(\{x_i\}\),满足:令\(y_i=\operatorname{LCM}(x_1,\dots,x_i)\),\(\forall1\lei<N,y_i<y_{i+1}\)(即\(y_i\)单调升)。$1\\leq\N\\leq\......
  • ARC171 B~E 四个数数
    A比较简单就不放了,这样刚好是全是数数题F先咕咕咕一会。Blink其实就是对于所有\(P_i>i\)的\(i\)到\(P_i\)连边,然后\(A_i\)就是\(i\)号点在的链上的最后一个点。考虑集合\(S_i=\{j\midA_j=i\}\),显然如果需要有解那么\(S_i\)中最大值必定为\(i\),而且这些点一......
  • Elasticsearch不同集群间备份恢复(S3存储)
    S3存储首先都知道需要在ES集群上安装S3插件以及重启集群在MINIO集群创建相应的桶Kibana上注册快照存储库,两个不同的集群需要对接到同一个S3存储库,对接后会自动识别桶里的快照《见上一篇博客》恢复搭建的恢复集群已对接到备份集群对接的MINIO集群了可以看到已自动识别到......
  • [ARC165C] Social Distance on Graph
    转化题意,对图进行黑白染色,求最大的\(X\)满足所有\(u,v\)间最短路径小于\(X\)的\(u,v\)异色。很明显是二分答案,假设现在二分到\(mid\),转化为判定型问题。直接\(n^2\)枚举点肯定不对。发现性质:如果\(u,v\)的最短路径长度小于\(X\)且最短路径上经过的边数大于\(......
  • [ARC003D] シャッフル席替え
    这道题使用了蒙特卡罗方法。蒙特卡罗方法是指使用随机数来解决计算问题的方法。他的工作原理就是两件事:不断抽样、逐渐逼近。例如计算\(\pi\)。这样的一个圆,在它的右上角做一个正方形。则圆的面积为\(\frac{\pi}{4}\),正方形的面积为\(1\)。现在向图中随机放点,则圆的面积......
  • [ARC067F] Yakiniku Restaurants
    首先考虑暴力。\(\mathcalO(n^2m)\)枚举左右两个端点,再贪心地选其中\(M\)张票的美味度最大那一家餐馆。复杂度不可接受,但是不难感觉到正解应该是\(\mathcalO(n^2)\)的。考虑枚举左端点\(i\),对于当前左端点,记每一个右端点\(j\)的答案为\(now_j\),若暂时不考虑距离,大部分......
  • [ARC108F] Paint Tree
    本题有两种思路。首先,对于普通的树,到一个点最远的点一定是直径的端点之一。记\(S\)表示直径长度。做法\(1\)先求出一条直径,若直径的两个端点颜色相同,则最长距离一定为直径。否则,令两个端点分别为\(x,y\),并钦定\(x,y\)不同色。枚举答案\(d\),所有到\(x\)距离\(>d\)的......
  • {fastcluster}:快速分层聚类程序(Fast Hierarchical Clustering Routines)
    1.函数代码该R包中最主要的函数是 hclust ,代码如下:>fastcluster::hclustfunction(d,method="complete",members=NULL){if(method=="ward"){message("The\"ward\"methodhasbeenrenamedto\"ward.D\&quo......
  • P1706 全排列问题
    全排列问题题目描述按照字典序输出自然数\(1\)到\(n\)所有不重复的排列,即\(n\)的全排列,要求所产生的任一数字序列中不允许出现重复的数字。输入格式一个整数\(n\)。输出格式由\(1\simn\)组成的所有不重复的数字序列,每行一个序列。每个数字保留\(5\)个场宽。......