hiho一下第58周《Beautiful String》题目分析

23
13

题意分析

给定字符串S，判定S是否存在子串S’满足"aa…abb…bcc…c"的形式。其中abc为连续的三个字母，且a,b,c的数量相同。

原题目中数量相等的连续n(n>3)个字母也是可行的，而实际上当n>3时一定包含有n=3的情况。比如"abcd"就包含有"abc"和"bcd"两个合法子串。

算法分析

最基本的思路为对S的每一个子串进行判定是否满足要求。枚举子串的起点、终点以及检查是否合法。

假设S的长度为N，则时间复杂度为O(N^3)。

For i = 0..N-1
    For j = 0..N-1
        check(S[i..j])
    End For
End For

这样的做法对于N稍大的数据来说就会超过时限。

进一步考虑，由于合法子串中相同的字母总是连续的，我们不妨用(c,n)来表示一串连续相同的字母，比如"aaa"表示(a,3)，"bb"表示为(b,2)。

我们将整个字符串S用(c,n)表示，得到{(c[1], n[1]),(c[2],n[2]),...,(c[t],n[t])}的序列。其中我们合法的子串也可以表示为{(a,n),(b,n),(c,n)}。

则算法改变为在序列{(c[1], n[1]),(c[2],n[2]),...,(c[t],n[t])}中判定是否存在连续的3个元素满足c[i],c[i+1],c[i+2]连续且n[i] == n[i+1] == n[i+2]。

预处理时间为O(N)，得到的序列长度最大为N，所以整体的时间复杂度降低为O(N)。

For i = 1 .. t-2
    If (c[i]+1 == c[i+1] and c[i+1]+1 == c[i+2]) and (n[i] == n[i+1] == n[i+2])
        Return True
    End If
End For

然而实际运行会发现，这个算法是不正确的。比如："aaaabbccc"，其对应的序列为{(a,4),(b,2),(c,3)}，根据我们上面的算法并不能找到合法子串。但实际上存在合法子串"aabbcc"。

很显然，问题出在我们对于n[i],n[i+1],n[i+2]的判定上。通过上面的反例我们可以发现，在子串中n[i],n[i+2]的值其实是可以变动的，唯一固定的是n[i+1]的值。当n[i]>n[i+1]时，我们只要删去前面的若干个字母，就能够使得n[i]==n[i+1]。同理对于n[i+2]>n[i+1]时，我们删去后面的字母。因此只要有n[i]>=n[i+1],n[i+2]>=n[i+1]，就一定能够通过变换使得n[i] == n[i+1] == n[i+2]。

改正后我们的算法代码为：

For i = 1 .. t-2
    If (c[i]+1 == c[i+1] and c[i+1]+1 == c[i+2]) and (n[i] >= n[i+1] and n[i+1] <= n[i+2])
        Return True
    End If
End For

结果分析

在实际的比赛中，该题目的通过率仅为26%。

但根据赛后的统计结果，大部分的选手都使用了朴素的算法通过了规模较小的数据点。在该题目上获取了10~60不等的分数。

其中比较有意思的是有一位选手仅仅判定连续3个字母是否连续，也获得了60的分数。

而分布在70~90分数段的程序，随机抽取了若干样本，发现大多数都是想到了正确算法的。而导致他们丢分的主要原因则是多组数据产生的初始化问题。

  • 4 abccde 请问一下那这个是怎么判断？

  • 依次会扫描到abc，cde满足条件

  • 添加评论
  • ✖reply

13 answer(s)

0 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<char,int> P;
int t;
int n;
char s[10*1024*1024+12];
int cnt=0;
vector<P> v;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        scanf("%s",s);
        getchar();
        cnt=0;
        if(n<3)
        {
            cout<<"NO"<<endl;
            continue;
        }
        v.push_back(make_pair(s[0],1));
        for(int i=1;i<strlen(s);i++)
        {
            if(s[i]==v[cnt].first)v[cnt].second++;
            else
            {
                cnt++;
                v.push_back(make_pair(s[i],1));
            }
        }
        if(cnt+1<3)
        {
            cout<<"NO"<<endl;
            continue;
        }
        int flag=1;
        for(int i=0;i<v.size()-2;i++)
        {
            if(v[i+1].first-v[i].first==1&&v[i+2].first-v[i+1].first==1&&v[i].second>=v[i+1].second&&v[i+2].second>=v[i+1].second)
            {
                cout<<"YES"<<endl;
                flag=0;
                break;
            }
        }
        if(flag)cout<<"NO"<<endl;
        v.clear();
    }
    return 0;
}

求助大神，请问那有问题啊，问什么会有数据过不了？

0 
#include<iostream>

include

include

include

include

using namespace std; typedef pair P; int t; int n; char s[10*1024*1024+12]; int cnt=0; vector

