首页 > 其他分享 >AtCoder Regular Contest 166——A - Replace C or Swap AB

AtCoder Regular Contest 166——A - Replace C or Swap AB

时间:2023-10-10 16:16:16浏览次数:47  
标签:AtCoder AB Contest back flag Ay Ax 替换 size

题目描述

 

 中文题目描述

每个字符串的长度为N,由A, B和C组成。

通过对X执行以下三种操作任意次数(可能为零),确定是否有可能使X与y重合。

 

操作(1):选择X中的字符C替换为字符A。

操作(2):在X中选择字符C替换为字符B。

操作(3):选择X中的子字符串AB,替换为BA。更正式地说,选择一个使x的第i和(i+1)个字符分别为A和B,并将前者替换为B,后者替换为A。

你有T个测试用例需要解决。

 


 

思路解析

最开始想的爆搜,过了1/5的数据。。。分数爆零。。。

1.先考虑没有C的情况,对于一个X串中的A,可以往后任意滑动(重点)

例如:ABB -> BAB ->BBA

ABAB -> BAAB -> BABA -> BBAA

那么对于没有C的情况只需比较X中每一个A的位置是否比Y中的A小即可

2.如果有C

先考虑Y中出现C,若Y中有C,则X对应位置必须有C,且X中的A遇到C时将无法向后滑动 ( 以Y中的C为分割点进行分割 ) 

再考虑X中不与Y中C对应的C,当X中的A不够时,可以用C来填补A(将C变成A,使X与Y中的A数量一致),其余C全部变成B,然后考虑X中所有A滑动对齐Y(贪心处理,将最前面的C变成A )

X串 :  ACA  C  BAACB 

Y串 :  BAA  C  BAABA 

合并考虑,将Y中的C作为分割点切割X,在分割X的每一个块中检查的A的数量(不够C来补),检查所有A能否滑动对齐

 


代码实现

敲代码时出现了vector使用中的经典错误。。。

Ax.size()会变化!!!

//A - Replace C or Swap AB
/*每个字符串的长度为N,由A, B和C组成。
通过对X执行以下三种操作任意次数(可能为零),确定是否有可能使X与y重合。

操作(1):选择X中的字符C替换为字符A。
操作(2):在X中选择字符C替换为字符B。
操作(3):选择X中的子字符串AB,替换为BA。更正式地说,选择一个使x的第i和(i+1)个字符分别为A和B,并将前者替换为B,后者替换为A。
你有T个测试用例需要解决。

约束
1≤T≤2×10
5

1≤N≤2×10
5
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#define MAXN 200009
using namespace std ;

int N , T ;
vector<int> Ax , Ay , Cx ;//记录X,Y每个块中的A和C出现位置 
string x , y ;
bool flag ;//判断是否不可实现 

void Clear() {//处理完一个块后清空 
    while( !Ax.empty() )
        Ax.pop_back() ;
    while( !Ay.empty() )
        Ay.pop_back() ;
    while( !Cx.empty() )
        Cx.pop_back() ;
}

void check() {
    if( Ax.size()+Cx.size() < Ay.size() || Ax.size() > Ay.size() ) {//块中出现X的A加C不够,或者X中的A过多 
        flag = 1 ;
        return ;
    }
    int cnt = 0 ;
    while(Ax.size()<Ay.size()) {//贪心处理,将位置最小的C变成A 
        Ax.push_back(Cx[cnt]) ;
        cnt ++ ; 
    }
    /*for( int i = 0 ; i < Ay.size()-Ax.size() ; ++ i )//经典错误,错误原因在于Ax push_back后长度增加 
        Ax.push_back(Cx[i]) ; */
    sort(Ax.begin(),Ax.end());
    for( int i = 0 ; i < Ay.size() ; ++ i ) {
        if( Ax[i] > Ay[i] ) {//比较X中每个A是否都小于Y中的A,如果有不小于的,说明这个A无法滑动至与Y中的A对齐 
            flag = 1 ;
            return ;
        } 
    }
    return ;
}

