前缀和40...

P2697 宝石串

HgSO4_QwQ @ 2021-04-12 20:07:45

\color{Red}{WA:3,5,6,7,8,9}

\color{Orange}{40\ Points}

#include<iostream>
using namespace std;

int R[1000000];
int G[1000000];

int main()
{
    string s;
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='R')
        {
            R[i]=R[i-1]+1;
            G[i]=G[i-1];
        }
        else if(s[i]=='G')
        {
            G[i]=G[i-1]+1;
            R[i]=R[i-1];
        }
    }
    int maxn=0,ans=0;
    for(int i=0;i<len;i++)
    {
        for(int j=i+1;j<len;j++)
        {
            int g=G[j]-G[i];
            int r=R[j]-R[i];
            if(g==r)
            {
                if(j-i>maxn)
                {
                    maxn=j-i;
                }
            }
        }
    }
    cout<<maxn;
    return 0;
}

还有，竟然没\color{#000099}{T}

by fsdgakjl @ 2021-04-12 20:39:31

下标从1开始用啊（没RE很离谱）

然后把这儿

for(int i=0;i<len;i++)
{
    for(int j=i+1;j<len;j++)
    {
        int g=G[j]-G[i];
        int r=R[j]-R[i];
        if(g==r)
        {
            if(j-i>maxn)
            {
                maxn=j-i;
            }
        }
    }
}

改成

for(int i=1;i<=len;i++)
{
    for(int j=i+1;j<=len;j++)
    {
        int g=G[j]-G[i-1];
        int r=R[j]-R[i-1];
        if(g==r)
        {
            if(j-i+1>maxn)
            {
                maxn=j-i+1;
            }
        }
    }
}

再把最开始的循环改成从1~n就行了。

by HgSO4_QwQ @ 2021-04-12 20:43:52

谢谢啦

\color{#0AC666}{Thanks}

by HgSO4_QwQ @ 2021-04-12 20:47:20

@wyy

50?

by HgSO4_QwQ @ 2021-04-12 20:47:49

#include<iostream>
using namespace std;

int R[1000000];
int G[1000000];

int main()
{
    string s;
    cin>>s;
    int len=s.length();
    for(int i=1;i<=len;i++)
    {
        if(s[i]=='R')
        {
            R[i]=R[i-1]+1;
            G[i]=G[i-1];
        }
        else if(s[i]=='G')
        {
            G[i]=G[i-1]+1;
            R[i]=R[i-1];
        }
    }
    int maxn=0,ans=0;
    for(int i=1;i<=len;i++)
    {
        for(int j=i+1;j<=len;j++)
        {
            int g=G[j]-G[i-1];
            int r=R[j]-R[i-1];
            if(g==r)
            {
                if(j-i+1>maxn)
                {
                    maxn=j-i+1;
                }
            }
        }
    }
    cout<<maxn;
    return 0;
}

by fsdgakjl @ 2021-04-12 20:55:54

这个字符串也要从一开始用

具体做法是:

在

int len=s.length();

的后面写上:

s='0'+s;

这样就是直接给字符串开头填充一个0帮助占位

这样原先的0~len-1位就变为1~len位

by HgSO4_QwQ @ 2021-04-12 21:01:15

\color{Green}{100}$ 了，谢谢 $!!

by fsdgakjl @ 2021-04-12 21:02:26

不客气

by yangshiyu10 @ 2021-06-27 16:38:32

同谢！