P9333 [JOIST 2023] 议会 / Council题解

P9333 [JOIST 2023] 议会 / Council题目背景本题子任务编号如果为 0 表示样例如果是非 0 的一位数表示满足对应的子任务如果是两位数表示同时满足这两个子任务。题目描述题目翻译在 JOI 市议会中有NNN名议员编号从111到NNN。议会将召开会议议员们将对MMM项提案进行表决编号为111到MMM。如果Ai,j1A_{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,j0A_{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 \ MNMA1,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输入 #13 3 1 0 0 1 1 0 1 1 1输出 #13 3 2输入输出样例 #2输入 #24 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输出 #25 4 6 6输入输出样例 #3输入 #316 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输出 #33 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0输入输出样例 #4输入 #44 2 1 0 0 1 1 1 1 1输出 #42 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×1051≤M≤201 \le M \le 201≤M≤200≤Ai,j≤10 \le A_{i, j} \le 10≤Ai,j​≤1保证所有输入均为整数。子任务编号分值限制111888N≤300N \le 300N≤300222888N≤3000N \le 3000N≤3000333666M≤2M \le 2M≤2444191919M≤10M \le 10M≤10555151515M≤14M \le 14M≤14666222222M≤17M \le 17M≤17777222222无思路FWT即可。代码见下#includebits/stdc.husingnamespacestd;intn,m,a[300005][21],nu[21],b[300005],a2[2005][2005],n2,su0,tu0,op[300005],ct[2005],ob(110)-1;intabc(inta1){intdb0;while(a1!0){dba1%2;a1/2;}returndb;}voidci(inta1){intx1a1ob;inty1(a110);for(inti0;iob;i){a2[i][y1]min(a2[i][y1],ct[ix1]);}return;}intco(inta1){intx1a1ob;inty1(a110);intdbdb1e97;for(inti0;iob;i){dbdbmin(dbdb,a2[x1][i]ct[y1i]);}returndbdb;}intmain(){cinnm;for(inti0;iob;i){ct[i]abc(i);}for(inti1;in;i){for(intj1;jm;j){cina[i][j];if(a[i][j]1){nu[j-1];b[i](1(j-1));}}}memset(a2,62,sizeof(a2));n2n/2;ci(b[1]);for(inti2;in;i){sutu0;for(intj0;jm-1;j){if(((b[i]j)1)1){nu[j]--;}}for(intj0;jm-1;j){if(nu[j]n2){su;}if(nu[j]n2){tu(1(j));}}op[i]max(op[i],su-co(tu));for(intj0;jm-1;j){if(((b[i]j)1)1){nu[j];}}ci(b[i]);}memset(a2,62,sizeof(a2));n2n/2;ci(b[n]);for(intin-1;i1;i--){sutu0;for(intj0;jm-1;j){if(((b[i]j)1)1){nu[j]--;}}for(intj0;jm-1;j){if(nu[j]n2){su;}if(nu[j]n2){tu(1(j));}}op[i]max(op[i],su-co(tu));for(intj0;jm-1;j){if(((b[i]j)1)1){nu[j];}}ci(b[i]);}for(inti1;in;i){coutop[i]endl;}return0;}