CF 1178E Archaeology 题解

题面

这道题竟然是E？还是洛谷中的黑题？

wow~！！

于是就做了一下；

然后一下就A了；(这并不代表想的容易，而是写的容易)

这道题就是骗人的！！

什么manacher，什么回文自动机，去靠一边站着，看我的无敌大模拟！

可以设定l，r两个点，初始时分别指向1和n；

如果是s[l]==s[r],那么答案就更新(ans+=2,但当l==r时,ans仅加1就够了)；

如果不等,那么就回文自动......诶？等等，题目说只有a，b，c？而且相邻的两位不等？蛤？这是什么情况？

如果s[i]!=s[j]，因为s[j-1]!=s[j],s[i+1]!=s[i],所以至少就是以下几种情况中的一种，s[i+1]==s[j],s[i]==s[j-1],s[i+1]==s[j-1]；

然后对其模拟，然后就轻松愉快的A啦~

#include <bits/stdc++.h>

using namespace std;

int n;

char s[];

bool bo[];

int cnt;

int main() {

    scanf("%s", s + );

    int l=,r=;

    n=r=strlen(s + );

    while(l <= r){

        if(s[l] == s[r]){

            bo[l] = bo[r] = ;

            cnt+=;

            if(l==r){

                --cnt;

            }

            ++l;

            --r;

        }

        else if(l+<=r&&s[l+]==s[r]){

            bo[l+]=bo[r]=;

            cnt+=+(l+!=r);

            l+=, --r;

        }

        else if (l<=r-&&s[l]==s[r-]){

            bo[l]=bo[r-]=;

            cnt+=+(l!=r-);

            ++l, r-=;

        }

        else{

            ++l, --r;

        }

    }

    if(cnt>=n/){

        for(int i=;i<=n;i++){

            if(bo[i]){

                printf("%c",s[i]);

            }

        }

        puts("");

    }

    else{

        puts("IMPOSSIBLE");

    }

    return ;

}

巴特西

CF 1178E Archaeology 题解

最新文章

热门文章