首页 > 代码库 > UVA 11235 (游程编码+ST算法)

UVA 11235 (游程编码+ST算法)

2024-07-25 11:59:58   216人阅读

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23846

题目大意：给定一个升序序列，有q次询问，每次询问(L,R)出现最多的值的次数。

解题思路：

非常麻烦的题目。尽管一眼就能看出来是个RMQ。

关键在于如何转化为RMQ。

首先对序列进行游程编码，压缩成pos段。

编码的同时用num[i]记录当前点在段中编号，LB[i]记录在当前段的左边界，更新code[pos]（当前段的容量）

编码之后O(n)扫一遍，用num[i]、code[num[i]]和LB[i]搞出在当前段的右边界RB[i]。

则Q(L,R)的时候有以下几种情况：

①如果num[L]=num[R]，则说明L,R在同一段，ans=R-L+1。

②如果num[L]≠num[R]，则说明L,R不在同一段，

  则整个(L,R)被划分成三段：(L,RB[L]-L+1)这些元素在同一个段中，（num[L]+1,num[R]-1)前提是num[L]+1<=num[R]-1，（R-LB[R]+1,R)这些元素在同一个段中。

  由于左右段都在同一段中，max元素个数即可。中间这段混合了多个完整的段，直接st即可，注意st初始化的是段的容量。

 

#include "cstdio"#include "cstring"#include "iostream"using namespace std;#define maxn 100000#define maxp 20int RMQ[maxn][maxp],n,q,w,l,r,code[maxn],num[maxn],LB[maxn],RB[maxn];template <class T>inline bool read(T &ret){    char c;    int sgn;    if(c=getchar(),c==EOF) return 0; //EOF    while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar();    sgn=(c==‘-‘)?-1:1;    ret=(c==‘-‘)?0:(c-‘0‘);    while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);    ret*=sgn;    return 1;}void ST(){    for(int i=1;i<=n;i++) RMQ[i][0]=code[i];    for(int j=1;(1<<j)<=n;j++)        for(int i=1;i+(1<<j)-1<=n;i++)           RMQ[i][j]=max(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);}int Query(int L,int R){    int k=0;    while((1<<(k+1))<=R-L+1) k++;    return max(RMQ[L][k],RMQ[R-(1<<k)+1][k]);}int Q(int L,int R){    if(num[L]==num[R]) return R-L+1;    else    {        int a=RB[L]-L+1;        int b=0;        if(num[L]+1<=num[R]-1) b=Query(num[L]+1,num[R]-1);        int c=R-LB[R]+1;        return max(max(a,b),c);    }}int main(){    while(read(n)&&read(q)&&n)    {        memset(RMQ,128,sizeof(RMQ));        memset(code,0,sizeof(code));        int pos=0,last=1<<28;        for(int i=1;i<=n;i++)        {             read(w);             if(w==last)             {                 LB[i]=LB[i-1];                 code[pos]++;//当前段容量             }             else             {                 LB[i]=i; //左边界                 code[++pos]=1;                 last=w;             }             num[i]=pos; //当前点段编号        }        for(int i=1;i<=n;i++) RB[i]=LB[i]+code[num[i]]-1; //右边界        n=pos;        ST();        for(int i=1;i<=q;i++)        {            read(l);read(r);            printf("%d\n",Q(l,r));        }    }}

 

2809497

neopenx

UVA 11235

Accepted

0 KB

182 ms

C++ 4.8.2

1827 B

2014-10-03 18:18:58

 

UVA 11235 (游程编码+ST算法)


联系
我们