link:http://acm.hdu.edu.cn/showproblem.php?pid=4691
暴力,数据明显太水了吧,n=10^5, O(n^2)的复杂度哎喂。想让大家暴力写直接让n=1000不就得了么,这算什么。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <algorithm> #include <queue> #include <deque> #include <queue> #include <list> #include <map> #include <set> #include <vector> #include <utility> #include <functional> #include <fstream> #include <iomanip> #include <sstream> #include <numeric> #include <cassert> #include <ctime> #include <iterator> const int INF = 0x3f3f3f3f; ][] = {{-,},{,},{,-},{,},{-,-},{-,},{,-},{,}}; using namespace std; ], b[]; //#define LL long long #define LL __int64 int main(void) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin ); #endif // ONLINE_JUDGE while (~scanf("%s", a)) { int n; scanf("%d", &n); ; LL ans = , bns = ; scanf("%d%d", &pl, &pr); bns += (pr - pl + ); ans += (pr - pl + + ); ; so < n-; ++so) { scanf("%d%d", &l, &r); bns += (r - l + ); tmp = ; int pos = pl, i; for (i = l; i < r && pos < pr; ++i) { if (a[i] == a[pos]) tmp++, pos++; else break; } sprintf(b, "%d", tmp); ans += strlen(b); ans += (r-l-(i-l)); ans += ; pl =l, pr = r; } // printf("%lld %lld\n", bns, ans); // printf("bns = %lld\n",bns); // printf("ans = %lld\n",ans); // printf("%lld %lld\n", bns, ans); cout << bns << " " << ans << endl; } ; }
标准做法据说是后缀数组+RMQ,留坑,今天研究一下再说。
不过还是有个问题,为什么上面这个程序里面62行是对的,61行输出就不对呢?明明是一样的啊,还好,我用59,60两行检验了一下,没浪费太多时间,只是现在还是不知道为什么,难道是输出格式错了??
o(╯□╰)o
走吧,小胖!