[牛客暑期多校第八场][构造]C-CDMA

发布于 2019-08-12  196 次阅读


https://ac.nowcoder.com/acm/contest/888/C

给你一个n 是2的i次方 就是说n是 2 4 8 16这种 让你构造一个n*n的矩阵 要求任意两行的内积为0 内积就是对应位置乘积之和
对于n=2 我们可以直到答案
1 1
1 -1 (很多个)
我们设这个矩阵为m 可以知道-m 也是满足条件的 然后我们根据这个 来构造2m对应的矩阵
m m
m -m
我们分为上下两个区域看 上半区域 任意两行 内积为0因为这就相当于在原来的基础上又向后延伸了一个它本身
下半区域同理
如果一个来自上半 一个来自下半 我们可以知道左边的的内积是x的话 右边的内积就是-x 加起来也为0 根据这个思路 写出代码 即可ac

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int maxn = 1024 + 5;
typedef long long ll;

int a[maxn][maxn];
int n;

void solve(int x) {//先构造n=2的(最小的)
	if (x == 1) {
		a[1][1] = 1;
		return;
	}
	int t = x / 2;
	solve(t);
	for (int i = 1; i <= t; i++) {
		for (int j = 1; j <= t; j++) {
			a[i + t][j] = a[i][j + t] = a[i][j];//右上和做下部分
			a[i + t][j + t] = -a[i][j];
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	solve(n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d%c", a[i][j], j == n ? '\n' : ' ');
		}
	}
	return 0;
}
//1 1 2 3 1+1+1+1+1+2+2+2+3+3 
//1 2 1 3 1+1+1+1+2+2+2+2+3+3

愿风指引你的道路,愿你的刀刃永远锋利。