首页 > ACM题库 > HDU-杭电 > HDU 2878-Great World of Goo-计算几何-[解题报告]HOJ
2014
02-17

HDU 2878-Great World of Goo-计算几何-[解题报告]HOJ

Great World of Goo

问题描述 :

The game is built around the idea of creating large structures using balls of goo. It is based on the prototype game Tower of Goo developed for Kyle Gabler’s rapid game prototyping Experimental Gameplay Project. The game is divided into five chapters, each containing several levels. Each level has its own graphic and musical theme, giving it unique atmosphere, similar in style to Tim Burton’s film designs. There is also a bonus meta-game called World of Goo Corporation, where the objective is to build the highest tower using goo balls which the player collected through the course of the game. Players from all over the world can compete, as the height of the tower and number of goo balls used are being constantly uploaded to the 2D Boy server.
–Wikipedia
As mentioned above, World of Goo is an excellent independent game. Personally I like playing it rather than Plants vs. Zombies though both of them are great.
Let’s consider a simplified version of “Fisty Bog” in Chapter One (Figure 1).

(Figure 1)


Ignore the part before the red line, as it’s given by the system initially. The following goo balls make the bridge using regular triangles, numbered from 1, beginning from left to right. To ensure the bridge formed strictly horizontal, we place a light goo ball every three triangles, and in this problem we don’t need to care about those balls.

From the figure we know that, some triangles are more danger during the construction process. For that case, goo balls want to be placed in different triangles. Risky goo balls want to be placed on the triangle more danger while others want safer ones. Now, my question comes, how many number of solutions exist when all goo balls are used and all wills are satisfied.

输入:

The first line: and integer k (k<=15) indicates the number of test case;
For each test case:
First line: n and m, 0<m,n<=500 , n represents the number of goo balls, m represents the number of wills;
Line 2…m+1:
Each line is consist of integers K A1 B1 A2 B2 … AK BK P C1 D1 C2 D2 … CP DP, represents a restriction. That means the goo ball(s) numbered between A1 and B1 (inclusive), or between A2 and B2 (inclusive) or … or between Ak and Bk (inclusive) wants to be placed at triangle(s) number between C1 and D1 (inclusive), or between C2 and D2 (inclusive) or … or between Ck and Dk (inclusive). Two restrictions may be the same or partly same. Every restriction is legal.

输出:

The first line: and integer k (k<=15) indicates the number of test case;
For each test case:
First line: n and m, 0<m,n<=500 , n represents the number of goo balls, m represents the number of wills;
Line 2…m+1:
Each line is consist of integers K A1 B1 A2 B2 … AK BK P C1 D1 C2 D2 … CP DP, represents a restriction. That means the goo ball(s) numbered between A1 and B1 (inclusive), or between A2 and B2 (inclusive) or … or between Ak and Bk (inclusive) wants to be placed at triangle(s) number between C1 and D1 (inclusive), or between C2 and D2 (inclusive) or … or between Ck and Dk (inclusive). Two restrictions may be the same or partly same. Every restriction is legal.

样例输入:

3
6 1
1 1 6 1 1 4
6 1
1 1 6 1 1 3
10 1
1 1 10 1 1 8

样例输出:

720
0
OVERFLOW!

HDU_2878

    这个题目说实话,感觉这个题的解题思想很好,但是题面的描述啊,&@!#¥&*@!*&!@#&*!@#……&*!@#*(¥@!)!!!!!!!

    看这张图就知道我为啥要吐槽题目的描述了……

    首先,题目里面核心就两个元素——球球和三角形,而且不难发现球球的数量-2就是三角形的数量,如果我们把球球可以放的位置按一定顺序编码的话,就会发现对于一段连续的三角形就会得到一段连续的位置,于是问题就变成了一段标号连续的球可以放到一段标号连续的位置中去,问最后有多少中方案,这就像是在求最大匹配有多少个一样,但是貌似没有直接求最大匹配个数的算法,所以采用搜索来实现。

    暂且先解释一下K A1 B1 A2 B2 … AK BK P C1 D1 C2 D2 … CP DP是什么意思,比如2 1 2 4 5 1 4 6,意思就是说标号为1、2、4、5的球可以放到标号为4、5、6的三角形中,转化成位置的话就是说这些球可以放到4、5、6、7、8这些位置上去。还有就是and all wills are satisfied这句话纯属扯淡,如果按所有will都满足去做的话就会是WA,实际上只要满足其中一个will就行,相当于将题目中的这些will取并集,而不是取交集。

    接下来就是思维很好的部分了,这个我也是在找到题解之后才会的(蛋疼的是只有题解没标程,所以一直到今早枚举题意的时候才偶然AC了这个题……)。建立一个N*N行2*N列的稀疏矩阵,每一行表示了某个球放到某个位置这样的特定的方案,如果这个球可以放到这个位置,就将这行中两列置为1,一列表示的是这是哪个球,另一列表示的是这是哪个位置,这样建好矩阵之后就转化成了选取某些行使得每列有且仅有一个1的模型,用Dancing Links搞之即可。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXM 1010
