b067. 6. 下棋問題＠Morris' Blog｜PChome Online 個人新聞台

2011-09-10 23:53:36| 人氣1,060| 回應0 | 上一篇 | 下一篇

b067. 6. 下棋問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

 eToy 發明了一個新的益智遊戲，該遊戲由A 
和B 兩人輪流在一個1,000,000 x 1,000,000 的方格棋盤上的格線交點下棋，格線交點的座標以（x, y）, 0 ≤ x , y ≤
 1,000,000 表示之，(0, 0)代表棋盤最左下角那點。
每一個棋子放置的位置不可以與任何其它棋子在同一X 座標或Y 座標上，棋盤上新增加一個棋子時，棋盤上的計數器會自動算出以目前棋盤上棋子所能夠圍成的「無障礙四方形」數。
「無障礙四方形」是指以任意兩個棋子所定義出的四方形內部不含其它棋子，每下一個棋子後所算出的「無障礙四方形」數即為下該棋子的得分數。每位下棋者的總分即是該下棋者每個棋子的得分數總和。
請寫一個程式計算A 和 B 兩位下棋者的累計總分。 

輸入說明：

第一行輸入只有一個整數n，代表此盤棋共下了n (1 ≤ n ≤ 5,000)個棋子。接下來的n 行，每一行有兩個整數，依序代表這n 個棋子所放置的位置。
請注意，由於測試資料中確實包含n=5000 的輸入，你的程式必須非常的有效率才會通過所有的測試資料。
 

輸出說明：

請輸出兩個整數，分別代表該盤棋兩位下棋者的累計得分數。先下棋者(A) 的分數在前，後下棋者(B)的分數在後，中間用一個空白隔開。
範例說明： 
 

範例輸入：

4    <- 此盤棋共下了四步棋
2 3  <- 第一步棋A 下在 (2, 3) *這一步棋A 得0 分
3 4  <- 第二步棋B 下在 (3, 4) *這一步棋B 得1 分
1 2  <- 第三步棋A 下在 (1, 2) *這一步棋A 得2 分
4 1  <- 第四步棋B 下在 (4, 1) *這一步棋B 得5 分
7    <- 此盤棋共下了七步棋
1 5  <- 第一步棋A 下在 (1, 5) *這一步棋A 得0 分
2 7  <- 第二步棋B 下在 (2, 7) *這一步棋B 得1 分
3 8  <- 第三步棋A 下在 (3, 8) *這一步棋A 得2 分
5 1  <- 第四步棋B 下在 (5, 1) *這一步棋B 得5 分
6 2  <- 第五步棋A 下在 (6, 2) *這一步棋A 得9 分
7 3  <- 第六步棋B 下在 (7, 3) *這一步棋B 得13 分
4 4  <- 第七步棋A 下在 (4, 4) *這一步棋A 得10 分

範例輸出：

2 6    <- 這盤棋累計得分為A 棋者2 分，B 棋者6 分
21 19  <- 這盤棋累計得分為A 棋者21 分，B 棋者19 分

提示：

出處：

 
  94全國資訊學科能力決賽

作法 : 暴力解 + 單調
找出以新的點, 劃分出來的四個象限, 找出嚴格遞增, 遞減的曲線,

A 是新的點

在曲線上的點, 都可以跟 A 做一個無礙的矩形, 曲線上的第二象限跟第四象限,
第一象限跟第三象限, 有可能之前存在無礙的矩形, 就必須被砍除

