HDU 4749 Parade Show(暴力水果)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4749

Problem Description

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?

Input

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);

Output

One integer, the maximal amount of well designed queues.

Sample Input

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

Sample Output

1

Source

2013 ACM/ICPC Asia Regional Nanjing Online

题意:

给出了一列数,再给出了一列参照的数列其每个数代表一个高度且须满足大小关系,求可以将所给的数列分割成多少个满足参照数列个数和高度的数列!

PS:

数据太水了,暴力过了! 正解貌似是KMP, 算了日后再补正解吧!

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 100017;
int a[maxn], b[maxn];

int main()
{
    int n, m, k;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&b[i]);
        }
        int cont = 0;
        for(int i = 0; i <= n-m; i++)
        {
            int tt = 0;
            for(int j = 0,l = i; l < m+i-1; l++,j++)
            {
                if((a[l]==a[l+1]&&b[j]==b[j+1]) || (a[l]>a[l+1]&&b[j]>b[j+1]) || (a[l]<a[l+1]&&b[j]<b[j+1]))
                {
                    tt++;
                }
                else
                    break;
            }
            if(tt == m-1)
            {
                cont++;
                i+=m-1;
            }
        }
        printf("%d\n",cont);
    }
    return 0;
}
时间: 10-19

HDU 4749 Parade Show(暴力水果)的相关文章

HDU 4499 Cannon (暴力搜索)

题意:在n*m的方格里有t个棋子,问最多能放多少个炮且每个炮不能互相攻击(炮吃炮) 炮吃炮:在同一行或同一列且中间有一颗棋子. #include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <queue> #include <math.h> #define M 50 #define LL long long using

HDU 4902 线段树||暴力

给定一个序列,两种操作 1:把一段变成x. 2:把一段每个数字,如果他大于x,就变成他和x的gcd,求变换完后,最后的序列. 线段树解法:用lazy标记下即可,优化方法还是很巧妙的, Accepted 4902 515MS 3308K 1941 B C++ #include "stdio.h" #include "string.h" struct node { int l,r,x;// 在叶子节点代表值,树节点代表成端更新的lazy操作. }data[400010]

HDU 4831 Scenic Popularity 暴力模拟

Scenic Popularity Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 340    Accepted Submission(s): 110 Problem Description 临近节日,度度熊们最近计划到室外游玩公园,公园内部包括了很多的旅游景点区和休息区,由于旅游景点很热门,导致景点区和休息区都聚集了很多人.所以度度熊

HDU 4961 Boring Sum 暴力

题意:对于所有的A[I],同时找到左边和右边离它最近且是它的倍数的数相乘最后加起来求和. 解题思路:n*sqrt(n)的算法,开始以为过不了,wa了两发因为lld I64d对拍一个小时发现一个小时前交的代码没错只是没变I64d,..具体思路是枚举每个a[i]的因子,找离它最近的那个更新,如果已经没更新就不用更新了.用两个辅助数组记录最近的就行. 解题代码: 1 // File Name: 1002.cpp 2 // Author: darkdream 3 // Created Time: 201

HDU - 2089 不要62 (暴力或数位DP)

Description 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer). 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众. 不吉利的数字为所有含有4或62的号码.例如: 62315 73418 88914 都属于不吉利号码.但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列. 你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新

hdu 4737 二分或暴力

http://acm.hdu.edu.cn/showproblem.php?pid=4737 Problem Description There are n numbers in a array, as a0, a1 ... , an-1, and another number m. We define a function f(i, j) = ai|ai+1|ai+2| ... | aj . Where "|" is the bit-OR operation. (i <= j)

hdu 4775 Infinite Go(暴力)

题目链接:hdu 4775 Infinite Go 题目大意:两个人下围棋,总共走了n步,黑棋和白棋交替走,如果一片棋的上下左右被封死,那么该片棋子就会被吃掉,问说最后黑白棋各剩多少个. 解题思路:比较恶心的模拟题,相邻相同色的棋子要用并查集连接,并且要记录每片棋子还剩的空格数,如果空格数为0的话说明该片棋子被其他颜色围住,则要剔除掉,不且将相邻的位置不同色的棋空格数加1.主要是细节上的问题. 样例 8 7 5 5 4 5 3 5 3 4 4 4 3 3 4 6 18 1 3 1 4 2 2 1

Hdu 3687 National Day Parade(暴力)

题目地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=3687 思路:暴力,枚举每列(矩形开始的列),将同一行的人按列从小到大排序,则每个人的移动距离为abs(g[j][k]-i-k)(第j行的第k个人移动到合适位置距离),枚举累加取最最小值即可. #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include&

hdu 2615 Division(暴力)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2615 题解:挺简单的暴力枚举,小小的分治主要是看没人写题解就稍微写一下 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll a[123] , ans , sum[123