题目链接:http://noi.ac/contest/15/problem/42
比赛成绩就不说了...本题解是在比赛完后的那个晚上洗澡时想出来的...
话说想出来了是真简单...80ms不到就A了...
先说说大概思路：
创建对于一个位点的八个方向的一维数组（就是这个点的左边，右边，上边，下边，左上，左下，右上，右下）,用来储存该位点是否会受到攻击。最后累加每个方向的结果：
Qr[left_+right+up+down+left_up+left_down+right_up+right_down]++;//Qr用来表示储存会受到各攻击次数皇后的个数
最后输出 Qr[0-8]即可
题目相信都看得懂，这里就不多说了，直接说题解
注意！ 1<=x,y<=10e5
先来define点东西...
const int MAXN=100005，MAX_T=0x7f7f7f7f;
int n,m,x,y,X,w,i,res,xy,xyn;// >>>> 注意！ 1<=x,y<=10e5 <<<<
//n棋盘边长,m棋子个数，x，y坐标 ，X，w读入优化需要 ，i循环需要，res受攻击数，xy=x+y，xyn=x-y+n 用于表示 （x,y）所在的斜...
char ch;//用于读入优化
int Qr[9];//被攻击次数保存数据 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];
我们再来画一张并没有什么用的棋盘...
拿第一个样例来说，下面是一张8*8的棋盘
8*8棋盘
数据：4 3 ，4 8， 6 5 ，1 6
然后，读入数据
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;//储存坐标数据 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); }}
难受...不会排版直接上图...
initData();
首先把min啥的全部开最大...不多说memset( xxx,0x7f,sizeof(xxx))...注意数组开出来后数据是MAX_T=0x7f7f7f7f...
然后iread()优化读入数据...
重点来了↓↓↓
xy=x+y;//不难发现，x+y可以表示同一斜（左上到右下↖ ↘ ）
xyn=x-y+n;//起始x-y可以表示同一斜（左下到右上↙ ↗），+n是因为xyn需要做下标故需要为正
min_x[y]=min(min_x[y],x);//获取y行最左边的皇后x坐标
max_x[y]=max(max_x[y],x);//获取y行最右边的皇后x坐标
min_y[x]=min(min_y[x],y);//获取x列最下边的皇后y坐标
max_y[x]=max(max_y[x],y);//获取x列最上边的皇后y坐标
min_xy[xy]=min(min_xy[xy],x);//获取同一溜最左上的皇后x坐标 （其实y也行
max_xy[xy]=max(max_xy[xy],x);//获取同一溜最右下的皇后x坐标
min_xyn[xyn]=min(min_xyn[xyn],x);//获取同一溜最左下的皇后x坐标
max_xyn[xyn]=max(max_xyn[xyn],x);//获取同一溜最右上的皇后x坐标
填图后...星星就看做皇后吧:）MAX_T表示最大值0x7f7f7f7f
伪填图..
斜着的就不写了，道理是一样的...
initData()完了后呢，我们来check()一遍
void check(){ for(i=0;i<m;i++){ res=0; x=vt[i][0];//挨个获取皇后坐标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（内心十分难受，谁能教我排版...）直接上图吧...
话说这操作！显而易见这是在统计被攻击的次数嘛...（register宏定义...其实对时间影响不大...详细见下面我两次ac记录时间对比）
总的来说，大于最小的，小于最大的，然后你就被攻击了...
拿一行来举例：
res += x>min_x[y];
如果这个皇后在这一行最左边的皇后的右边...那么这个皇后就会被攻击！
然后...就写完了....
在输出一下Qr[0-8]...
void PutOut(){
for(register int i=0;i<9;i++)
printf("%d ",Qr[i]);
}
不对...main还没写...补上...
```
int main(){
initData();//读入...
check();//检查所有皇后...
PutOut();//输出答案...
return 0;
}
```
就这样...写完了...来提交一波
noi.ac #42 queen AC记录
嗯...后边两次去掉了部分无用代码...加入了作用不大的register...
noi.ac #42 queen AC统计
wtf!居然还上榜了！嘿嘿嘿...(雷布斯说，厚道的人运气不会太差哦)
RTRTRT!代码附上 ，证明一下...（虽然乱成一坨）...是在看着不想复制的话就点下边这个吧...
点击查看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];//被攻击次数保存数据 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;//储存坐标数据 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];//挨个获取皇后坐标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;}
```
***
（第二次写简书...经验还是不够，希望各位dalao们多多指教！以后会更新关于android开发和java的一些demo与算法，oj ac记录主要以c++为主）
网友评论