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;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
char a[111111], b[11111];
//#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);
        int l, r, pl, pr, tmp = 0;
        LL ans = 0, bns = 0;
        scanf("%d%d", &pl, &pr);
        bns += (pr - pl + 1);
        ans += (pr - pl + 1 + 2);
        for (int so = 0; so < n-1; ++so)
        {
            scanf("%d%d", &l, &r);
            bns += (r - l + 1);
            tmp = 0; 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 += 2;
            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;
    }
    return 0;
}

标准做法据说是后缀数组+RMQ，留坑，今天研究一下再说。

不过还是有个问题，为什么上面这个程序里面62行是对的，61行输出就不对呢？明明是一样的啊，还好，我用59,60两行检验了一下，没浪费太多时间，只是现在还是不知道为什么，难道是输出格式错了？？

o(╯□╰)o

走吧，小胖！