bupt204nbsp;北邮多校J题nbsp;nbsp;后最数组+LC…

2024-04-01 17:38
文章标签 数组 多校 lc 北邮 nbsp bupt204nbsp

本文主要是介绍bupt204nbsp;北邮多校J题nbsp;nbsp;后最数组+LC…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题报告

题目 ：http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=204

算法 ：利用后缀数组求出以每个点为中心的最长回文长度，然后利用二分长度和RMQ搞

思路 ：利用后缀数组求出以每个点为中心的最长回文长度，但是偶数和奇数的情况要注意一下，我没想到好方法，只是偶数的维护了一次RMQ，奇数的又维护了一次RMQ。假设求区间[l,r]内的最长回文子串，我们枚举回文串一半的长度mid（奇数原长2×mid + 1）然后判一下在区间[l + mid, r – mid] 内有没有一个以某个点为中心长度大于等于2×mid+1的点，有的话说明这个mid可以被满足，同时我们还要考虑在区间[l + mid, r – mid + 1]中有没有一个长度大于等于2×mid的偶数回文串，这时我们记录最大的长度。由于北邮内存卡的较紧，奇数和偶数是分开处理的。

要注意的是枚举l和r是，奇数情况l从0开始，偶数情况l从1开始。

后缀数组最威武！

 

提交情况 ：MLE，TLE， wa， 3天， AC 一次

 

AC code：

 

 

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <map>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

 

typedef int I64;

typedef unsigned int uI64;

typedef double real;

const double LE =log(2.0);

 

const uI64 B[32] = {1, 2, 4, 8, 16,32, 64, 128, 256, 512, 1024, 2048,4096, 8192, 16384, 32768, 65536, 131072,262144, 524288, 1048576, 2097152, 4194304, 8388608,16777216, 33554432, 67108864, 134217728, 268435456,536870912, 1073741824, 2147483648};

#define MAX(a, b) ((a) > (b) ?(a) : (b))

#define MIN(a, b) ((a) < (b) ?(a) : (b))

#define mem(a, b) memset(a, b, sizeof(a))

#define fup(i, a, b) for(i = a; i < b; ++i)

#define fdn(i, a, b) for(i = a; i > b; --i)

#define INF 210000000

 

I64 Gcd(I64 a, I64 b){return b ? Gcd(b, a% b) : a;}

I64 Lcm(I64 a, I64 b){return a / Gcd(a, b)* b; }

 

#define MAXL 400010

#define MAXCHAR 300

#define MAXJ 20

 

char str[MAXL];

I64 Rank[MAXL], ST_min[MAXJ][MAXL],ST_max[MAXJ][MAXL / 2], ANS[MAXL / 2],ql[MAXL], qr[MAXL / 2];

I64 L;

 

bool cmp(I64 *tp, I64 a, I64 b, I64l){

    return tp[a] == tp[b] && tp[a+ l] == tp[b + l];

}

 

void Get_SA(){

    I64 len = L +1, i, m = MAXCHAR, *t, *rank =Rank, *SA = ql, *buc = ST_min[2],*y = ST_min[4], *nrank = ST_min[6];

    fup(i, 0, m) buc[i]= 0;

    fup(i, 0, len) buc[rank[i]= str[i]] ++;

    fup(i, 0, m) buc[i +1] += buc[i];

    fdn(i, len  - 1, -1) SA[--buc[rank[i]]]= i;

    for(I64 p= 1, k = 1; p < len;k <<= 1, m = p){

       for(p =0, i = len - k; i < len;++ i) y[p ++] = i;

       fup(i, 0, len) if(SA[i] >= k) y[p ++]= SA[i] - k;

       fup(i, 0, m) buc[i]= 0;

       fup(i, 0, len) buc[nrank[i]= rank[y[i]]] ++;

       fup(i, 0, m) buc[i +1] += buc[i];

       fdn(i, len - 1, -1)SA[--buc[nrank[i]]] = y[i];

       for(t =y, y = rank, rank = t, rank[SA[0]]= 0, i = p = 1; i <len; ++i)

           rank[SA[i]] = cmp(y,SA[i - 1], SA[i], k) ? p -1 : p ++;

    }

}

 

void Get_height(){

    I64 len = L, i,j, k = 0, *SA = ql, *height= ST_min[0];

    fup(i, 1, len + 1)Rank[SA[i]] = i;

    for(i =0; i < len; height[Rank[i++]] = k)

       for(k ?k -- : 0, j = SA[Rank[i] -1]; str[i + k] == str[j + k];k ++);

}

 