v; int main() { cin>>t; while(t--) { cin>>n; scanf("%s",s); getchar(); cnt=0; if(n<3) { cout<<"NO"<=v[i+1].second&&v[i+2].second>=v[i+1].second) { cout<<"YES"<

0

include

include

include

include

include

using namespace std; typedef pair P; int t; int n; char s[10*1024*1024+12]; int cnt=0; vector

v; int main() { cin>>t; while(t--) { cin>>n; scanf("%s",s); getchar(); cnt=0; if(n<3) { cout<<"NO"<=v[i+1].second&&v[i+2].second>=v[i+1].second) { cout<<"YES"<

0

include

include

include

int main(void) { char *p[10]; int i,test,n,j,count=0; unsigned int num,bak; //bak记录查找源位置！ char str[3][2]; unsigned char flag = 0;

printf("Please Input 1~10:\n");
scanf("%d",&test);

for (i=0;i<test;i++)
{
    scanf("%d",&n);
    if (n<10*1024*1024)
    {
        p[i] = (char *)malloc((n+1)*sizeof(char));
        scanf("%s",p[i]);
    }
    else
        printf("Please Input n less 10M");
}

memset(str,0,sizeof(str));
for (i=0;i<test;i++)
{
    n = strlen(p[i]);
    for (j=0,num=0,bak=j;j<n&&flag==0;j++)  //j++与变量bak配合使用！从源位置起始。
    {
        count++;
        if(*(p[i]+j)!=*(p[i]+j+1)&&num<3)
        {
            str[num][0] = *(p[i]+j);
            str[num][1] = count;
            num++;
            if (num == 3)
            {
                num = 0;
                if ((str[0][0]+1==str[1][0])&&(str[1][0]+1==str[2][0])&&(str[0][1]>=str[1][1])&&(str[1][1]<=str[2][1]))
                    flag = 1;
                else
                    j = bak++;  //从原位置的下一个位置开始查找！
            }
            count = 0;
        }
    }
    if (flag == 1)
    {
        printf("Yes!\n");
        flag = 0;
        free(p[i]);
    }
    else
    {
        printf("No!\n");
        free(p[i]);
    }
    memset(str,0,sizeof(str));
}
//printf("%c\n",*(p[1]+1));

/* i = 0; for (i=0;i 

return EXIT_SUCCESS;

}

0

能给些测试用例吗，我半天都找不来处在哪里，大家可以帮我看看嘛

include

include

using namespace std;

bool isbeautiful(char *p, int len) { int times[26] = {0}; int index = 0; int pre1 = -1; int pre2 = -1;

while (index < len)
{
    while (index < len - 1)
        if (p[index] == p[index + 1])
        {       
            times[p[index]-'a']++;
            index++;
        }
        else
            break;
    times[p[index]-'a']++;

    if (pre1 == -1)
    {
        pre1 = index;
        index++;
    }
    else
    {
        if (p[pre1] + 1 != p[index])
        {
            pre1 = index;
            index++;
            if (pre2 != -1)
            {
                times[p[pre2]-'a'] = 0;
                pre2 = -1;
            }

        }
        else
        {
            if (pre2 == -1)
            {
                pre2 = pre1;
                pre1 = index;
                index++;
            }
            else
            {
                if (times[p[pre1]-'a'] <= times[p[pre2]-'a'] && times[p[pre1]-'a'] <= times[p[index]-'a'])
                    return true;
                else
                {
                    if (times[p[index]-'a'] > times[p[pre1]-'a'])
                    {
                        times[p[pre2]-'a'] = 0;
                        times[p[pre1]-'a'] = 0;
                        pre2 = -1;
                        pre1 = index;
                        index++;
                    }
                    else
                    {
                        times[p[pre2]-'a'] = 0;
                        pre2 = pre1;
                        pre1 = index;
                        index++;
                    }

                }

            }

        }

    }

}

return false;

}

int main() {

int t;
scanf("%d", &t);
int len;
char *arr= new char[10*1024*1024+100];
while (t > 0)
{
    scanf("%d",&len);
    scanf("%s",arr);

    bool res = isbeautiful(arr,len);
    if (res)
        printf("YES\n");
    else
        printf("NO\n");

    t--;
}

delete[] arr;
system("pause");
return 0;

}

0

只通过了少部分数据，难道大数据都超时了？

0

我就是90%，醉了。。。

0

之前没看题目分析，理解错题意想复杂了，难怪一直WA，今天一改就AC了。这道题就是状态转移判断，最多扫描完一遍字符串就得出结果了，感觉简单。字符串长度也不用事先定义，用malloc就行~

0

问下字符串的长度设置为多少合适？是10 * 1024 + 5大小就行么？还是其他的？

0

题目真心模糊

0

觉得题目有点水……

  • 这是第一题，算是个热身题。后面3题越来越难。

  • 添加评论
  • ✖reply
4

我感觉通过率低很有可能是题意有点模糊.......

2 
mark

write answer 切换为英文 切换为中文

转发分享

▲