首页 > ACM题库 > HDU-杭电 > HDU 4749-Parade Show-KMP-[解题报告]HOJ
2015
09-17

HDU 4749-Parade Show-KMP-[解题报告]HOJ

Parade Show

问题描述 :

Area

  2013 is the 60 anniversary of Nanjing University of Science and Technology, and today happens to be the anniversary date. On this happy festival, school authority hopes that the new students to be trained for the parade show. You should plan a better solution to arrange the students by choosing some queues from them preparing the parade show. (one student only in one queue or not be chosen)
  Every student has its own number, from 1 to n. (1<=n<=10^5), and they are standing from 1 to n in the increasing order the same with their number order. According to requirement of school authority, every queue is consisted of exactly m students. Because students who stand adjacent in training are assigned consecutive number, for better arrangement, you will choose in students with in consecutive numbers. When you choose these m students, you will rearrange their numbers from 1 to m, in the same order with their initial one.
  If we divide our students’ heights into k (1<=k<=25) level, experience says that there will exist an best viewing module, represented by an array a[]. a[i] (1<=i<=m)stands for the student’s height with number i. In fact, inside a queue, for every number pair i, j (1<=i,j<=m), if the relative bigger or smaller or equal to relationship between the height of student number i and the height of student number j is the same with that between a[i] and a[j], then the queue is well designed. Given n students’ height array x[] (1<=x[i]<=k), and the best viewing module array a[], how many well designed queues can we make at most?

输入:

Multiple cases, end with EOF.
First line, 3 integers, n (1<=n<=10^5) m (1<=m<=n) k(1<=k<=25),
Second line, n students’ height array x[] (1<=x[i]<=k,1<=i<=n);
Third line, m integers, best viewing module array a[] (1<=a[i]<=k,1<=i<=m);

输出:

Multiple cases, end with EOF.
First line, 3 integers, n (1<=n<=10^5) m (1<=m<=n) k(1<=k<=25),
Second line, n students’ height array x[] (1<=x[i]<=k,1<=i<=n);
Third line, m integers, best viewing module array a[] (1<=a[i]<=k,1<=i<=m);

样例输入:

10 5 10
2 4 2 4 2 4 2 4 2 4
1 2 1 2 1

样例输出:

1

HDU4749 一道稍微饶了点弯子的KMP 题目。。。

给定一个模式串,要求匹配的字符串中字符的两两大小关系与模式串相同

比如:

模式串 1 3 5 2 4 6

匹配串 9 12 16 10 14 19

就是一组合法的匹配。

其实没什么复杂的。。 顺序处理模式串当中的每一个字符,处理出:

(如果该字符之前出现过)在其前面等于该字符的字符位置 

(如果该字符没出现过)或者是大于该字符的最小字符,以及小于该字符的最大字符

这样就可以像比较一般的字符串一样去比较题目描述的字符串了。。之后就是一个普通的KMP

———————————————————————————————————————————————————

其实这题目的数据比较水 不用KMP 暴搞也能过… _(:3J L)_

上代码:

#include<cstdio>
#include<cstring>
using namespace std;

int n,m,k;
int cp[100005][2];
int app[30];
int s1[100005],s2[100005];
int nxt[100005];

void init1(){
	for(int i=0;i<=k;i++) app[i]=-1;
	for(int i=0;i<m;i++){
		cp[i][0]=-1;
		for(int j=s2[i];j>0;j--)
			if(app[j]>=0){
				cp[i][0]=app[j];
				break;
			}
		cp[i][1]=-1;
		for(int j=s2[i];j<=k;j++)
			if(app[j]>=0){
				cp[i][1]=app[j];
				break;
			}
		app[s2[i]]=i;
	}
}

bool fit(int *s,int p){
	int v=*s;
	s-=p;
	if(cp[p][0]<0 && cp[p][1]<0) return 1;
	if(cp[p][0]<0) return v<s[cp[p][1]];
	if(cp[p][1]<0) return v>s[cp[p][0]];
	if(cp[p][0]==cp[p][1])
		return s[p]==s[cp[p][0]];
	return s[p]<s[cp[p][1]] && s[p]>s[cp[p][0]];
}

void init2(){
	nxt[0]=-1;
	int i=0,j=-1;
	while(i<m){
		if(j==-1 || fit(&s2[i],j)) nxt[++i]=++j;
		else j=nxt[j];
	}
}

int main(){
	while(scanf("%d%d%d",&n,&m,&k)!=EOF){
		for(int i=0;i<n;i++) scanf("%d",&s1[i]);
		for(int i=0;i<m;i++) scanf("%d",&s2[i]);
		init1();
		init2();
		int i=0,j=0;
		int ans=0;
		while(i<n){
			j=0;
			while(i<n && j<m){
				if(j==-1 || fit(&s1[i],j)) ++i,++j;
				else j=nxt[j];
			}
			if(j==m) ++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

参考:http://blog.csdn.net/neko_apocalypse/article/details/11952681