「CF1521E」Nastia and a Beautiful Matrix

发表于 分类于

$Link$

你有 $m$ 个数，值域为 $[1,k]$，其中数 $i$ 有 $a_i$ 个。

你需要构造最小的 $n\times n$ 矩阵，其中包含这 $m$ 个数，剩下的位置为 $0$，并且对于任意的 $2\times2$ 子矩阵：

  • 不是 $0$ 的位置数不超过 $3$。
  • 对角线上的两个数不同。

$t$ 组数据，输出方案。

$1\le t\le10^4,1\le m,k\le10^5,\sum m,k\le2\times10^5$。

首先，显然是隔一行隔一列地放一个 $0$，这样一个 $n\times n$ 的矩阵最多可以放 $n^2-\lfloor\frac{n}{2}\rfloor^2$ 个数。

接下来需要满足对角线上的两个数不同，考虑最坏状况下，我们在每个 $2\times2$ 的子矩阵中，都在同一行或者同一列放上两个一样的数。

于是可以得到出现最多次的数的个数不能超过 $n\lceil\frac{n}{2}\rceil$。

直接枚举或者二分就可以得到最小的 $n$ 了。

至于构造方案直接按照出现次数从大到小，按照上面的方案直接填就好了。

时间复杂度 $O(tn^2)$，$n$ 最大大概是 $500$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 500;
const int M = 1e5;

int tt;
int n, m, k;
struct Node {
    int num, cnt;
    inline bool operator <(Node x) const
    {
        return cnt > x.cnt;
    }
} node[M + 1];
int w[M + 1];
int ans[N + 1][N + 1];

int main()
{
    tt = read();

    while (tt--) {
        m = read();
        k = read();
        for (int i = 1; i <= k; i++)
            node[i] = { i, read() };
        sort(node + 1, node + k + 1);
        for (int i = 1, j = 0; i <= k; i++)
            for (int k = 1; k <= node[i].cnt; k++)
                w[++j] = node[i].num;
        if (m == 1) {
            printf("1\n");
            printf("%d\n", node[1].num);
            continue;
        }
        n = 1;
        while (n * n - (n / 2) * (n / 2) < m || n * ((n + 1) / 2) < node[1].cnt)
            n++;
        printf("%d\n", n);
        memset(ans, 0, sizeof(int) * (N + 1) * (N + 1));
        int i = 1;
        for (int x = 2, y = 1; i <= m && x <= n; i++) {
            ans[x][y] = w[i];
            y += 2;
            if (y > n) {
                x += 2;
                y = 1;
            }
        }
        for (int x = 1, y = 1; i <= m && x <= n; i++) {
            ans[x][y] = w[i];
            y += 2;
            if (y > n) {
                x += 2;
                y = 1;
            }
        }
        for (int x = 1, y = 2; i <= m && x <= n; i++) {
            ans[x][y] = w[i];
            y += 2;
            if (y > n) {
                x += 2;
                y = 2;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                printf("%d ", ans[i][j]);
            printf("\n");
        }
    }

    return 0;
}