2019.9.14校内考试

科技前沿 • 2025-03-15 11:12 • 阅读 36

大家好，我是讯享网，很高兴认识大家。

T1：

　　　发现正方形棋盘，其边长为2^k（1<k<10），而且2^k（1<k<10）-1能被3整除，就想到了分治（主要还是qbzt的老师讲过）。每次将大棋盘从中间分成4个正方形的小棋盘，根据坏点在第几个棋盘分类处理，最后在棋盘大小分为2的时候就可以结束递归了。

讯享网

AC代码：

 1 #include<iostream>  2 #include<cstdio>  3  4 using namespace std;  5  6 int a,map[514][514],len[10]={ 
 
   
 1,2,4,8,16,32,64,128,256,512},k,ex,ey;  7  8 void erfen(int zx,int zy,int yx,int yy,int hx,int hy)  9 { 10 int zhongx=(zx+yx)>>1,zhongy=(zy+yy)>>1; 11 if(zhongx==zx&&zhongy==zy)//最后要终止递归时在分类把小棋盘剩下的未确认数的点填一下  12  { 13 if(zx==hx&&zy==hy) 14  { 15 map[zx+1][zy]=map[zx+1][zy+1]=map[zx][zy+1]=4; 16  } 17 if(zx==hx&&zy+1==hy) 18  { 19 map[zx][zy]=map[zx+1][zy]=map[zx+1][zy+1]=3; 20  } 21 if(zx+1==hx&&zy==hy) 22  { 23 map[zx][zy]=map[zx][zy+1]=map[zx+1][zy+1]=2; 24  } 25 if(zx+1==hx&&zy+1==hy) 26  { 27 map[zx][zy]=map[zx+1][zy]=map[zx][zy+1]=1; 28  } 29 return; 30  } 31 if(hx<=zhongx&&hy<=zhongy)//已经确定数的点在左上 32  { 33 map[zhongx+1][zhongy+1]=map[zhongx+1][zhongy]=map[zhongx][zhongy+1]=4; 34  erfen(zx,zy,zhongx,zhongy,hx,hy); 35 erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy); 36 erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1); 37 erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1); 38  } 39 if(hx>zhongx&&hy<=zhongy)//已经确定数的点在左下  40  { 41 map[zhongx+1][zhongy+1]=map[zhongx][zhongy]=map[zhongx][zhongy+1]=2; 42  erfen(zx,zy,zhongx,zhongy,zhongx,zhongy); 43 erfen(zhongx+1,zy,yx,zhongy,hx,hy); 44 erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1); 45 erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1); 46  } 47 if(hx<=zhongx&&hy>zhongy)//在右上  48  { 49 map[zhongx+1][zhongy+1]=map[zhongx][zhongy]=map[zhongx+1][zhongy]=3; 50  erfen(zx,zy,zhongx,zhongy,zhongx,zhongy); 51 erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy); 52 erfen(zx,zhongy+1,zhongx,yy,hx,hy); 53 erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1); 54  } 55 if(hx>zhongx&&hy>zhongy)//在右下  56  { 57 map[zhongx][zhongy+1]=map[zhongx][zhongy]=map[zhongx+1][zhongy]=1; 58  erfen(zx,zy,zhongx,zhongy,zhongx,zhongy); 59 erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy); 60 erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1); 61 erfen(zhongx+1,zhongy+1,yx,yy,hx,hy); 62  } 63 } 64 65 void print()//输出矩阵  66 { 67 for(int i=1;i<=a;i++) 68  { 69 for(int j=1;j<a;j++) 70 putchar(map[i][j]+'0'),putchar(' '); 71 putchar(map[i][a]+'0'),putchar('\n'); 72  } 73 } 74 75 int main() 76 { 77 freopen("chessboard.in","r",stdin); 78 freopen("chessboard.out","w",stdout); 79 cin>>k>>ey>>ex; 80 a=len[k]; 81 map[ex][ey]=7; 82 erfen(1,1,a,a,ex,ey); 83  print(); 84 return 0; 85 }

讯享网

2019.9.14校内考试

相关推荐