[分块] 查单词 (洛谷P2412)

此题显然可以用分块做。我们只需要用分块维护字典序最大的字符串的下标即可。
本人刚学分块,代码可能有不足之处,请见谅。
代码:

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>

// 计算下标所在的块
#define calc(a) (ceil((double)a/size)>tot?tot:ceil((double)a/size))

using namespace std;
int n, m, tot, size, l[225], r[225], mx[225], x, y;
char o[50001][15];
char s[50001][15];

// 处理询问
int query() {
    // lid、rid分别是左端点和右端点所在的块的编号,ret是答案
    int lid = calc(x), rid = calc(y), ret; 

    // 分情况处理
    if (lid == rid) {
        ret = x;
        for ( int i = x+1; i <= y; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;
    } else {
        ret = x;

        // 暴力处理左端
        for ( int i = x+1; i <= r[lid]; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;

        // 中间部分
        for ( int i = lid+1; i < rid; ++ i )
            if (strcmp(s[mx[i]], s[ret])>=0) // 用strcmp比较字典序
                ret = mx[i];

        // 暴力处理右端
        for ( int i = l[rid]; i <= y; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;
    }
    return ret;
}

// 转换大小写
void convert(char* k) { 
    int len = strlen(k);
    for ( int i = 0; i < len; ++ i )
        k[i] = tolower(k[i]);
}

int main() {
    scanf("%d%d", &n, &m); // 输入数据较大,使用cin输入会TLE

    // 求出块的大小和块的数量
    tot = size = sqrt(n);

    // 输入字符串
    for ( register int i = 1; i <= n; ++ i ) {
        scanf("%s", s[i]);
        memcpy(o[i], s[i], sizeof(s[i])); // 用o数组保存原字符串,s数组保存转换小写后的字符串
        convert(s[i]); // 转换大小写
    }

    // 保存块的左右端点
    for ( register int i = 1; i <= tot; ++ i )
        l[i] = (i-1)*size+1,
        r[i] = i*size;

    // 处理末端多出来的一块
    if (r[tot] < n) {
        ++tot;
        l[tot] = r[tot-1]+1;
        r[tot] = n;
    }

    // 预处理
    for ( register int i = 1; i <= tot; ++ i ) {
        mx[i] = l[i];
        for ( register int j = l[i]+1; j <= r[i]; ++ j )
            if (strcmp(s[j], s[mx[i]])>=0) // 处理块内字典序最大的字符串
                mx[i] = j;
    }

    // 回答询问
    while (m--) {
        scanf("%d%d", &x, &y); // 输入区间
        puts(o[query()]); // 输出答案
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注