“蔚来杯“2022牛客暑期多校训练营（加赛） K.Killer Sajin‘s Matrix

原题链接

传送门

题目大意

给定 $n,m,k$，求大小为 $n\times m$的 $01$ 矩阵 $a$ ，满足

• 每行每列总和为奇数；
• 恰好有 $k$ 个 $1$ ， $nm-k$ 个 $0$ ；

题解

这是一道构造题，考虑每行每列总和为奇数，所以每行每列所对应的 $1$ 的个数必然大于等于 $1$ ，贪心的思想，我们先考虑在坐标 $(i,i)$ 上放上 $1$ ，贪心的使得每一行列的初始值均为 $1$ ，然后再将剩下的均匀两个两个分配给每一行/列。
考虑，每一行的值 $h_i$ 所对应的列值 $w_i$ ，
显然的，对于当前的 $w_i$ ，我们需要找到一个已填个数最大的值去对应，用优先队列维护即可，
同样的，对于列中数字的选择，我们也要从大到小来枚举。
特例：

• 当 $n,m$ 都为奇数且 $k=nm-2$ 时，我们发现，对于一个全是 $1$ 的矩阵，无法满足删去一个数后使得行列同时减一来满足条件；
• 当 $k<max(n,m)$ 时，显然无法使得每行每列至少有一个数字；
• 当 $n,m,k$ 的奇偶性中有两个不同时，我们发现无法使得为奇数；

特判即可。
计算完我们可以发现，将剩余的值平均分配给每一行/列构造的序列是最优解，因为 $2x+1,2x-1$ 的情况中包含着 $2x+3,2x-3$ ， 若当前不满足，则其他构造方法必然不满足。

参考代码

#include
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m,k,T;
int h[N],w[N];
int main()
{
    cin>>T;
    while(T--)
    {
        int b=0;
        scanf("%d%d%d",&n,&m,&k);
        if(n&1 && m&1 && n*m-2==k || ((n&1)+(m&1)+(k&1))%3!=0 || k<max(n,m))    //特判
        {
            puts("No");
            continue;
        }
        int t=k-n,tot=1;
        for(int i=1;i<=n;i++)
            h[i]=1;
        for(int i=1;i<=m;i++)
            w[i]=1;
        while(t)                    //构造一段序列使得其为2x+1,2x+1...2x-1,2x-1使得尽可能平均
        {
            h[tot]+=2;
            t-=2;
            tot%=n;
            tot++;
        }
        t=k-m,tot=1;
        while(t)
        {
            w[tot]+=2;
            t-=2;
            tot%=m;
            tot++;
        }
        priority_queue<pair<int,int> > q;               //用优先队列维护最大值
        queue<pair<int,int> > q1;
        vector<pair<int,int> > ans;
        for(int i=1;i<=n;i++)
            q.push(make_pair(h[i],i));
        for(int i=1;i<=m;i++)
        {
            while(w[i])              //从大到小枚举列值
            {
                w[i]--;
                if(q.empty())
                {
                    b=1;
                    break;
                }
                pair<int,int> now=q.top();            //行值
                q.pop();
                ans.push_back(make_pair(now.second,i));
                now.first--;
                if(now.first)
                    q1.push(now);
            }
            if(b)
                break;
            while(q1.size())
            {
                q.push(q1.front());
                q1.pop();
            }
        }
        if(b)
        {
            puts("No");
            continue;
        }
        puts("Yes");
        for(int i=0;i<ans.size();i++)
            cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
}
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