确定这道题标签没有错？

超长数字串
数据弱爆了 LV 6 @ 12 年前

测试数据 #0: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #1: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #2: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #7: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #10: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #11: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #12: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #13: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #14: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #15: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #16: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #17: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #18: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #19: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #20: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #21: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #22: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #23: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #24: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #25: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #26: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #27: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #28: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #29: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #30: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #31: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #32: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #33: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #34: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #35: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #36: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #37: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #38: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

测试数据 #39: TimeLimitExceeded, time = 1015 ms, mem = 1692 KiB, score = 0

kmp做法，数组开小了就爆，开大了就超，确定可以用KMP？我记得M67大神说了不可以的

mockingjay LV 7 @ 8 年前

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char a[6000005];
int kmp[205];
char inp[205];
int size;

void getkmp()
{
    kmp[0] = 1;
    kmp[1] = 1;
    int i = 2;
    int k = 1;
    int temp = 1;
    while (i <= size)
    {
        if(inp[i] == inp[k])
        {
            kmp[i] = temp;
            ++i;
            ++k;
        }
        else
        {
            while(inp[i] != inp[k] && k > 0)
            {
                temp += kmp[k];
                k -= kmp[k];
            }
            kmp[i] = temp;
            ++i;
            ++k;
        }
    }
}

int main()
{
    int i = 1;
    while(scanf("%c",&inp[i]))
    {
        if(inp[i] == '\n')
        {
            break;
        }
        ++i;
        //printf("success\n");
    }
    size = i - 1;
    getkmp();
    /*for(int j = 1;j <= size;++j)
    {
        printf("%d ",kmp[j]);
    }*/
    int k = 1,temp;
    for(int j = 1;j < 10;++j)
    {
        a[k] = '0' + j;
        ++k;
    }
    for(int j = 10;j < 100;++j)
    {
        temp = j;
        a[k] = '0' + temp / 10;
        ++k;
        temp %= 10;
        a[k] = '0' + temp;
        ++k;
    }
    for(int j = 100;j < 1000;++j)
    {
        temp = j;
        a[k] = '0' + temp / 100;
        ++k;
        temp %= 100;
        a[k] = '0' + temp / 10;
        ++k;
        temp %= 10;
        a[k] = '0' + temp;
        ++k;
    }
    for(int j = 1000;j < 10000;++j)
    {
        temp = j;
        a[k] = '0' + temp / 1000;
        ++k;
        temp %= 1000;
        a[k] = '0' + temp / 100;
        ++k;
        temp %= 100;
        a[k] = '0' + temp / 10;
        ++k;
        temp %= 10;
        a[k] = '0' + temp;
        ++k;
    }
    for(int j = 10000;j < 100000;++j)
    {
        temp = j;
        a[k] = '0' + temp / 10000;
        ++k;
        temp %= 10000;
        a[k] = '0' + temp / 1000;
        ++k;
        temp %= 1000;
        a[k] = '0' + temp / 100;
        ++k;
        temp %= 100;
        a[k] = '0' + temp / 10;
        ++k;
        temp %= 10;
        a[k] = '0' + temp;
        ++k;
    }
    for(int j = 100000;j < 1000000;++j)
    {
        temp = j;
        a[k] = '0' + temp / 100000;
        ++k;
        temp %= 100000;
        a[k] = '0' + temp / 10000;
        ++k;
        temp %= 10000;
        a[k] = '0' + temp / 1000;
        ++k;
        temp %= 1000;
        a[k] = '0' + temp / 100;
        ++k;
        temp %= 100;
        a[k] = '0' + temp / 10;
        ++k;
        temp %= 10;
        a[k] = '0' + temp;
        ++k;
    }
    //printf("print start\n");
    /*for(int j = 1;j <= 1000;++j)
    {
        printf("%c ",a[j]);
    }*/
    //printf("\n%d",size);
    i = 0;
    k = 0;
    while(k < size)
    {
        if(a[i + 1] == inp[k + 1])
        {
            //printf("%d matched!\n",i + 1);
            i += 1;
            k += 1;
        }
        else
        {
            if(k == 0)
            {
                i += 1;
                continue;
            }
            k -= kmp[k];
        }
    }
    printf("%d" ,i - size + 1);
    //system("pause");
    return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 6428 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 6412 KiB, score = 0
测试数据 #9: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #10: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #11: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #12: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
测试数据 #13: Accepted, time = 0 ms, mem = 6424 KiB, score = 10
测试数据 #14: Accepted, time = 0 ms, mem = 6424 KiB, score = 10
测试数据 #15: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #16: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
测试数据 #17: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #18: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #19: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #20: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #21: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
测试数据 #22: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
测试数据 #23: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
测试数据 #24: Accepted, time = 15 ms, mem = 6428 KiB, score = 10
测试数据 #25: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
测试数据 #26: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
测试数据 #27: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
测试数据 #28: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
测试数据 #29: RuntimeError, time = 15 ms, mem = 6416 KiB, score = 0
测试数据 #30: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
测试数据 #31: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #32: RuntimeError, time = 31 ms, mem = 6424 KiB, score = 0
测试数据 #33: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
测试数据 #34: RuntimeError, time = 31 ms, mem = 6416 KiB, score = 0
测试数据 #35: Accepted, time = 15 ms, mem = 6424 KiB, score = 10
测试数据 #36: RuntimeError, time = 15 ms, mem = 6420 KiB, score = 0
测试数据 #37: RuntimeError, time = 31 ms, mem = 6424 KiB, score = 0
测试数据 #38: RuntimeError, time = 31 ms, mem = 6420 KiB, score = 0
测试数据 #39: Accepted, time = 0 ms, mem = 6428 KiB, score = 10
TimeLimitExceeded, time = 1668 ms, mem = 6428 KiB, score = 220
同KMP
22个点
求大牛为何RTE

琉璃盏 LV 10 @ 8 年前

同感，好整齐的时间
laosb LV 4 @ 12 年前

夷，这么整齐的时间和内存很少见。
- 数据弱爆了 LV 6 @ 12 年前
  
  -！。。。。不是叫你关注这个
- zhengjiaqi LV 6 @ 11 年前
  
  同感少见

ID: 1005
难度: 8
分类: 字符串 | KMP 点击显示
标签: (无)
递交数: 6744
已通过: 637
通过率: 9%
被复制: 36
上传者: xiaomengxian

确定这道题标签没有错？

3 条评论

超长数字串

信息

状态

开发

支持

确定这道题标签没有错？

3 条评论

超长数字串

信息

状态

开发

支持

还没有账户？

登录