2011-09-10 23:53:36Morris
b067. 6. 下棋問題
b067. 6. 下棋問題
作法 : 暴力解 + 單調
找出以新的點, 劃分出來的四個象限, 找出嚴格遞增, 遞減的曲線,

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;
}
內容 :
eToy 發明了一個新的益智遊戲,該遊戲由A
和B 兩人輪流在一個1,000,000 x 1,000,000 的方格棋盤上的格線交點下棋,格線交點的座標以(x, y), 0 ≤ x , y ≤
1,000,000 表示之,(0, 0)代表棋盤最左下角那點。
每一個棋子放置的位置不可以與任何其它棋子在同一X 座標或Y 座標上,棋盤上新增加一個棋子時,棋盤上的計數器會自動算出以目前棋盤上棋子所能夠圍成的「無障礙四方形」數。
「無障礙四方形」是指以任意兩個棋子所定義出的四方形內部不含其它棋子,每下一個棋子後所算出的「無障礙四方形」數即為下該棋子的得分數。每位下棋者的總分即是該下棋者每個棋子的得分數總和。
請寫一個程式計算A 和 B 兩位下棋者的累計總分。
每一個棋子放置的位置不可以與任何其它棋子在同一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;
}
上一篇:d370. 2. 盤中飧
下一篇:b174. 旅游规划