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,1A1,2⋯A1,M
A2,1 A2,2 ⋯ A2,MA_{2, 1} \ A_{2, 2} \ \cdots \ A_{2, M}A2,1A2,2⋯A2,M
⋮\vdots⋮
AN,1 AN,2 ⋯ AN,MA_{N, 1} \ A_{N, 2} \ \cdots \ A_{N, M}AN,1AN,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，保证所有输入均为整数。
| 子任务编号 | 分值 | 限制 |
|---|---|---|
| 111 | 888 | N≤300N \le 300N≤300 |
| 222 | 888 | N≤3000N \le 3000N≤3000 |
| 333 | 666 | M≤2M \le 2M≤2 |
| 444 | 191919 | M≤10M \le 10M≤10 |
| 555 | 151515 | M≤14M \le 14M≤14 |
| 666 | 222222 | M≤17M \le 17M≤17 |
| 777 | 222222 | 无 |
思路
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;}
