问题标题: 酷町堂:7082 字符串为什么90分

0
0
已解决
吴庞茂旭
吴庞茂旭
资深光能
资深光能

题目链接: 酷町堂:7082

题目传送门

我的代码:

/*
NAME:7082 字符串
NODE/TIPS:NONE
*/
//std
#include <iostream>
#include <cstdio>
#define int long long
#define capital(x) ((x)>='A'&&(x)<='Z')
#define IKOCCF while(true);
using namespace std;
struct node{
    int size;
    bool flag;
};
const int MAXN=1000005;
string s; 
int n,maxl,maxs,maxn;
node a[MAXN];
signed main(){
    cin>>s;
    a[0]=(node){0,false};
    n=1;
    a[n]=(node){1,capital(s[0])};
    for(int i=1;i<s.size();i++){
        if(capital(s[i])==capital(s[i-1])){
            a[n].size++;
        } else{
            a[++n]=(node){1,capital(s[i])};
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i].flag){
            maxl=max(maxl,a[i].size);
        } else{
            maxs=max(maxs,a[i].size);
        }
        if(a[i].size==1){
            maxn=max(maxn,a[i-1].size+a[i+1].size);
        }
    }
    cout<<maxs<<endl<<maxl<<endl<<maxn;
    return 0;
} 

第8个测试点错了,求解答!


2
已采纳
汪恺恒
汪恺恒
中级启示者
中级启示者

我和你的思路不太一样,我是这样写的

首先要求最长连续一段全是小写英文字母构成的子串的长度和最长连续一段全是大写英文字母构成的子串的长度。

这个很简单,直接DP就行了

第三问可以这样考虑,如果当前位置为小写字母,则往前遍历,统计前面连续大写字母的数量,记为lc;再往后遍历,统计后面连续大写字母的数量,记为rc,这样就是在模拟删去这个字符后,最长连续一段全是大写英文字母构成的子串的长度,自然长度就是lc+rc。

大写字母同理,每次取最大值就行了

举个例子,比如字符串是HelloWorld,枚举到W时,发现前面与其相连的有4个小写字母,后面与其相连的有4个小写字母,则这时得到的答案就为4+4=8

当然也可以用前缀和、后缀和来优化,但不优化也能AC

我要回答