首页 > 代码库 > UVA 11235 (游程编码+ST算法)
UVA 11235 (游程编码+ST算法)
题目链接: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算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。