void Solve() {
    for( int i = 0 ; i < N ; ++ i ) {
        if( y[i] == 'C' ) {
            if( x[i] != 'C' ) {
                flag = 1 ;
                break ;
            }
            check() ;
            x[i] = 'D' ;//防止切割点C被纳入用于填充的C 
            if( flag ) break;
            Clear() ;
        }
        if( y[i] == 'A' )//记录A的位置 
            Ay.push_back(i) ;
        if( x[i] == 'A' )
            Ax.push_back(i) ;
        if( x[i] == 'C' )//记录C的位置 
            Cx.push_back(i) ;
    }
    check();
    return ;
}

int main() {
    scanf("%d", &T );
    for( int t = 1 ; t <= T ; ++ t ) {
        Clear() ;
        flag = 0 ;
        scanf("%d", &N );
        cin >> x >> y ;
        Solve() ;
        if( flag == 1 )
            printf("No\n");
        else printf("Yes\n");
    }
}

 

标签:AtCoder,AB,Contest,back,flag,Ay,Ax,替换,size
From: https://www.cnblogs.com/Nomad-Joe-violet/p/17754819.html

相关文章

  • winform -Label控件
    1、设置标签文本   label1.Text="用一生下载你";2、显示/隐藏控件label1.Visible=true;   //来设置是否隐藏控件 ......
  • Non-terminating decimal expansion; no exact representable decimal result.
    上网查了一下这个异常的,找到了原因所在:通过BigDecimal的divide方法进行除法时当不整除,出现无限循环小数时,就会抛异常:java.lang.ArithmeticException:Non-terminatingdecimalexpansion;noexactrepresentabledecimalresult. 解决的办法就是给divide方法设置精确的小......
  • 35KV母线(ABC三相)电流电压温度环境温湿度振动数据采集
     一.采集需求:1、35KV母线(ABC三相),电流、电压、温度;环境温湿度、振动等数据采集2、采集频率:分钟级别(1分钟),可以的情况下,尝试秒级采集3、传感器供电:外供电和电池供电可选(电池供电首选)4、内网网线形式对接自己平台5、所有传感器采集的数据统一集中到一个主机后(多种传感器对接一......
  • abp.vnext笔记
    安装工具dotnettoolinstall-gVolo.Abp.Cli--version6.0创建项目abpnewTodoApp--version6.0.0配置数据库连接修改TodoApp.DbMigrator和TodoApp.Web项目的appsettings.json"ConnectionStrings":{//"Default":"Server=(LocalDb)\\MSSQLLocalDB;Da......
  • 【ABC320C】题解
    AtCoderBeginnerContest320ProblemC-SlotStrategy2(Easy)题解题目简述给定\(3\)个长度为\(m\)的转盘,转动过后三个转盘分别可以在不同的时间停下,求停下时所有转盘都显示相同数字的最小时间。思路由于这题\(m\le100\),数据较水,所以可以先把每个数列都复制\(......
  • 【ABC320D】题解
    AtCoderBeginnerContest320ProblemD-RelativePosition题解题目保证不矛盾,就可以直接vector建图,然后dfs一遍,边权为\((w_x,w_y)\)表示坐标的差,从\(u=1\)开始搜索,设点\(u,v\)有一条无向边,\(v_x=u_x+w_x,v_y=u_y+w_y\),最后如果没有被标记过的话(也就是没有......
  • Sqli-labs通关实况之第一关
    Sqli-labsless-1首先看题,提示你输入数字值的ID作为参数,我们输入?id=1,发现直接得到登录名和密码输入的数值不同,回显内容也不同,所以输入的内容是带入到数据库里面查询了接下来判断是字符型还是数字型我们可以在数值1后面加上一个单引号和双引号来判断,先加入单引号看看。可以......
  • DataGridView绑定DataTable的建议方式
    DataGridView绑定DataTable的建议方式1.将DataTable绑定到BindingSource2.将BindingSource绑定到DataGridView3.DataGridView修改完要从Datatable取值时,同步过去时,BindingSource和DataGridView两个都要执行EndEdit()publicpartialclassForm1:Form{D......
  • zabbix6.0一键安装脚本
    ......
  • Babel基础知识
    Babel中文官网Babel入门教程-阮一峰Babel博客教程-姜瑞涛Bilibili--系列Babel视频学习教学1.介绍1.1简介Babel是一个JavaScript编译器。Babel是一个工具链,主要用于将采用ECMAScript2015+语法编写的代码转换为向后兼容的JavaScript语法,以便能够运行在当前和旧......