AT_abc433_e

jojo222 · 2025-11-30 06:39:14 · 题解

热烈庆祝场切蓝。

思路

首先给出的 max 肯定是矩阵中存在的，且是最大的。

然后我们就可以先填 max。

• 如果行和列都存在，直接填那；
• 如果只有行存在，那么选一个满足 X_i<Y_j 的格子填入 X_i；
• 如果只有列存在，同上。

剩下的空位按照 \min(X_i,Y_j) 从小到大排序，剩下的数从小到大依次贪心填入。

为什么在只有行存在，那么选一个满足 X_i<Y_j 的格子填入 X_i 呢？因为 X_i<Y_j，所以所有候选格子的 \min(X_i,Y_j) 相同，后续填入没有影响。

最后判断是否可行。很简单，因为填的已经最优了，按照题目原样判断即可。

核心代码

const int N=2e5+5;
int t, n, m, a[N], b[N], c[N], x[N], y[N];
bool vis[N];
int id(int x, int y) { return (x - 1) * m + y; }
bool cmp(int x, int y) { return a[x] < a[y]; }
bool check()
{
    memset(vis, 0, sizeof vis);
    rep(i, 1, n) rep(j, 1, m)
        if(vis[b[id(i, j)]]) return 0;
        else vis[b[id(i, j)]] = 1;
    rep(i, 1, n)
    {
        int mx = 0;
        rep(j, 1, m) mx = max(mx, b[id(i, j)]);
        if(mx != x[i]) return 0;
    }
    rep(i, 1, m)
    {
        int mx = 0;
        rep(j, 1, n) mx = max(mx, b[id(j, i)]);
        if(mx != y[i]) return 0;
    }
    return 1;
}
int main()
{
    read(t);
    while(t--)
    {
        read(n, m), readArr(x, n), readArr(y, m);
        memset(b, 0, sizeof b);
        memset(vis, 0, sizeof vis);
        rep(i, 1, n) rep(j, 1, m) a[id(i, j)] = min(x[i], y[j]), c[id(i, j)] = id(i, j);
        rep(i, 1, n) rep(j, 1, m)
            if(x[i] == y[j]) { b[id(i, j)] = x[i], vis[x[i]] = 1; break; }
        rep(i, 1, n) rep(j, 1, m)
            if(x[i] < y[j] && !vis[x[i]]) { b[id(i, j)] = x[i], vis[x[i]] = 1; break; }
        rep(i, 1, m) rep(j, 1, n)
            if(y[i] < x[j] && !vis[y[i]]) { b[id(j, i)] = y[i], vis[y[i]] = 1; break; }
        sort(Rng(c, n*m), cmp);
        int cnt = 1;
        rep(i, 1, n*m)
        {
            if(vis[b[c[i]]]) continue;
            while(vis[cnt]) cnt++;
            b[c[i]] = cnt++;
        }
        bool f = check();
        Flag(f);
        if(f) rep(i, 1, n)
            {
                rep(j, 1, m) write(b[id(i, j)], ' ');
                write('\n');
            }
    }
    return 0;
}