首页 > ACM题库 > HDU-杭电 > hdu 2679 Bloxorz-树状数组-[解题报告]C++
2014
02-13

hdu 2679 Bloxorz-树状数组-[解题报告]C++

Bloxorz

问题描述 :

Bloxorz is an interesting game and someone may have played it before. The rule of this game is simple.
This game is played on a platform constructed of many square grids. You have a cuboid whose size is 2×1×1. On the platform there is a 1×1 hole and it‘s your destination. What you have to do is move the cuboids to the hole. During the game you must keep the cuboid on the platform, if any part of cuboid is off the platform, you lose the game.
When this game starts, the cuboid stays on the platform. The way to move the cuboid is not sliding but rolling. You can move it in any of the four directions. If you want to move it right, the surfaces next to the original bottom in that direction will be the new bottom. In the following three images, the cuboid moves right twice.
Pic-1

    

输入:

Input contains multiple test cases. Each test case starts with two integers N and M (0<N, M < 20), which stand for number of rows and columns of the platform. Then there comes N lines, describe the platform with ‘#’ for empty cell, ‘^’ for square grid, ‘X’ for the position of cuboid (There maybe two ‘X’, but data guarantee that these two ‘X’s belong to the same cuboid and only one cuboid exists.).
Then there comes several lines which stand for order list. Each line only contains uppercase characters and blank. In the list, ‘L’ means moving left, ‘R’ means moving right, ‘U’ means moving up and ‘D’ means moving down. If you meet a ‘Q’, print the whole station of platform. Each case ends with a line a line entitled “END”.
ANY MOVE COULD CAUSE YOU TO LOSE THE GAME, YOU SHOULD JUST IGNORE IT.

输出:

Input contains multiple test cases. Each test case starts with two integers N and M (0<N, M < 20), which stand for number of rows and columns of the platform. Then there comes N lines, describe the platform with ‘#’ for empty cell, ‘^’ for square grid, ‘X’ for the position of cuboid (There maybe two ‘X’, but data guarantee that these two ‘X’s belong to the same cuboid and only one cuboid exists.).
Then there comes several lines which stand for order list. Each line only contains uppercase characters and blank. In the list, ‘L’ means moving left, ‘R’ means moving right, ‘U’ means moving up and ‘D’ means moving down. If you meet a ‘Q’, print the whole station of platform. Each case ends with a line a line entitled “END”.
ANY MOVE COULD CAUSE YOU TO LOSE THE GAME, YOU SHOULD JUST IGNORE IT.

样例输入:

5 6
^^^^^^
^X^^^^
^^^^^^
#^^^^^
###^^^
RQ
RQ
END

样例输出:

^^^^^^
^^XX^^
^^^^^^
#^^^^^
###^^^

^^^^^^
^^^^X^
^^^^^^
#^^^^^
###^^^

前不久,探险队b前往inst沙漠进行考察。他们在沙漠中发现了一种生命力十分强悍的植物。这种植物从种子到发芽只需要1天时间,而从发芽的第x天开始,一直到第y天(包括第y天),每天又都会繁殖出一粒种子,每棵植物都会在发芽的第z天时枯萎死亡。因为探险队b以前在营地里并没有见过这种植物,于是他们取了一颗种子放在他们的营地里(这一天叫做第0天),他们想知道第n天的时候营地里这种神奇的植物(不包括种子)的棵数m。但是这个数太大了,他们现在只想知道m的最后8位是多少。

Input

题目包含多个测试数据,每个测试数据只有一行,包含四个正整数x,y,z,n,用空格分开。其中0 < x ≤ y < z ≤ 2500,0 < n ≤ 2500。题目以四个整数0 0 0 0结束输入,这一行不用处理。

Output

每个测试数据输出一行,包含一个正整数,表示m的最后8位,m不足八位的输出m。输出不含前导0。

Sample Input

1 2 3 4 
0 0 0 0

Sample Output

5

树状数组的巧妙运用,每次所有时间点右移相对意义上等价于时间原点左移,想到这种相对问题后,问题一下变得简单许多,树状数组求和即可解决。

#include <iostream>

#include <cstring>

#define N 5008

#define M 100000000LL

using namespace std;

long long c[N];

int lowbit(int x)

{

    return x&(-x);

}

void add(int ad, long long v)

{

    while (ad <= N)

    {

        c[ad] += v;

        ad += lowbit(ad);

    }

}

long long sum(int ad)

{

    long long ans = 0;

    while (ad)

    {

        ans += c[ad];

        ad -= lowbit(ad);

    }

    return ans;

}

int main()

{

    int x, y, z, n;

    long long temp;

    while (cin >> x >> y >> z >> n && x)

    {

        memset(c, 0, sizeof(c));

        add(n+1, 1);

        while (n)

        {

            temp = sum(n+y) – sum(n+x-1);

            add(n, temp%M);

            n–;

        }

        cout << (sum(n+z) – sum(n+1))%M << endl;

    }

    return 0;

}

解题转自:http://hi.baidu.com/perfectcai_/item/dcfe5d01545bb333f3eafc5a


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }