OJ入口：noi.ac

題目鏈接:http://noi.ac/contest/15/problem/42

比賽成績就不說了...本題解是在比賽完后的那個(gè)晚上洗澡時(shí)想出來的...

話說想出來了是真簡單...80ms不到就A了...

先說說大概思路：

創(chuàng)建對(duì)于一個(gè)位點(diǎn)的八個(gè)方向的一維數(shù)組（就是這個(gè)點(diǎn)的左邊絮缅，右邊膀曾，上邊酒唉，下邊叁熔，左上委乌，左下，右上者疤，右下）,用來儲(chǔ)存該位點(diǎn)是否會(huì)受到攻擊福澡。最后累加每個(gè)方向的結(jié)果：

Qr[left_+right+up+down+left_up+left_down+right_up+right_down]++;//Qr用來表示儲(chǔ)存會(huì)受到各攻擊次數(shù)皇后的個(gè)數(shù)

最后輸出 Qr[0-8]即可

題目相信都看得懂，這里就不多說了驹马，直接說題解

注意革砸！ 1<=x,y<=10e5??

先來define點(diǎn)東西...

const int MAXN=100005，MAX_T=0x7f7f7f7f;

int n,m,x,y,X,w,i,res,xy,xyn;// >>>> 注意糯累！ 1<=x,y<=10e5 <<<<

//n棋盤邊長,m棋子個(gè)數(shù)算利，x，y坐標(biāo) 泳姐，X效拭，w讀入優(yōu)化需要 ，i循環(huán)需要，res受攻擊數(shù)缎患，xy=x+y慕的，xyn=x-y+n 用于表示 （x,y）所在的斜...

char ch;//用于讀入優(yōu)化

int Qr[9];//被攻擊次數(shù)保存數(shù)據(jù) int vt[MAXN][2];

int min_x[MAXN],max_x[MAXN],min_y[MAXN],max_y[MAXN],min_xy[2*MAXN],max_xy[2*MAXN],min_xyn[2*MAXN],max_xyn[2*MAXN];

我們?cè)賮懋嬕粡埐]有什么用的棋盤...

拿第一個(gè)樣例來說，下面是一張8*8的棋盤?

8*8棋盤

數(shù)據(jù)：4? 3 挤渔，4? 8肮街， 6? 5 ，1? 6

然后判导，讀入數(shù)據(jù)

inline int iread(){//讀入優(yōu)化不多說

? ? ?X=0,w=0; ch=0;

? ? ?while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}

? ? ?while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();

? ? ?return w?-X:X;

}