/**********************************************************************************/
/* Problem: b067 "6. 下棋問題" from 94全國資訊學科能力決賽         */
/* Language: C                                                                   */
/* Result: AC(172ms, 24.7MB) judge by this@ZeroJudge                             */
/* Author: morris1028 at 2011-09-10 22:43:49                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
#define oo 2147483647
char link[25000001];
struct {
   int x, y, num;
}Point[5001];
int First[5001], Second[5001], Third[5001], Fourth[5001];
int Calu(int x, int y, int n, int idx) {
   int Fy = oo, Sy = oo, Ty = -oo, Fthy = -oo;
   int i, j, Ft, St, Tt, Ftht;
   Ft = St = Tt = Ftht = 0;
   for(i = idx+1; i <= n; i++) {
       if(Point[i].y > y) {
           if(Point[i].y < Fy) {
               Fy = Point[i].y;
               First[Ft++] = Point[i].num;
           }
       } else {
           if(Point[i].y > Fthy) {
               Fthy = Point[i].y;
               Fourth[Ftht++] = Point[i].num;
           }
       }
   }
   for(i = idx-1; i >= 0; i--) {
       if(Point[i].y > y) {
           if(Point[i].y < Sy) {
               Sy = Point[i].y;
               Second[St++] = Point[i].num;
           }
       } else {
           if(Point[i].y > Ty) {
               Ty = Point[i].y;
               Third[Tt++] = Point[i].num;
           }
       }
   }
   int nodex = Point[idx].num, nodey;
   int Ans = Ft + St + Tt + Ftht;
   for(i = 0; i < Ft; i++) {
       nodey = First[i];
       link[nodex*5000+nodey] = 1;
       link[nodey*5000+nodex] = 1;
   }
   for(i = 0; i < St; i++) {
       nodey = Second[i];
       link[nodex*5000+nodey] = 1;
       link[nodey*5000+nodex] = 1;
   }
   for(i = 0; i < Tt; i++) {
       nodey = Third[i];
       link[nodex*5000+nodey] = 1;
       link[nodey*5000+nodex] = 1;
   }
   for(i = 0; i < Ftht; i++) {
       nodey = Fourth[i];
       link[nodex*5000+nodey] = 1;
       link[nodey*5000+nodex] = 1;
   }
   for(i = 0; i < Ft; i++) {
       for(j = 0; j < Tt; j++) {
           nodex = First[i], nodey = Third[j];
           if(link[nodex*5000+nodey])
               Ans--, link[nodex*5000+nodey] = 0;
       }
   }
   for(i = 0; i < St; i++) {
       for(j = 0; j < Ftht; j++) {
           nodex = Second[i], nodey = Fourth[j];
           if(link[nodex*5000+nodey])
               Ans--, link[nodex*5000+nodey] = 0;
       }
   }
   return Ans;
}
main() {
   int n, i, j, x, y;
   while(scanf("%d", &n) == 1) {
       memset(link, 0, sizeof(link));
       long long A = 0, B = 0, Score = 0;
       for(i = 0; i < n; i++) {
           scanf("%d %d", &x, &y);
           for(j = i-1; j >= 0; j--)
               if(Point[j].x > x)   Point[j+1] = Point[j];
               else   break;
           Point[j+1].x = x, Point[j+1].y = y, Point[j+1].num = i;
           Score += Calu(x, y, i, j+1);
           if(i&1)   B += Score;
           else   A += Score;
       }
       printf("%lld %lld\n", A, B);
   }
   return 0;
}

利用位元運算, 將連結的部分壓縮

/**********************************************************************************/
/* Problem: b067 "6. 下棋問題" from 94全國資訊學科能力決賽         */
/* Language: C                                                                   */
/* Result: AC(128ms, 3.4MB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2011-09-10 23:39:27                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
#define oo 2147483647
unsigned int link[781260];
struct {
    int x, y, num;
}Point[5001];
int First[5001], Second[5001], Third[5001], Fourth[5001];
void modifybit(int state) {
    static int i, j;
    i = state>>5, j = state&31;
    link[i] ^= (1<<j);
}
int findbit(int state) {
    static int i, j;
    i = state>>5, j = state&31;
    return link[i]&(1<<j);
}
int Calu(int x, int y, int n, int idx) {
    int Fy = oo, Sy = oo, Ty = -oo, Fthy = -oo;
    static int i, j, Ft, St, Tt, Ftht;
    Ft = St = Tt = Ftht = 0;
    for(i = idx+1; i <= n; i++) {
        if(Point[i].y > y) {
            if(Point[i].y < Fy) {
                Fy = Point[i].y;
                First[Ft++] = Point[i].num;
            }
        } else {
            if(Point[i].y > Fthy) {
                Fthy = Point[i].y;
                Fourth[Ftht++] = Point[i].num;
            }
        }
    }
    for(i = idx-1; i >= 0; i--) {
        if(Point[i].y > y) {
            if(Point[i].y < Sy) {
                Sy = Point[i].y;
                Second[St++] = Point[i].num;
            }
        } else {
            if(Point[i].y > Ty) {
                Ty = Point[i].y;
                Third[Tt++] = Point[i].num;
            }
        }
    }
    int nodex = Point[idx].num, nodey;
    int Ans = Ft + St + Tt + Ftht;
    for(i = 0; i < Ft; i++) {
        nodey = First[i];
        modifybit(nodey*5000+nodex);
    }
    for(i = 0; i < St; i++) {
        nodey = Second[i];
        modifybit(nodey*5000+nodex);
    }
    for(i = 0; i < Tt; i++) {
        nodey = Third[i];
        modifybit(nodex*5000+nodey);
    }
    for(i = 0; i < Ftht; i++) {
        nodey = Fourth[i];
        modifybit(nodex*5000+nodey);
    }
    for(i = 0; i < Ft; i++) {
        for(j = 0; j < Tt; j++) {
            nodex = First[i], nodey = Third[j];
            if(findbit(nodex*5000+nodey))
                Ans--, modifybit(nodex*5000+nodey);
        }
    }
    for(i = 0; i < St; i++) {
        for(j = 0; j < Ftht; j++) {
            nodex = Second[i], nodey = Fourth[j];
            if(findbit(nodex*5000+nodey))
                Ans--, modifybit(nodex*5000+nodey);
        }
    }
    return Ans;
}
main() {
    int n, i, j, x, y;
    while(scanf("%d", &n) == 1) {
        memset(link, 0, sizeof(link));
        long long A = 0, B = 0, Score = 0;
        for(i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            for(j = i-1; j >= 0; j--)
                if(Point[j].x > x)    Point[j+1] = Point[j];
                else    break;
            Point[j+1].x = x, Point[j+1].y = y, Point[j+1].num = i;
            Score += Calu(x, y, i, j+1);
            if(i&1)    B += Score;
            else    A += Score;
        }
        printf("%lld %lld\n", A, B);
    }
    return 0;
}

我要檢舉

#b067#6 #下棋問題

台長： Morris

您可能對以下文章有興趣

[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）

d913. 1. 彈珠配置

[ZJ] d372. 4. 合法執行路徑問題

b066. 5. 六芒星棋遊戲：先還是後比較有利？

人氣(1,060) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:b174. 旅游规划
此分類上一篇:d370. 2. 盤中飧

回應(0)