题目链接:hdu 4749 Parade Show
题目大意:学校要举办一场典礼,要从n个学生中选若干支队伍来,每支队伍有m个人。然后现在将学生的身高划分成k个等级,接着按照学生的顺序给出学生的身高等级,再然后,给出m个人的队伍要求的相对高度。然后要求从n个中间挑选连续的m个人,满足相对高度即可组成一支队伍。问说最多可以组成多少支队伍。
解题思路:KMP算法的变形,只不过在判断相等的时候有点难办,因为它算的是相对高度,就是同一支队伍中,对应比自己高的个数,相等的个数,比自己矮的个数都要和要求的相等,所以要开一个cx,cy数组,将KMP中判断相等写成一个函数。
#include <stdio.h>
#include <string.h>
const int N = 1e5+5;
int n, m, k, next[N], x[N], y[N];
int cx[N][30], cy[N][30];
void init () {
int a;
memset(cx[0], 0, sizeof(cx[0]));
memset(cy[0], 0, sizeof(cy[0]));
for (int i = 1; i <= n; i++) {
memcpy(cx[i], cx[i-1], sizeof(cx[i-1]));
scanf("%d", &x[i]);
cx[i][x[i]]++;
}
for (int i = 1; i <= m; i++) {
memcpy(cy[i], cy[i-1], sizeof(cy[i-1]));
scanf("%d", &y[i]);
cy[i][y[i]]++;
}
}
bool judge (int p, int q, int (*a)[30], int (*b)[30], int tp, int tq) {
int s = 0;
for (int i = 1; i < tp; i++)
s += a[p][i];
for (int i = 1; i < tq; i++)
s -= (b[q][i] - b[q-p][i]);
return s == 0 && a[p][tp] == (b[q][tq] - b[q-p][tq]);
}
void getNext () {
int j = 0;
for (int i = 2; i <= m; i++) {
while (j > 0 && !judge (j+1, i, cy, cy, y[j+1], y[i]))
j = next[j];
if (judge (j+1, i, cy, cy, y[j+1], y[i]))
j++;
next[i] = j;
}
}
int KMP () {
int ans = 0;
getNext();
int j = 0;
for (int i = 1; i <= n; i++) {
while (j > 0 && !judge (j+1, i, cy, cx, y[j+1], x[i]))
j = next[j];
if (judge (j+1, i, cy, cx, y[j+1], x[i]))
j++;
if (j == m) {
ans++;
j = 0;
}
}
return ans;
}
int main () {
while (scanf("%d%d%d", &n, &m, &k) == 3) {
init ();
printf("%d\n", KMP());
}
return 0;
}
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码