好题。
首先可以视为每一列 \(1\) 的个数 \(\ge a_i\)，超出的最后再无视即可。
首先先不考虑构造。考虑二分 \(k\)，考虑 Dilworth 定理，即询问是否有 \(k\) 条链覆盖所有的黑格。
可以调整使得第 \(i\) 条链的起点为 \((n - k + i, 1)\)，终点为 \((i, m)\)。
那么一条链往上走的次数都为 \(n - k\)。
因为一条链必定至少经过一遍每一列，所以不妨令 \(b_i = \max(0, a_i - k)\)。
那么也就是第 \(i\) 列需要往上走至少 \(b_i\) 次。
一个显然的必要条件是 \(\sum\limits_{i = 1}^m b_i \le k (n - k)\)。后面我们通过构造方案证明这是充要的。
贪心按链从前往后构造。对于第 \(i\) 条链，贪心地使它满足最前面的若干个上升。
容易发现此时若两条链重合就相当于 \(b_i > n - k\)，与题目条件矛盾。
所以上述条件是充要的。直接这样构造即可。
时间复杂度 \(O(nm)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, m, a[maxn], b[maxn];
inline bool check(int x) {
int s = 0;
for (int i = 1; i <= m; ++i) {
s += max(0, a[i] - x);
}
return s <= x * (n - x);
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
int l = 0, r = min(n, m), k = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
k = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%d\n", k);
vector< vector<int> > ans(n + 2, vector<int>(m + 2, 0));
for (int i = n - k + 1; i <= n; ++i) {
int x = i;
for (int j = 1; j <= m; ++j) {
ans[x][j] = 1;
while (x > i - n + k && a[j] > k) {
--a[j];
ans[--x][j] = 1;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (b[j] && ans[i][j]) {
putchar('#');
--b[j];
} else {
putchar('.');
}
}
putchar('\n');
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}