关于队里面最菜的在博客打卡第二十九天这件事

62 阅读 0 评论 41 点赞

我是靠谱客的博主慈祥舞蹈，最近开发中收集的这篇文章主要介绍关于队里面最菜的在博客打卡第二十九天这件事，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：https://codeforces.com/contest/1553/problem/D

这是一道神奇的dp题，是给你一个两个字符串a,b, 然后让你判断是否可以通过多次删去a中连续的两个字符或者删去任意前缀，然后让剩余字符和b完全相等，刚开始入手这道题以为是简单的dp，于是就鬼使神差的用一维dp但是两个for循环去写结果第86个数据tle了（很痛苦），后来试着去优化发现有一些数据是用过就可以抛弃的，然后写了个set倒排写法，结果tle到第4个，整破防了直接。。。。，想了好长时间，然后今天上午接着去想这题，直接剖析问题的本质，最后发现字符串a和b的奇偶性对应的成立情况分别唯一对应一种在字符串中来回跳的选择和结尾的下标的奇偶性。于是就直接暴力判断写出O(n)的代码（太痛苦了QAQ

题目：

ac代码：

#include<iostream>
#include<cstdio>

using namespace std;
typedef long long int LL ;
const int N = 1e6 + 10;

bool st[N];
string a, b ;

bool check01()
{
    int lena = a.size() , lenb = b.size();
    a = '*' + a;
    b = '*' + b;
    int bj = 0;//0表示偶，1表示奇。
    int cntb = 1;
    for(int i = 1; i <= lena ; i ++)
        if(i % 2 == bj && a[i] == b[cntb])
        {
            cntb ++ ;
            if(cntb > lenb)
            {
                if(bj == 0)return true;
                else return false;
            }
            bj = 1 - bj;
        }
    return false;
}

bool check00()
{
    int lena = a.size() , lenb = b.size();
    a = '*' + a;
    b = '*' + b;
    int bj = 1;//0表示偶，1表示奇。
    int cntb = 1;
    for(int i = 1; i <= lena ; i ++)
    {
        if(i % 2 == bj && a[i] == b[cntb])
        {
            cntb ++ ;
            if(cntb > lenb)
            {
                if(bj == 0)return true;
                else return false;
            }
            bj = 1 - bj;
        }
    }
    return false;
}

bool check11()
{
    int lena = a.size() , lenb = b.size();
    a = '*' + a;
    b = '*' + b;
    int bj = 1;//0表示偶，1表示奇。
    int cntb = 1;
    for(int i = 1; i <= lena ; i ++)
    {
        if(i % 2 == bj && a[i] == b[cntb])
        {
            cntb ++ ;
            if(cntb > lenb)
            {
                if(bj == 1)return true;
                else return false;
            }
            bj = 1 - bj;
        }
    }
    return false;
}

bool check10()
{
    int lena = a.size() , lenb = b.size();
    a = '*' + a;
    b = '*' + b;
    int bj = 0;//0表示偶，1表示奇。
    int cntb = 1;
    for(int i = 1; i <= lena ; i ++)
    {
        if(i % 2 == bj && a[i] == b[cntb])
        {
            cntb ++ ;
            if(cntb > lenb)
            {
                if(bj == 1)return true;
                else return false;
            }
            bj = 1 - bj;
        }
    }
    return false;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> a >> b ;
        
        if(a.size() < b.size())
        {
            cout <<"NO"<<endl;
            continue;
        }
        for(int i = 0 ; i < b.size() ; i ++)st[i] = false;
        if(a.size() % 2 == 0 && b.size() % 2 == 1)
            if(check01())cout <<"YES"<<endl;
                else cout <<"NO"<<endl;
        else if(a.size() % 2 == 0 && b.size() % 2 == 0)
            if(check00())cout<<"YES"<<endl;
            else cout <<"NO"<<endl;
        else if(a.size() % 2 == 1 && b.size() % 2 == 1)
            if(check11())cout <<"YES"<<endl;
            else cout <<"NO"<<endl;
        else if(a.size() % 2 == 1 && b.size() % 2 == 0)
            if(check10())cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
    }
}

这道题不知道写了多长时间。。。。。。