hdu4691 Front compression ——暴力 || 后缀数组

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

走吧,小胖!

上一篇:Omu.AwesomeMvc.dll 和Omu.ValueInjecter.dll 介绍


下一篇:python学习道路(day12note)(mysql操作,python链接mysql,redis)