首页 > ACM题库 > HDU-杭电 > HDU 4742-Pinball Game 3D-分治-[解题报告]HOJ
2015
09-17

HDU 4742-Pinball Game 3D-分治-[解题报告]HOJ

Pinball Game 3D

问题描述 :

RD is a smart boy and excel in pinball game. However, playing common 2D pinball game for a great number of times results in accumulating tedium.

Recently, RD has found a new type of pinball game, a 3D pinball game. The 3D pinball game space can be regarded as a three dimensional coordinate system containing N balls. A ball can be considered as a point. At the beginning, RD made a shot and hit a ball. The ball hit by RD will move and may hit another ball and the “another ball” may move and hit another another ball, etc. But once a ball hit another ball, it will disappear.

RD is skilled in this kind of game, so he is able to control every ball’s moving direction. But there is a limitation: if ball A’s coordinate is (x1,y1,z1) and ball B’s coordinate is (x2,y2,z2), then A can hit B only if x1 <= x2 and y1 <= y2 and z1 <= z2.

Now, you should help RD to calculate the maximum number of balls that can be hit and the number of different shooting schemes that can achieve that number. Two schemes are different if the sets of hit balls are not the same. The order doesn’t matter.

输入:

The first line contains one integer T indicating the number of cases.
In each case, the first line contains one integer N indicating the number of balls.
The next N lines each contains three non-negative integer (x, y, z), indicating the coordinate of a ball.
The data satisfies T <= 3, N <= 105, 0 <= x, y, z <= 230, no two balls have the same coordinate in one case.

输出:

The first line contains one integer T indicating the number of cases.
In each case, the first line contains one integer N indicating the number of balls.
The next N lines each contains three non-negative integer (x, y, z), indicating the coordinate of a ball.
The data satisfies T <= 3, N <= 105, 0 <= x, y, z <= 230, no two balls have the same coordinate in one case.

样例输入:

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

样例输出:

2 1
3 2
Hint
In the first case, RD can shoot the second ball at first and hit the third ball indirectly. In the second case, RD can shoot the second or the third ball initially and hit the fourth ball as well as the fifth ball. Two schemes are both the best.

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by—cxlove

毫无分治的灵感。。。

一维的答案就是n,二维的就是按x排序然后 对y求LIS。三维的肯定要按X排序,就少掉一维。

然后将Z离散化,用BIT维护。。。想法大概都知道,就是不会做

分治做法,将区间的点按y排序,将左区间的点加入到BIT中

查询右区间的点,并更新就行了。。

做法是nlognlogn

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#define lowbit(x) (x & (-x))
#define mp(a,b) make_pair (a , b)
#pragma comment(linker, "/STACK:1024000000,1024000000")    
using namespace std;
typedef long long LL;
const int N = 100005;
typedef pair<int , int> pii;
struct Node {
    int x , y , z , id;
    void input () {
        scanf ("%d %d %d" , &x , &y, &z);
    }
    bool operator < (const Node &n) const {
        return x != n.x ? x < n.x : (y != n.y ? y < n.y : z < n.z);
    }
}a[N] , b[N];
int x[N] , m , n;
pii dp[N] , bit[N];
void update (pii &a , pii b) {
    if (b.first > a.first) a = b;
    else if (b.first == a.first) a.second += b.second;
}
void init () {
    for (int i = 1 ; i <= m ; i ++)
        bit[i] = mp(0 , 0);
}
void add (int idx , pii val) {
    for (int i = idx ; i <= m ; i += lowbit (i))
        update (bit[i] , val);
}
pii ask (int idx) {
    pii ans = mp (0 , 0);
    for (int i = idx ; i > 0 ; i -= lowbit (i))
        update (ans , bit[i]);
    return ans;
}
void clear (int idx) {
    for (int i = idx ; i <= m ; i += lowbit (i))
        bit[i] = mp (0 , 0);
}
void gao (int l , int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    gao (l , mid);
    int cnt = 0;
    for (int i = l ; i <= r ; i ++) {
        b[cnt ++] = a[i];
        b[cnt - 1].x = 0;
    }
    sort (b , b + cnt);
    for (int i = 0 ; i < cnt ; i ++) {
        if (b[i].id <= mid) {
            add (b[i].z , dp[b[i].id]);
        }
        else {
            pii t = ask (b[i].z);
            t.first ++;
            update (dp[b[i].id] , t);
        }
    }
    // init ();
    for (int i = 0 ; i < cnt ; i ++)
        if (b[i].id <= mid)
            clear (b[i].z);
    gao (mid + 1 , r);
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    int t ;
    scanf ("%d" , &t);
    while (t --) {
        scanf ("%d" , &n);
        for (int i = 0 ; i < n ; i ++) {
            a[i].input ();
            x[i] = a[i].z;
            dp[i] = mp (1 , 1);
        }
        sort (x , x + n);
        m = unique (x , x + n) - x;
        for (int i = 0 ; i < n ; i ++)
            a[i].z = lower_bound (x , x + m , a[i].z) - x + 1;
        sort (a , a + n);
        for (int i = 0 ; i < n ; i ++)
            a[i].id = i;
        init ();
        gao (0 , n - 1);
        pii ans = mp (0 , 0);
        for (int i = 0 ; i < n ; i ++) {
            update (ans , dp[i]);
        }
        printf ("%d %d\n" , ans.first , ans.second);
    }
    return 0;
}


参考:http://blog.csdn.net/acm_cxlove/article/details/11850333