首页 > ACM题库 > HDU-杭电 > HDU 3603-Coach Yehr’s punishment[解题报告]HOJ
2014
11-27

HDU 3603-Coach Yehr’s punishment[解题报告]HOJ

Coach Yehr’s punishment

问题描述 :

During the Mult-University Trainging,Coach Yehr asks all the ACM teammates to jog at 6:30AM.But 6:30 is too early,there are always somebody might be late.Coach Yehr likes AC sequence very much,the AC sequence is a number sequence with all the elements different.A sequence (S1 ,S2 ,S3 ……Sn ) is a AC sequence if S1 ,S2 ,S3 ……Sn are all different. There are N teammates,the time(in second time) every teammate’arrival make a number sequence with length N. In order to punish the laters,Coach Yehr give them a puzzle,Coach Yehr choose a subsequence from Sa to Sb ,the laters must tell Coach Yehr the longest length of AC sequence in the subsequence as soon as possible.

输入:

There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.

输出:

There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.

样例输入:

8
3 2 5 6 8 3 2 6
2
2 4
1 8
6
5 3 1 2 3 4
1 6
3 3

样例输出:

3
5
4
2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define maxn 300001
#define eps 1e-6
using namespace std;
int n;
int m;
int len[maxn];
int vis[maxn];
int mx[maxn][24];
int pre[maxn];

int search(int l,int r)
{
 int t=l;
 while(l<r)
 {
 int mid=l+r>>1;
 if(pre[mid]<t)
 {
 l=mid+1;
 }
 else
 {
 r=mid;
 }
 }
 return l;
}

void init_rmq()
{
 int i,j;
 int k=(int)(log2(n)+eps);
 for(i=1; i<=n; i++)
 {
 mx[i][0]=len[i];
 }
 for(i=1; i<=k; i++)
 {
 for(j=1; j<=n; j++)
 {
 mx[j][i]=mx[j][i-1];
 if(j+(1<<(i-1))<=n)
 {
 mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
 }
 }
 }
}

int rmq(int l,int r)
{
 int k=(int)(log2(r-l+1)+eps);
 return max(mx[l][k],mx[r-(1<<k)+1][k]);
}

int main()
{
 //freopen("input.txt","r",stdin);
 int i,j;
 while(scanf("%d",&n)!=EOF)
 {
 memset(len,0,sizeof(len));
 memset(vis,-1,sizeof(vis));
 memset(pre,-1,sizeof(pre));
 for(i=1; i<=n; i++)
 {
 int temp;
 scanf("%d",&temp);
 if(vis[temp]==-1)
 {
 pre[i]=1;
 }
 else
 {
 pre[i]=vis[temp]+1;
 }
 pre[i]=max(pre[i],pre[i-1]);
 len[i]=i-pre[i]+1;
 vis[temp]=i;
 }
 init_rmq();
 scanf("%d",&m);
 while(m--)
 {
 int l,r;
 scanf("%d %d",&l,&r);
 if(l>r) swap(l,r);
 int t=search(l,r);
 if(t==r)
 {
 printf("%d\n",t-l+1);
 }
 else
 {
 printf("%d\n",max(t-l,rmq(t,r)));
 }
 }
 }
 return 0;
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  4. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”