牛客网暑期ACM多校训练营(第四场) D - Another Distinct Values

啊 摸鱼真棒 实验室有空调 爽死了(就是蚊子有点多)

1.png

大致题意是使用1,0,-1构建一个N*N的矩阵,并且使矩阵的每行每列的和都不相等,如果存在这样的矩阵,输出"possible"并输出任意种情况,如果不存在输出"impossible"

首先在纸上模拟了一下,当N是奇数的时候是必然无解的
而当N是偶数时,我们可以先构建一个对称的矩阵,但由于对角线位置特殊,所以我们使用0填充,其余部分用1与-1填充

2.png

此时的话矩阵是关于对角线对称的,行列和存在相等,不符合题意,所以要想办法打破这种对称,所以对于对角线的另一半0的位置上可以使用其他数字来填充,则必定能构建一个合法的矩阵

3.png

附代码

Accepted 72ms 3632KB C++

/**
 * @author      Moe_Sakiya      i@tun.moe
 * @date        2018-07-30 23:58:37
 *
 */
 
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, i, j;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        if (n % 2 == 0) {
            printf("possible\n");
            for (i = 0; i < n; i++) {
                for (j = 0; j < i; j++) {
                    putchar('1');
                    if (j != n - 1)
                        putchar(' ');
                }
                if (j < n / 2)
                    putchar('0');
                else
                    printf("-1");
                if (j != n - 1)
                    putchar(' ');
                j++;
                for (; j < n; j++) {
                    printf("-1");
                    if (j != n - 1)
                        putchar(' ');
                }
                putchar('\n');
            }
        } else
            printf("impossible\n");
    }
    return 0;
}

添加新评论

captcha
请输入验证码