UVALive - 6439（思维题）

题目链接：https://vjudge.net/contest/241341#problem/F

题目大意：给你一个字符串，你可以用任意单个字符代替其中的一个子串，使它形成一个回文串，要求形成的回文串长度最长。

例如：S=‘ABCADDABCA’这个字符串

你可以令a= ‘ABCA’，b= ‘DD’，则S='aba'，长度为3；

你可以令a= ‘ABCA’,b='D'，则S=‘abba’，长度为4；

你也可以令a= ‘A’，b= ‘BC’，c= ‘D’，则S=’abaccaba',长度为8；

8即使该字符串形成回文串的最长的长度。

解题思路：定义两个空的字符串a，b，一个从长串的头开始往后插入a当中，另一个就是从长串的尾部开始往前插入b当中，只要他们相同计数加2，然后又对它们清空处理，知道中间的位置就行，最后如果字符串不为空，计数还得加1。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string.h>

#include<deque>

using namespace std;

const int inf=0x3f3f3f3f;

char s[];

int main()

{

    int t;

    cin>>t;

    int kase=;

    while(t--)

    {

        kase++;

        scanf("%s",s);

        int count=;

        int len=strlen(s);

        string a,b;

        a="",b="";

        for(int i=;i<=(len-)/;i++)

        {

            a+=s[i];

            b=s[len-i-]+b;

            if(a==b&&i!=len-i-)

            {

                count+=;

                a="";

                b="";

            }

        }

        if(!a.empty()) count++;

        printf("Case #%d: %d\n",kase,count);

    }

    return ;

}

/*

4

PASTIPAS

ABCADDABCA

MADAMIAMADAM

ACMICPCJAKARTASITE

*/

巴特西

UVALive - 6439（思维题）

最新文章

热门文章