Codeforces Round #719 (Div. 3) C. Not Adjacent Matrix
一、写在前面
按说这就是一道典型的构造题。但是由于参赛经验不足,自己又去多想能否用枚举,甚至dfs等做法来做,而忽略了数据范围的问题,导致最后没有完成这道题。
二、算法分析
参赛时就想到了按奇数和偶数构造。因为要求差1,那么我们按照先填奇数再填偶数的策略来做,这样可以保证奇数的部分左右相邻至少差1,偶数部分同理。考虑上下相邻,更是差2∗n。那么就只用考虑衔接处即可,这里有个巧妙的方式就是奇数和偶数都从小到大排列,这样衔接处差距最大。只有2这个特例无法构造,输出-1即可
三、代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int N=105; 7 int G[N][N]; 8 int n; 9 int cnt=0; //记录输出了多少个数,用于控制换行10 void enter(){ //控制换行的函数11 cnt++;12 if(cnt%n==0) cout<<endl;13 }14 void solve(){15 16 for(int i=0;i<=n*n/2-1;i++){17 cout<<i*2+1<<' ';18 enter();19 }20 if(n%2){21 cout<<n*n<<' ';22 enter();23 }24 for(int i=1;i<=n*n/2;i++){25 cout<<i*2<<' ';26 enter();27 }28 /*if(n%2==0){29 cout<<n*n<<' ';30 enter();31 }*/32 }33 int main(){34 35 int T;36 cin>>T;37 while(T--){38 cin>>n;39 if(n==1) cout<<1<<endl;40 else if(n==2) cout<<-1<<endl;41 else solve();42 }43 44 45 46 47 return 0;48 49 }
__EOF__
来源:https://www.cnblogs.com/talk-sea/p/14748758.html