- 超长数字串
- 2013-03-05 09:29:43 @
测试数据 #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大神说了不可以的
3 条评论
-
mockingjay LV 7 @ 2016-10-24 22:34:42
#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 -
2016-08-13 21:54:32@
同感,好整齐的时间
-
2013-03-05 21:03:21@
夷,这么整齐的时间和内存很少见。
- 1