HDU 4749 Parade Show(暴力水果)
HDU 暴力 show 水果
2023-09-11 14:20:43 时间
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4749
Problem Description
![](http://acm.hdu.edu.cn/data/images/C479-1002-1.jpg)
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);
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
题意:
给出了一列数,再给出了一列參照的数列其每一个数代表一个高度且须满足大小关系。求能够将所给的数列切割成多少个满足參照数列个数和高度的数列!
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; }
相关文章
- hdu 1814 字典序最小的2sat(暴力深搜)
- hdu 1171 Big Event in HDU(01背包)
- [ACM] hdu 1035 Robot Motion (模拟或DFS)
- HDU 2489 Minimal Ratio Tree
- HDU 4778 Gems Fight!
- HDU 1404 Digital Deletions (暴力博弈)
- HDU 6055 Regular polygon (暴力)
- HDU 3687 National Day Parade (暴力)
- HDU 5443 The Water Problem (水题,暴力)
- HDU 5706 GirlCat (DFS,暴力)
- HDU 1718 Rank (排序)
- HDU 2161 Primes (素数筛选法)
- 【HDU 5832】A water problem(大数取模)
- 【HDU 5839】Special Tetrahedron(计算几何)
- HDU ACM 1073 Online Judge ->字符串水题
- 亲串 (hdu 2203 KMP)
- hdu 1171 Big Event in HDU (01背包, 母函数)
- hdu 1863 畅通工程 (并查集 、 kruskal)