#define MAXN 250010
#define MAXD 501010
#define INF 0x3f3f3f3f
int N, M, K, P, a[510], b[510], g[510][510];
int size, U[MAXD], D[MAXD], L[MAXD], R[MAXD], C[MAXD];
int S[MAXM], H[MAXN], ANS;
void read(int X, int *a, int c)
{
    int i, j, x, y, n;
    memset(a, 0, sizeof(int) * (N + 1));
    for(i = 0; i < X; i ++)
    {
        scanf("%d%d", &x, &y);
        if(x > y) std::swap(x, y);
        if(c) y += 2;
        for(j = x; j <= y; j ++) a[j] = 1;
    }
}
void prep(int n, int m)
{
    int i;
    for(i = 0; i <= m; i ++)
    {
        R[i] = i + 1, L[i + 1] = i;
        U[i] = D[i] = i, S[i] = 0;
    }
    R[m] = 0, size = m;
    for(i = 0; i <= n; i ++) H[i] = -1;
}
void insert(int r, int c)
{
    ++ size;
    C[size] = c, ++ S[c];
    D[size] = D[c], U[size] = c, U[D[c]] = size, D[c] = size;
    if(H[r] == -1) L[size] = R[size] = size, H[r] = size;
    else L[size] = H[r], R[size] = R[H[r]], L[R[H[r]]] = size, R[H[r]] = size;
}
void init()
{
    int i, j, k;
    scanf("%d%d", &N, &M);
    memset(g, 0, sizeof(g));
    for(i = 0; i < M; i ++)
    {
        scanf("%d", &K), read(K, a, 0);
        scanf("%d", &P), read(P, b, 1);
        for(j = 1; j <= N; j ++)
            if(a[j])
                for(k = 1; k <= N; k ++)
                    if(b[k]) g[j][k] = 1;
    }
    prep(N * N, N + N);
    for(i = 1; i <= N; i ++)
        for(j = 1; j <= N; j ++)
            if(g[i][j]) insert((i - 1) * N + j, i), insert((i - 1) * N + j, N + j);
}
void remove(int c)
{
    int i, j;
    R[L[c]] = R[c], L[R[c]] = L[c];
    for(i = D[c]; i != c; i = D[i])
        for(j = R[i]; j != i; j = R[j])
            U[D[j]] = U[j], D[U[j]] = D[j], -- S[C[j]];
}
void resume(int c)
{
    int i, j;
    for(i = U[c]; i != c; i = U[i])
        for(j = L[i]; j != i; j = L[j])
            U[D[j]] = j, D[U[j]] = j, ++ S[C[j]];
    R[L[c]] = c, L[R[c]] = c;
}
void dance()
{
    if(R[0] == 0)
    {
        ++ ANS;
        return ;
    }
    int i, j, t = INF, id;
    for(i = R[0]; i != 0; i = R[i])
        if(S[i] < t) t = S[i], id = i;
    remove(id);
    for(i = D[id]; i != id; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j]) remove(C[j]);
        dance();
        if(ANS > 65535) return ;
        for(j = L[i]; j != i; j = L[j]) resume(C[j]);
    }
    resume(id);
}
void solve()
{
    ANS = 0;
    dance();
    if(ANS > 65535) printf("OVERFLOW!\n");
    else printf("%d\n", ANS);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();
    }
    return 0;
}

 

 

解题参考:http://www.cnblogs.com/staginner/archive/2012/09/19/2693186.html


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。