P9333 [JOIST 2023] 议会 / Council题解

P9333 [JOIST 2023] 议会 / Council

题目背景

本题子任务编号如果为 0 表示样例，如果是非 0 的一位数表示满足对应的子任务，如果是两位数表示同时满足这两个子任务。

题目描述

题目翻译

在 JOI 市议会中，有NNN名议员，编号从111到NNN。议会将召开会议，议员们将对MMM项提案进行表决，编号为111到MMM。如果Ai,j=1A_{i,j}=1Ai,j​=1，则议员i(1≤i≤N)i (1≤i≤N)i(1≤i≤N)将对提案j(1≤j≤M)j (1≤j≤M)j(1≤j≤M)表决肯定票。如果Ai,j=0A_{i,j}=0Ai,j​=0，则议员iii将对提案jjj表决否定票。

JOI 市议会的程序如下所示。

• 在NNN名议员中，通过抽签随机选择主席。

• 主席将在除了主席以外的其他N−1N−1N−1名议员中选择副主席。

• 将对MMM项提案进行表决。除了主席和副主席以外的其他N−2N−2N−2名议员，每人对每个提案均投票支持或反对。如果大多数议员（即肯定票大于等于⌊N2⌋⌊\dfrac{N}{2}⌋⌊2N​⌋）投票赞成，则议会将批准该提案。其中⌊x⌋⌊x⌋⌊x⌋表示不超过xxx的最大整数。

市长 K 希望议会尽可能地批准更多的提案。市长 K 收集了议员的信息并知道每个议员在每个提案上的表决结果。

请编写程序，在给定议员投票信息的情况下，计算每个议员作为主席时议会可以批准的提案数量的最大可能值。

输入格式

从标准输入读取以下数据。

N MN \ MNM

A1,1 A1,2 ⋯ A1,MA_{1, 1} \ A_{1, 2} \ \cdots \ A_{1, M}A1,1​A1,2​⋯A1,M​

A2,1 A2,2 ⋯ A2,MA_{2, 1} \ A_{2, 2} \ \cdots \ A_{2, M}A2,1​A2,2​⋯A2,M​

⋮\vdots⋮

AN,1 AN,2 ⋯ AN,MA_{N, 1} \ A_{N, 2} \ \cdots \ A_{N, M}AN,1​AN,2​⋯AN,M​

输出格式

输出NNN行。输出的第iii行（1≤i≤N1≤i≤N1≤i≤N）应包含议员iii作为主席时议会可以批准的提案数量的最大可能值。

输入输出样例 #1

输入 #1

3 3 1 0 0 1 1 0 1 1 1

输出 #1

3 3 2

输入输出样例 #2

输入 #2

4 12 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0

输出 #2

5 4 6 6

输入输出样例 #3

输入 #3

16 4 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

输出 #3

3 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0

输入输出样例 #4

输入 #4

4 2 1 0 0 1 1 1 1 1

输出 #4

2 2 1 1

说明/提示

该样例满足子任务1,2,4,5,6,71, 2, 4, 5, 6, 71,2,4,5,6,7的限制。

【样例解释 #2】

该样例满足子任务1,2,5,6,71, 2, 5, 6, 71,2,5,6,7的限制。

【样例解释 #3】

该样例满足子任务1,2,4,5,6,71, 2, 4, 5, 6, 71,2,4,5,6,7的限制。

【样例解释 #4】

该样例满足所有子任务的限制。

【数据范围】

对于所有测试数据，3≤N≤3×1053 \le N \le 3 \times 10 ^ 53≤N≤3×105，1≤M≤201 \le M \le 201≤M≤20，0≤Ai,j≤10 \le A_{i, j} \le 10≤Ai,j​≤1，保证所有输入均为整数。

思路

FWT即可。

代码见下

#include<bits/stdc++.h>usingnamespacestd;intn,m,a[300005][21],nu[21],b[300005],a2[2005][2005],n2,su=0,tu=0,op[300005],ct[2005],ob=(1<<10)-1;intabc(inta1){intdb=0;while(a1!=0){db+=a1%2;a1/=2;}returndb;}voidci(inta1){intx1=a1&ob;inty1=(a1>>10);for(inti=0;i<=ob;i++){a2[i][y1]=min(a2[i][y1],ct[i&x1]);}return;}intco(inta1){intx1=a1&ob;inty1=(a1>>10);intdbdb=1e9+7;for(inti=0;i<=ob;i++){dbdb=min(dbdb,a2[x1][i]+ct[y1&i]);}returndbdb;}intmain(){cin>>n>>m;for(inti=0;i<=ob;i++){ct[i]=abc(i);}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==1){nu[j-1]++;b[i]+=(1<<(j-1));}}}memset(a2,62,sizeof(a2));n2=n/2;ci(b[1]);for(inti=2;i<=n;i++){su=tu=0;for(intj=0;j<=m-1;j++){if(((b[i]>>j)&1)==1){nu[j]--;}}for(intj=0;j<=m-1;j++){if(nu[j]>=n2){su++;}if(nu[j]==n2){tu+=(1<<(j));}}op[i]=max(op[i],su-co(tu));for(intj=0;j<=m-1;j++){if(((b[i]>>j)&1)==1){nu[j]++;}}ci(b[i]);}memset(a2,62,sizeof(a2));n2=n/2;ci(b[n]);for(inti=n-1;i>=1;i--){su=tu=0;for(intj=0;j<=m-1;j++){if(((b[i]>>j)&1)==1){nu[j]--;}}for(intj=0;j<=m-1;j++){if(nu[j]>=n2){su++;}if(nu[j]==n2){tu+=(1<<(j));}}op[i]=max(op[i],su-co(tu));for(intj=0;j<=m-1;j++){if(((b[i]>>j)&1)==1){nu[j]++;}}ci(b[i]);}for(inti=1;i<=n;i++){cout<<op[i]<<endl;}return0;}