CF1521E Nastia and a Beautiful Matrix

· · 题解

My blog

其实这题并不需要排序，下面会给出证明

答案满足单调性，可以通过二分找出边长 len。如下图所示将网格染成四种颜色：

（图片的markdown好像挂了？就是官方题解里的图，也可以在这里看）

饱和的情况就是把所有非白色的格子都填上数，共 S=len^2-\lfloor \frac{len}{2} \rfloor^2 个，那么二分第一个条件是 S\ge\sum a_i

然后考虑众数 x，为了满足对角线不重复，它最多只能放在蓝色和红(或黄)色的格子里，共 T=len\times \lceil \frac{len}{2} \rceil 个，需满足 T\ge a[x]

对于满足以上两个条件的 len，一定可以构造出一个解，方法如下：

把所有数排成一列，相同的数排在一起，x 排在最前面，其他数顺序随意，然后先往红格子放，红的放完了放蓝的，最后放黄的。

简单的证明一下所有 2\times 2 对角线不重复：所有对角线都由一个黄的一个红的组成，进行分类，

1、如果 x 填满了红格子，并且根据二分条件 x 最多填满蓝的，不会填到黄的，所以黄和红不重复

2、如果 x 没填满红格子，若出现重复，则存在一个 y，在红格子里填了，又填满了蓝的，还得填黄的。而格子数量 蓝 \ge 红，x 又是众数，显然不可能

所以其他数的填放顺序根本无所谓，不需要排序。 

#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
    char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 2e5 + 5, M = 2000, NN = N * 5;
int n, s, mx, a[N], res[M][M], sr, sb, sy, id[N];
pair<int, int> r[NN], b[NN], y[NN];
#define xx first
#define yy second
int get () {
    int l = 0, r = 1000, mid, res = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (s <= mid * mid - (mid / 2) * (mid / 2) && a[1] <= mid * ((mid + 1) / 2))
            res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}
signed main() {
    int T; read (T);
    while (T--) {
        read (s), read (n); mx = 0;
        for (int i = 1; i <= n; ++i) {
            read (a[i]), id[i] = i;
            if (a[i] > a[mx]) mx = i;
        }
        id[1] = mx, id[mx] = 1; swap (a[1], a[mx]);
        int len = get (); sr = sb = sy = 0;
        for (int i = 2; i <= len; i += 2)
            for (int j = 1; j <= len; j += 2) r[++sr] = {i, j};
        for (int i = 1; i <= len; i += 2)
            for (int j = 1; j <= len; j += 2) b[++sb] = {i, j};
        for (int i = 1; i <= len; i += 2)
            for (int j = 2; j <= len; j += 2) y[++sy] = {i, j};
        for (int i = 1; i <= len; ++i)
            for (int j = 1; j <= len; ++j) res[i][j] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= a[i]; ++j) {
                if (sr) res[r[sr].xx][r[sr].yy] = id[i], --sr;
                else if (sb) res[b[sb].xx][b[sb].yy] = id[i], --sb;
                else res[y[sy].xx][y[sy].yy] = id[i], --sy;
            }
        }
        printf ("%d\n", len);
        for (int i = 1; i <= len; ++i) {
            for (int j = 1; j <= len; ++j) printf ("%d ", res[i][j]); puts ("");
        }
    }
    return 0;
}