void Built_ST_min(){

    for(I64 j= 1; B[j] <= L; ++ j)

       for(I64 i= 0; i <= L - B[j] +1; i ++)

           ST_min[j][i] = MIN(ST_min[j- 1][i], ST_min[j - 1][i + B[j- 1]]);

}

 

I64 find_ST_min(I64 sux1, I64sux2){

    I64 x = Rank[sux1],y = Rank[sux2];

    if(x >y) swap(x, y);

    I64 len = (I64)(log((double)y - x) / LE);

    return MIN(ST_min[len][x + 1], ST_min[len][y- B[len] + 1]);

}

 

void Built_ST_max(I64 cnel){

    I64 i, j;

    fup(i, 0, cnel){

       j = 2 * cnel- i;

       ST_max[0][i] = find_ST_min(i,j) * 2 - 1;

    }

    for(j =1; B[j] < cnel; ++ j)

       for(i =0; i < cnel - B[j] + 1;++ i){

           ST_max[j][i] = MAX(ST_max[j- 1][i], ST_max[j - 1][i + B[j- 1]]);

       }

}

 

void Built_ST_max1(I64 cnel){

    I64 i, j;

    fup(i, 0, cnel){

       j = 2 * cnel- i + 1;

       ST_max[0][i] = find_ST_min(i,j) * 2;

    }

    for(j =1; B[j] < cnel; ++ j)

       for(i =0; i < cnel - B[j] + 1;++ i){

           ST_max[j][i] = MAX(ST_max[j- 1][i], ST_max[j - 1][i + B[j- 1]]);

       }

}

 

I64 find_ST_max(I64 x, I64y){

    if(x >y) return 0;

    I64 len = (I64)(log((double)y - x + 1) /LE);

    return MAX(ST_max[len][x], ST_max[len][y - B[len]+ 1]);

}

 

 

I64 exist(I64 x, I64y, I64 len){

    if(find_ST_max(x+ len, y - len) >= 2 *len + 1) return 2* len + 1;

    return 0;

}

 

I64 slove(I64 x, I64y, I64 cnel){

    I64 l = 0, r= (y - x + 1) / 2, mid,ans = 0, t;

    while(l <=r){

       mid = l + (r- l) / 2;

       if(t =exist(x, y, mid)){

           ans = t;

           l = mid +1;

       }else r= mid - 1;

    }

    return ans;

}

 

I64 exist2(I64 x, I64y, I64 len){

    if(find_ST_max(x+ len, y - len + 1) >=2 * len) return 2* len;

    return 0;

}

 

I64 slove2(I64 x, I64y, I64 cnel){

    I64 l = 1, r= (y - x + 1) / 2, mid,ans = 0, t;

    while(l <=r){

       mid = l + (r- l) / 2;

       if(t =exist2(x, y, mid)){

           ans = t;

           l = mid +1;

       }else r= mid - 1;

    }

    return ans;

}

 

int main(){

    I64 CASE, i, len, x,y, m;

    scanf("%d",&CASE);

    while(CASE--){

       scanf("%s",str);

       len = strlen(str);

       L = 2 * len +1;

       str[len] = 1;

       fup(i, 1, len + 1)

           str[len + i] =str[len - i];

       str[L] = 0;

       Get_SA();

       Get_height();

       Built_ST_min();

       Built_ST_max(len);

       scanf("%d",&m);

       fup(i, 0, m){

           scanf("%d %d", &ql[i], &qr[i]);

           ANS[i] = slove(ql[i]- 1, qr[i] - 1, len);

       }

       Built_ST_max1(len);

       fup(i, 0, m){

           if(ANS[i] < (x = slove2(ql[i] - 1,qr[i] - 1, len))) ANS[i] = x;

           printf("%d\n",ANS[i]);

       }

    }

    return 0;

}

 

 //在hdu没过

这篇关于bupt204nbsp;北邮多校J题nbsp;nbsp;后最数组+LC…的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/867747。

相关文章

MySQL JSON 查询中的对象与数组技巧及查询示例

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA
阅读更多...
JAVA数组中五种常见排序方法整理汇总

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言：法一：Arrays.sort()法二：冒泡排序法三：选择排序法四：反转排序法五：直接插入排序前言：几种常用的Java数组排序
阅读更多...
Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
C++原地删除有序数组重复项的N种方法

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体：最多保留两次五、分析和代码实现5.1、问题分析5.
阅读更多...
Java中数组转换为列表的两种实现方式(超简单)

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架（Arrays.asList）1.1 示例代码1.
阅读更多...
C++一个数组赋值给另一个数组方式

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法：使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2