首页 > ACM题库 > HDU-杭电 > HDU 3410-Passing the Message-线性结构-[解题报告]HOJ
2014
03-23

HDU 3410-Passing the Message-线性结构-[解题报告]HOJ

Passing the Message

问题描述 :

What a sunny day! Let’s go picnic and have barbecue! Today, all kids in “Sun Flower” kindergarten are prepared to have an excursion. Before kicking off, teacher Liu tells them to stand in a row. Teacher Liu has an important message to announce, but she doesn’t want to tell them directly. She just wants the message to spread among the kids by one telling another. As you know, kids may not retell the message exactly the same as what they was told, so teacher Liu wants to see how many versions of message will come out at last. With the result, she can evaluate the communication skills of those kids.
Because all kids have different height, Teacher Liu set some message passing rules as below:

1.She tells the message to the tallest kid.

2.Every kid who gets the message must retell the message to his “left messenger” and “right messenger”.

3.A kid’s “left messenger” is the kid’s tallest “left follower”.

4.A kid’s “left follower” is another kid who is on his left, shorter than him, and can be seen by him. Of course, a kid may have more than one “left follower”.

5.When a kid looks left, he can only see as far as the nearest kid who is taller than him.

The definition of “right messenger” is similar to the definition of “left messenger” except all words “left” should be replaced by words “right”.

For example, suppose the height of all kids in the row is 4, 1, 6, 3, 5, 2 (in left to right order). In this situation , teacher Liu tells the message to the 3rd kid, then the 3rd kid passes the message to the 1st kid who is his “left messenger” and the 5th kid who is his “right messenger”, and then the 1st kid tells the 2nd kid as well as the 5th kid tells the 4th kid and the 6th kid.
Your task is just to figure out the message passing route.

输入:

The first line contains an integer T indicating the number of test cases, and then T test cases follows.
Each test case consists of two lines. The first line is an integer N (0< N <= 50000) which represents the number of kids. The second line lists the height of all kids, in left to right order. It is guaranteed that every kid’s height is unique and less than 2^31 � 1 .

输出:

The first line contains an integer T indicating the number of test cases, and then T test cases follows.
Each test case consists of two lines. The first line is an integer N (0< N <= 50000) which represents the number of kids. The second line lists the height of all kids, in left to right order. It is guaranteed that every kid’s height is unique and less than 2^31 � 1 .

样例输入:

2
5
5 2 4 3 1
5
2 1 4 3 5

样例输出:

Case 1:
0 3
0 0
2 4
0 5
0 0
Case 2:
0 2
0 0
1 4
0 0
3 0

题意:

  给出一个数组,问你对于第i个数,从最后一个比它大的数到它之间比它小的数中最大的那个数的下标,以及它右边到第一个比它大的数中比它小的数中最大的那一个数的下标<下标从1开始>。

  eg:5 2 4 3 1

    l    0 0 2 0 0        对5来说左边比它小的数没有,所以是0。对2来说左边比它小的数没有,所以是0。对4来说左边比它小的数是2,所以下标是2。

    r   3 0 4 5 0         对5来说右边比它小的数中最大的是4,是第3个,所以答案是3。对2来说右边比它小的数是1,但是4比2大,所以无法到达1,所以答案是0。对于4,右边比它小的数中最大一个3的下标是4,所以答案是4。

 

思路:

  单调队列。

  先从左向右维护一个单调队列,然后在维护过程中最后一个从队列中剔除掉的即右边比它小的数中最大的那一个。

  单调队列中的值是下标值。

  从右向左再维护一个单调队列就可以求出另一个值。

 

Tips:

  nothing..

Code: 

Passing the Message

#include <stdio.h>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int MAXN = 50010;
 
 int main()
 {
     freopen("in.txt", "r", stdin);
     int iCase, n, ic = 1;
     int arr[MAXN], que[MAXN];
     int rear, front;
     int l[MAXN], r[MAXN];
     bool flag;
     scanf("%d", &iCase);
     while (iCase--) {
         arr[0] = 0;
         memset(que, 0, sizeof(que));
 
         scanf("%d", &n);
         for (int i = 1; i <= n; ++i)
             scanf("%d", &arr[i]);
 
         front = 0, rear = -1;
         for (int i = 1; i <= n; ++i) {
             flag = false;
             while (front <= rear && arr[que[rear]] < arr[i]) {
                 flag = true;
                 rear--;
             }
             if (flag) l[i] = que[rear+1];
             else l[i] = 0;
             que[++rear] = i;
         }
 
         front = 0, rear = -1;
         for (int i = n; i >= 1; --i) {
             flag = false;
             while (front <= rear && arr[que[rear]] < arr[i]) {
                 flag = true;
                 rear--;
             }
             if (flag) r[i] = que[rear+1];
             else r[i] = 0;
             que[++rear] = i;
         }
 
         printf("Case %d:\n", ic++);
         for (int i = 1; i <= n; ++i) {
             printf("%d %d\n", l[i], r[i]);
         }
     }
     return 0;
 }

View Code

 

链接:http://acm.hdu.edu.cn/showproblem.php?pid=3410

参考:http://www.cnblogs.com/Griselda/archive/2013/07/26/3217105.html


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false