Codeforces Tutorial

C. Harmony Analysis

Problem Analysis

题目大意生成一个维度为2的k次方的方阵，使得任意两行的内积为0.
当\(k=2\)时
\[ \left[ \begin{array}{cc|cc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ \hline 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1\\ \end{array}\right] \]

可以发现规律是除了右下角，其他三个矩阵相同，右下角每个元素去相反数。即
\[ \left[ \begin{array}{c|c} A& A\\ \hline A& -A\\ \end{array} \right] \]

可以验证当\(k=1\)时也成立。

Acepted Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<istream>
#include<cassert>
#include<set>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<" = "<<x<<" , "\
<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
const int MAXN=600;
int power2(int n)
{
    int rt=1;
    for(int ii=1;ii<=n ;ii++ ){
        rt*=2;
    }
    return rt;
}
int grid[MAXN][MAXN];
void format(int n)
{
    if(n==1)cout<<"+";
    else cout<<"*";
}
int main()
{
//    freopen("in.txt","r",stdin);
    int k;
    cin>>k;
    grid[1][1]=1;
    for(int ii=1;ii<=k ;ii++ ){
        ///对称生长法
        int l=power2(ii-1)+1,r=power2(ii),
        delta=l-1;
        for(int row=l-delta;row<=r-delta ;row++ ){
            for(int col=l;col<=r ;col++ ){
                grid[row][col]=grid[row][col-delta];
            }
        }
        for(int row=l;row<=r ;row++ ){
            for(int col=l-delta;col<=r-delta ;col++ ){
                grid[row][col]=grid[row-delta][col];
            }
        }
        for(int row=l;row<=r ;row++ ){
            for(int col=l;col<=r ;col++ ){
                grid[row][col]=-grid[row-delta][col-delta];
            }
        }
    }
    int pw=power2(k);
    for(int ii=1;ii<=pw ;ii++ ){
        for(int jj=1;jj<=pw ;jj++ ){
            format(grid[ii][jj]);
        }
        cout<<endl;
    }
}

Wrong Answer Cases

What I Learn

给出的矩阵是\(n\times n\)，然后\(n\)又是\(2\)的幂次。突破口往往在这样比较凑巧的特点上。所以题目的形式值得反复推敲

Reference