題目鏈接：http://poj.org/problem?id=3368

題目大意：

給出一個n個數(shù)長度的串。 m個詢問

求出給定范圍內(nèi)的最大連續(xù)字符串的長度

方法：

RMQ模板， 記錄每一個位置的數(shù)連續(xù)的次數(shù)。用RMQ求出每一個區(qū)間的最大連續(xù)字符的長度值

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm>using namespace std; const int maxn = 100010; int A[maxn]; int Max[maxn][20]; int f[maxn];void RMQ(int n) {int k = (int )(log(n) / log(2));for(int j=1; j<=k; j++)for(int i=1; i<=n; i++)if(i + (1<<j) - 1 <= n){Max[i][j] = max(Max[i][j-1], Max[i+(1<<(j-1))][j-1]);} }int main() {int n, q;while(~scanf("%d",&n) && n){scanf("%d",&q);memset(f, 0, sizeof(f));for(int i=1; i<=n ;i++){scanf("%d", &A[i]);if(A[i] == A[i-1] && i > 1)f[i] = f[i-1] + 1;else {f[i]++;}Max[i][0] = f[i];}RMQ(n);//for(int i=1; i<=n; i++)// printf("%d ",f[i]);while(q--){int a, b;scanf("%d%d",&a,&b);int t = a;while(t <= b && A[t] == A[t-1])t++;int k = (int )(log(b-t+1)/log(2));int ans;if(t > b)ans = 0;else ans = max(Max[t][k], Max[b-(1<<k)+1][k]);printf("%d\n", max(ans,t-a));}}return 0; }

總結

以上是生活随笔為你收集整理的POJ 3368 Frequent values (RMQ)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。