Codeforces Round #337 (Div. 2) C. Harmony Analysis (構造) -开发者知识库

Codeforces Round #337 (Div. 2) C. Harmony Analysis (構造) -开发者知识库,第1张

題意:

給一個k,求2^k個2^k維的向量,兩兩垂直。

已知求出k=n時的結果為一個矩陣a,求k=n 1時只需構造

a  a

a -a

就可以了,正確性一想就能知道。

 

比賽時一直沒有思路,dp沒想出,甚至打印出來想找規律orz……

 

#include <bits/stdc  .h>

using namespace std;

int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};

int a[600][600];

void _copy(int x, int y, int cx, int cy, int n)
{
    for (int i = 0; i < n;   i) {
        for (int j = 0; j < n;   j) {
            a[cx i][cy j] = a[x i][y j];
        }
    }
}

void __copy(int x, int y, int cx, int cy, int n)
{
    for (int i = 0; i < n;   i) {
        for (int j = 0; j < n;   j) {
            a[cx i][cy j] = !a[x i][y j];
        }
    }
}

void solve(int n)
{
    if (n == 0) {
        a[1][1] = 1;
    } else {
        solve(n-1);
        _copy(1, 1, 1, p[n-1] 1, p[n-1]);
        _copy(1, 1, p[n-1] 1, 1, p[n-1]);
        __copy(1, 1, p[n-1] 1, p[n-1] 1, p[n-1]);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    solve(n);
    for (int i = 1; i <= p[n];   i) {
        for (int j = 1; j <= p[n];   j) {
            if (a[i][j]) printf(" ");
            else printf("*");
        }
        printf("\n");
    }
    return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复