首页 > ACM题库 > HDU-杭电 > HDU 3468-Treasure Hunting-线段树-[解题报告]HOJ
2014
03-30

HDU 3468-Treasure Hunting-线段树-[解题报告]HOJ

Treasure Hunting

问题描述 :

Do you like treasure hunting? Today, with one of his friend, iSea is on a venture trip again. As most movie said, they find so many gold hiding in their trip.
Now iSea’s clever friend has already got the map of the place they are going to hunt, simplify the map, there are three ground types:

● ‘.’ means blank ground, they can get through it
● ‘#’ means block, they can’t get through it
● ‘*’ means gold hiding under ground, also they can just get through it (but you won’t, right?)

What makes iSea very delighted is the friend with him is extraordinary justice, he would not take away things which doesn’t belong to him, so all the treasure belong to iSea oneself!
But his friend has a request, he will set up a number of rally points on the map, namely ‘A’, ‘B’ … ‘Z’, ‘a’, ‘b’ … ‘z’ (in that order, but may be less than 52), they start in ‘A’, each time friend reaches to the next rally point in the shortest way, they have to meet here (i.e. iSea reaches there earlier than or same as his friend), then start together, but you can choose different paths. Initially, iSea’s speed is the same with his friend, but to grab treasures, he save one time unit among each part of road, he use the only one unit to get a treasure, after being picked, the treasure’s point change into blank ground.
Under the premise of his friend’s rule, how much treasure iSea can get at most?

输入:

There are several test cases in the input.

Each test case begin with two integers R, C (2 ≤ R, C ≤ 100), indicating the row number and the column number.
Then R strings follow, each string has C characters (must be ‘A’ � ‘Z’ or ‘a’ � ‘z’ or ‘.’ or ‘#’ or ‘*’), indicating the type in the coordinate.

The input terminates by end of file marker.

输出:

There are several test cases in the input.

Each test case begin with two integers R, C (2 ≤ R, C ≤ 100), indicating the row number and the column number.
Then R strings follow, each string has C characters (must be ‘A’ � ‘Z’ or ‘a’ � ‘z’ or ‘.’ or ‘#’ or ‘*’), indicating the type in the coordinate.

The input terminates by end of file marker.

样例输入:

2 4
A.B.
***C
2 4
A#B.
***C

样例输出:

1
2

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 100000+10;
int n,m,sum;

struct node
{
    int l,r;
    __int64 n,sum;//sum为增量
} a[maxn<<2];

void init(int l,int r,int i)
{
    a[i].l = l;
    a[i].r = r;
    a[i].n = 0;
    a[i].sum = 0;
    if(l!=r)
    {
        int mid = (l+r)>>1;
        init(l,mid,2*i);
        init(mid+1,r,2*i+1);
    }
}

void insert(int i,int l,int r,__int64 m)
{
    a[i].n+=(r-l+1)*m;
    if(a[i].l >= l && a[i].r <= r)
        a[i].sum+=m;////若此节点所在区段被包含在要插入的区段中,就将插入值存在sum

    else
    {
        int mid = (a[i].l+a[i].r)>>1;
        if(r<=mid)
            insert(2*i,l,r,m);
        else if(l>mid)
            insert(2*i+1,l,r,m);
        else
        {
            insert(2*i,l,mid,m);
            insert(2*i+1,mid+1,r,m);
        }
    }
}

__int64 find(int i,int l,int r)
{
    if(a[i].l == l && a[i].r == r)
        return a[i].n;
    else
    {
        int mid = (a[i].l+a[i].r)>>1;
        if(a[i].sum)
        { //若上面if条件不成立,则要询问它的子节点,此时增量要下传,并且要更新其本身的sum;
            a[2*i].sum += a[i].sum;
            a[2*i].n+=a[i].sum*(a[2*i].r-a[2*i].l+1);
            a[2*i+1].sum += a[i].sum;
            a[2*i+1].n+=a[i].sum*(a[2*i+1].r-a[2*i+1].l+1);
            a[i].sum = 0;
        }
        if(r<=mid)
            return find(2*i,l,r);
        else if(l>mid)
            return find(2*i+1,l,r);
        else
        {
            return find(2*i,l,mid)+find(2*i+1,mid+1,r);
        }
    }
}

int main()
{
    int i,j,x,y;
    __int64 k;
    char str[5];
    while(~scanf("%d%d",&n,&m))
    {
        init(1,n,1);
        for(i = 1; i<=n; i++)
        {
            scanf("%I64d",&k);
            insert(1,i,i,k);
        }
        while(m--)
        {
            scanf("%s%d%d",str,&x,&y);
            if(str[0] == 'C')
            {
                scanf("%I64d",&k);
                insert(1,x,y,k);
            }
            else if(str[0] == 'Q')
                printf("%I64d\n", find(1,x,y));
        }
    }

    return 0;
}

参考:http://blog.csdn.net/libin56842/article/details/13614183


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge