**1.題目解析可見《訓練指南》P198**
**2代碼:**
~~~
#include<cstdio>
#include<cstring>
#include<cmath>
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define N 100005
#define INF 1<<30
using namespace std;
int a[N];
int value[N],cnt[N],num[N],L[N],R[N];
int ST[N][20];
int n,q;
int k;
void make_ST()//對cnt[]預處理
{
for(int i=1;i<=k;i++)
{
ST[i][0]=cnt[i];
}
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;(i+(1<<j)-1)<=n;i++)
{
ST[i][j]=Max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
}
int Query(int l,int r)
{
if(l>r)
return 0;
else
{
int kk=floor(log2(r-l+1));
return Max(ST[l][kk],ST[r-(1<<kk)+1][kk]);
}
}
int main()
{
while(scanf("%d",&n)&&n)
{
scanf("%d",&q);
k=0;
value[0]=INF;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=value[k])
{
R[k]=i;
value[++k]=a[i];
L[k]=i-1;
cnt[k]=1;
num[i]=k;
}
else
{
cnt[k]++;
num[i]=num[i-1];
}
}
R[k]=n+1;
make_ST();
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
if(num[l]==num[r])
{
printf("%d\n",r-l+1);
}
else
{
int tmp=Max(R[num[l]]-l,r-L[num[r]]);
int ans=Max(tmp,Query(num[l]+1,num[r]-1));
printf("%d\n",ans);
}
}
}
return 0;
}
~~~
- 前言
- The 12th Zhejiang Provincial Collegiate Programming Contest - D
- 用鄰接表存儲n個頂點m條弧的有向圖
- hdu 5289 Assignment(給一個數組,求有多少個區間,滿足區間內的最大值和最小值之差小于k)
- hdu 1358 Period(給定一個字符串,求有多少個前綴(包括自己本身),它是由k(k&gt;2,并且盡量大)個循環節組成的)
- hdu 1806 Frequent values(給定一個非降序數組,求任意區間內出現次數最多的數的次數)
- poj 3264 Balanced Lineup(查詢區間最大值與最小值的差)
- HDU 1010 Tempter of the Bone(DFS+奇偶剪枝)
- HDU 1015 Safecracker(第一次用了搜索去遍歷超時,第二次用for循環可以了,思路一樣的)
- HDU 1016 Prime Ring Problem(DFS)
- HDU 1026 Ignatius and the Princess I(BFS+記錄路徑)
- HDU 1072 Nightmare(BFS)
- HDU 1237 簡單計算器(后綴式+棧)