void initData(){ memset(min_x,0x7f,sizeof(min_x)); memset(min_y,0x7f,sizeof(min_y)); memset(min_xy,0x7f,sizeof(min_xy)); memset(min_xyn,0x7f,sizeof(min_xyn)); n=iread(); m=iread(); for(i=0;i<m;i++){ x=iread();y=iread(); vt[i][0]=x;//儲(chǔ)存坐標(biāo)數(shù)據(jù) vt[i][1]=y; xy=x+y; xyn=x-y+n; min_x[y]=min(min_x[y],x); max_x[y]=max(max_x[y],x); min_y[x]=min(min_y[x],y); max_y[x]=max(max_y[x],y); min_xy[xy]=min(min_xy[xy],x);//左下右上 max_xy[xy]=max(max_xy[xy],x); min_xyn[xyn]=min(min_xyn[xyn],x);//左上右下 max_xyn[xyn]=max(max_xyn[xyn],x); }}

難受...不會(huì)排版直接上圖...

initData();

首先把min啥的全部開最大...不多說memset( xxx,0x7f,sizeof(xxx))...注意數(shù)組開出來后數(shù)據(jù)是MAX_T=0x7f7f7f7f...

然后iread()優(yōu)化讀入數(shù)據(jù)...

重點(diǎn)來了↓↓↓

xy=x+y;//不難發(fā)現(xiàn)嫉父，x+y可以表示同一斜（左上到右下↖ ↘ ）

xyn=x-y+n;//起始x-y可以表示同一斜（左下到右上↙ ↗），+n是因?yàn)閤yn需要做下標(biāo)故需要為正

min_x[y]=min(min_x[y],x);//獲取y行最左邊的皇后x坐標(biāo)

max_x[y]=max(max_x[y],x);//獲取y行最右邊的皇后x坐標(biāo)

min_y[x]=min(min_y[x],y);//獲取x列最下邊的皇后y坐標(biāo)

max_y[x]=max(max_y[x],y);//獲取x列最上邊的皇后y坐標(biāo)

min_xy[xy]=min(min_xy[xy],x);//獲取同一溜最左上的皇后x坐標(biāo) （其實(shí)y也行

max_xy[xy]=max(max_xy[xy],x);//獲取同一溜最右下的皇后x坐標(biāo)

min_xyn[xyn]=min(min_xyn[xyn],x);//獲取同一溜最左下的皇后x坐標(biāo)

max_xyn[xyn]=max(max_xyn[xyn],x);//獲取同一溜最右上的皇后x坐標(biāo)

填圖后...星星就看做皇后吧:）MAX_T表示最大值0x7f7f7f7f

偽填圖..

斜著的就不寫了眼刃，道理是一樣的...

initData()完了后呢绕辖，我們來check()一遍

void check(){ for(i=0;i<m;i++){ res=0; x=vt[i][0];//挨個(gè)獲取皇后坐標(biāo)x，y y=vt[i][1]; xy=x+y; xyn=x-y+n; //check left res += x>min_x[y]&&min_x[y]!=MAX_T; //check right res += x<max_x[y]&&max_x[y]!=0; //check down res += y>min_y[x]&&min_y[x]!=MAX_T; //check up res += y<max_y[x]&&max_y[x]!=0; //check xy left res += x>min_xy[xy]&&min_xy[xy]!=MAX_T; //check xy right res += x<max_xy[xy]&&max_xy[xy]!=0; //check xyn left res += x>min_xyn[xyn]&&min_xyn[xyn]!=MAX_T; //check xyn right res += x<max_xyn[xyn]&&max_xyn[xyn]!=0; Qr[res]++; }}

......T^T（內(nèi)心十分難受擂红，誰能教我排版...）直接上圖吧...

話說這操作仪际！顯而易見這是在統(tǒng)計(jì)被攻擊的次數(shù)嘛...（register宏定義...其實(shí)對(duì)時(shí)間影響不大...詳細(xì)見下面我兩次ac記錄時(shí)間對(duì)比）

總的來說，大于最小的篮条，小于最大的弟头，然后你就被攻擊了...

拿一行來舉例：

res += x>min_x[y];

如果這個(gè)皇后在這一行最左邊的皇后的右邊...那么這個(gè)皇后就會(huì)被攻擊！

然后...就寫完了....

在輸出一下Qr[0-8]...

void PutOut(){

? ? ?for(register int i=0;i<9;i++)

? ? ? ? ? printf("%d ",Qr[i]);

}??

不對(duì)...main還沒寫...補(bǔ)上...

```

int main(){

? ? ?initData();//讀入...

? ? ?check();//檢查所有皇后...

? ? ?PutOut();//輸出答案...

? ? ?return 0;

}?

```

就這樣...寫完了...來提交一波

noi.ac #42 queen AC記錄

嗯...后邊兩次去掉了部分無用代碼...加入了作用不大的register...

noi.ac #42 queen AC統(tǒng)計(jì)

wtf!居然還上榜了涉茧！嘿嘿嘿...(雷布斯說赴恨，厚道的人運(yùn)氣不會(huì)太差哦)

RTRTRT!代碼附上 ，證明一下...（雖然亂成一坨）...是在看著不想復(fù)制的話就點(diǎn)下邊這個(gè)吧...

點(diǎn)擊查看codehttp://noi.ac/submission/12865

```

#include<bits/stdc++.h>using namespace std;const int MAXN=100005;const int MAX_T=0x7f7f7f7f;int n,m,x,y,X,w,i,res,xy,xyn;// >>>> 注意伴栓！ 1<=x,y<=10e5 <<<<char ch;int Qr[9];//被攻擊次數(shù)保存數(shù)據(jù) int vt[MAXN][2];int min_x[MAXN],max_x[MAXN],min_y[MAXN],max_y[MAXN],min_xy[2*MAXN],max_xy[2*MAXN],min_xyn[2*MAXN],max_xyn[2*MAXN];inline int iread(){ X=0,w=0; ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}void initData(){ memset(min_x,0x7f,sizeof(min_x)); memset(min_y,0x7f,sizeof(min_y)); memset(min_xy,0x7f,sizeof(min_xy)); memset(min_xyn,0x7f,sizeof(min_xyn)); n=iread(); m=iread(); for(i=0;i<m;i++){ x=iread();y=iread(); vt[i][0]=x;//儲(chǔ)存坐標(biāo)數(shù)據(jù) vt[i][1]=y; xy=x+y; xyn=x-y+n; min_x[y]=min(min_x[y],x); max_x[y]=max(max_x[y],x); min_y[x]=min(min_y[x],y); max_y[x]=max(max_y[x],y); min_xy[xy]=min(min_xy[xy],x);//左下右上 max_xy[xy]=max(max_xy[xy],x); min_xyn[xyn]=min(min_xyn[xyn],x);//左上右下 max_xyn[xyn]=max(max_xyn[xyn],x); }}void check(){ for(i=0;i<m;i++){ res=0; x=vt[i][0];//挨個(gè)獲取皇后坐標(biāo)x伦连，y y=vt[i][1]; xy=x+y; xyn=x-y+n; //check left res += x>min_x[y]&&min_x[y]!=MAX_T; //check right res += x<max_x[y]&&max_x[y]!=0; //check down res += y>min_y[x]&&min_y[x]!=MAX_T; //check up res += y<max_y[x]&&max_y[x]!=0; //check xy left res += x>min_xy[xy]&&min_xy[xy]!=MAX_T; //check xy right res += x<max_xy[xy]&&max_xy[xy]!=0; //check xyn left res += x>min_xyn[xyn]&&min_xyn[xyn]!=MAX_T; //check xyn right res += x<max_xyn[xyn]&&max_xyn[xyn]!=0; Qr[res]++; }}void PutOut(){ for(i=0;i<9;i++) printf("%d ",Qr[i]);}int main(){ initData(); check(); PutOut(); return 0;}

```

***

（第二次寫簡書...經(jīng)驗(yàn)還是不夠，希望各位dalao們多多指教钳垮！以后會(huì)更新關(guān)于android開發(fā)和java的一些demo與算法惑淳，oj ac記錄主要以c++為主）