CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A Two 0-1 Sequences

发布于:2023-01-24 ⋅ 阅读:(12) ⋅ 点赞:(0) ⋅ 评论:(0)

Problem - 1704A - Codeforces

题意:

给你两个01串a和b,你可以进行若干次这样的操作:你每次可以选择a和b数列的第二个数,把它变成第一个数和第二个数的min或max,并把第一个数去掉

去掉第一个数后,第二个数就变成了第一个数

问你进行若干次这种操作后,a能不能变成b

思路:

先判别题型:操作+结论

对于操作题,先去直观想象操作,这样的目的是为了能简化代码,因为很多情况下只需写出操作的等效操作即可

然后去想在操作中和我们的目的(或者要维护的东西 有关的一些基本性质

首先,这个操作就是等效于把a2变成a1或不变,然后去除a1

这个操作还能把a数组前面一些我们想要的元素转移到后面

然后我们的目的是让a数列变成b数列

由于每次我们只能动数列的前缀,因此两个数列的后缀必须相同

这里是个很重要的模型:

当只对数列的前缀操作时,我们去维护一些后缀的信息

后缀相同后,我们要让a数组前面的一些元素变成b1

而该操作还有一个性质就是可以把a数组前面的一些我们想要的元素传递下来

因此我们去看a数组前面的元素中是否含有b1即可

因此我们用双指针从后往前遍历,找到两个数组开始变得不一样的位置,维护这个位置,然后去看a数组在这个位置之前的元素是否存在b1即可

Code:

#include <bits/stdc++.h>
using namespace std;
const int mxn=5e1+10;
void solve(){
    int n,m,p1,p2;
    char a[mxn],b[mxn];
    scanf("%d%d",&n,&m),getchar();
    p1=n;p2=m;
    for(int i=1;i<=n;i++) scanf("%c",&a[i]);
    getchar();
    for(int i=1;i<=m;i++) scanf("%c",&b[i]);
    while(a[p1]==b[p2]&&p1>=1&&p2>=1){
        p1--;p2--;
    }
    if(p2>1){
        puts("NO");
        return;
    }else if(p2<1){
        puts("YES");
        return;
    }else{
        for(int i=1;i<=p1;i++){
            if(a[i]==b[1]){
                puts("YES");
                return;
            }
        }
    }
    puts("NO");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

总结:

1.对于操作题,先去直观想象操作,这样的目的是为了能简化代码,因为很多情况下只需写出操作的等效操作即可,然后去想在操作中和我们的目的(或者要维护的东西 有关的一些基本性质

2.总结一个操作题中很重要的模型:只对数列前缀操作时,去维护后缀的信息