牛客多校第八场 C
- 题意：
- 构造题，输入m，m是2的次方，
- 输出m行m列的矩阵，要求任意俩行的相加结果为0.
- 题解：
- 没有做过多少构造题，规律也找麻烦了，不知道怎么写
- 这里首先考虑最小的2*2的矩阵为
- 1 1
- 1 -1
- m m
- m -m
- 可以令m = 1
- 那么转移到4*4里就成了
- 1 1 1 1
- 1 -1 1 -1
- 1 1 -1 -1
- 1 -1 -1 1
- m m m m
- m -m m -m
- m m -m -m
- m -m -m m
- 不知道大家找到规律了吗
- 设a的解为m
- 那么2a的解就是
- m m
- m -m
- 递归求解。
- 代码：
#include <bits/stdc++.h> using namespace std; int a[1030][1030]; void solve(int n) { if(n == 2){ return ; } solve(n>>1); int x = n>>1; for(int i=1;i<=x;i++) { for(int j=1;j<=x;j++) { a[i][j+x] = a[i][j]; a[i+x][j] = a[i][j]; a[i+x][j+x] = -a[i][j]; } } } int main() { int n; cin>>n; a[1][1] = 1,a[1][2] = 1,a[2][1] = 1,a[2][2] = -1; solve(n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(j != 1) cout<<" "; cout<<a[i][j]; }cout<<endl; } return 0; }
查看14道真题和解析