首页 > ACM题库 > HDU-杭电 > HDU 3914-Super Mario-排序-[解题报告]HOJ
2015
04-14

HDU 3914-Super Mario-排序-[解题报告]HOJ

Super Mario

问题描述 :

The Mario series is a series of highly popular and acclaimed video games by Nintendo, featuring Nintendo’s mascot Mario and, in many games, his brother Luigi and his best friend Yoshi. Gameplay in the series often centers around jumping on and defeating enemies. The games usually feature simple plots; the most common theme is that of Bowser, the primary antagonist, kidnapping Princess Peach, whom Mario saves. Despite the plots usually being very simple, the Mario role-playing games tend to have deeper plots, often involving enemies other than Bowser (many of which involve Bowser actually teaming up with Mario), with aspirations for world domination. Mario has been featured in 200 games, and the series has sold over 200 million copies total, making it the best-selling video game series of all time.
SUFFIX

Today,Mario comes to a forest,whick has many apple trees.These trees are special,the apples are grown in the nodes of the tree,whick is shown as follow.
SUFFIX

Numbers in the nodes indicate the amount of apples which are also in this node. The root of a tree is also considered as a node too.
  There are many trees in this forest, and some trees are connect by one-way road.
SUFFIX

Mario is start at a root, and he can jump along the branches up or down. Before each jump, he has to eat an apple, and after he eat an apple he have to jump up or down. Mario can walk along the roads too. He can walk along a road with at most an apple, or without any apple. These walks need not any apples. He can finish his journey at any root. All the nodes, including normal node and root node, are numbered together from 1 to M.
  How many apples is Mario able to eat at most?

输入:

Multiple cases, you need process to EOF.
  First line contains N, M and S, where N indicates the number of roots, M indicates the number of nodes, and S indicates the start root’s number. 0< N<M <= 20000, S is in the range of [1, M].

  Every next N lines contains “ID T A1 … AT”, where ID indicates a node-number of root. T indicates the number of roots ID connect to, and A1 to AT is the node-number of these T roots. ID is in the range of [1, M]; T is in the range of [0, M]; A1 to AT is in the range of [1, N]. Integers in every line are split by single space.

  Next M lines describe the M nodes. The i th line describe the i th node, and is formatted as: “AppleAmouts T B1 … BT”. Where AppleAmouts indicates the amount of apple in this node, T indicates the number of nodes this node connect with by branches, and B1 to BT indicate the number of these T nodes. AppleAmounts is in the range of [0, 1000]; T is in the range of [0, M-1]; B1 to BT is in the range of [1,M]. Integers in a line are split by a single space.

输出:

Multiple cases, you need process to EOF.
  First line contains N, M and S, where N indicates the number of roots, M indicates the number of nodes, and S indicates the start root’s number. 0< N<M <= 20000, S is in the range of [1, M].

  Every next N lines contains “ID T A1 … AT”, where ID indicates a node-number of root. T indicates the number of roots ID connect to, and A1 to AT is the node-number of these T roots. ID is in the range of [1, M]; T is in the range of [0, M]; A1 to AT is in the range of [1, N]. Integers in every line are split by single space.

  Next M lines describe the M nodes. The i th line describe the i th node, and is formatted as: “AppleAmouts T B1 … BT”. Where AppleAmouts indicates the amount of apple in this node, T indicates the number of nodes this node connect with by branches, and B1 to BT indicate the number of these T nodes. AppleAmounts is in the range of [0, 1000]; T is in the range of [0, M-1]; B1 to BT is in the range of [1,M]. Integers in a line are split by a single space.

样例输入:

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

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

样例输出:

2
6
Hint
SUFFIX

http://acm.hdu.edu.cn/showproblem.php?pid=4417

思路:线段树+二分裸奔~~~

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100005;
int as[23][maxn*4];
int n,m;
void build(int rt,int l,int r,int d)
{
    int md=(l+r)>>1;
    for(int i = l; i <= r; ++ i)//保存rt节点下所有的叶子节点
        as[d][i]=as[d-1][i];
    if(l==r)return;
    build(rt<<1,l,md,d+1);
    build(rt<<1|1,md+1,r,d+1);
    sort(as[d]+l,as[d]+r+1);//给rt节点下的叶子节点排序
}
int bitser(int a,int b,int d,int v)//二分查找v值在区间[a,b]的位置
{
    int l = a,r = b,md;
    while(l < r){
        md = (l + r) >> 1;
        if(as[d][md]>v)r = md;
        else l = md + 1;
    }
    if(as[d][l]>v)--l;
    return l;
}
int tot;
void query(int rt,int l,int r,int L,int R,int v,int d)
{
    int md = (l + r) >> 1;
    if(L<=l && r<=R){
        int k = bitser(l,r,d,v);//k为在区间[l,r]上<=v的个数
        tot += k - l + 1;
        return ;
    }
    if(l>=r)return;
    if(L<=md)query(rt<<1,l,md,L,R,v,d+1);
    if(R>md )query(rt<<1|1,md+1,r,L,R,v,d+1);
}
int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++ i)
            scanf("%d",&as[0][i]);
        build(1,0,n-1,1);
        printf("Case %d:\n",++cas);
        while(m--){
            int l,r,v;
            scanf("%d %d %d",&l,&r,&v);
            tot = 0;
            query(1,0,n-1,l,r,v,1);
            printf("%d\n",tot);
        }
    }
    return 0;
}

参考:http://www.cnblogs.com/aigoruan/archive/2012/09/23/2699070.html


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