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。

相关文章

Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
计算数组的斜率，偏移，R2

计算数组的斜率，偏移，R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou
阅读更多...
C# double[] 和Matlab数组MWArray[]转换

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };
阅读更多...
PHP7扩展开发之数组处理

PHP7扩展开发之数组处理

前言 这次，我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下： <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2