打卡信奥刷题（3634）用C++实现信奥题 P11912 [PA 2025] 集合 2 / Zbiory 2

P11912 [PA 2025] 集合 2 / Zbiory 2题目背景PA 2025 trial round t2.请注意本题非同寻常的时空限制。题目描述问题。给定正整数nnn和非负整数mmm。定义全集U{1,2,…,n}U\{1,2,\ldots,n\}U{1,2,…,n}。构造(nm)(nm)(nm)个集合A1,A2,…,AnmA_1,A_2,\ldots,A_{nm}A1​,A2​,…,Anm​对于1≤i≤n1\le i\le n1≤i≤nAiA_iAi​里的元素为UUU中iii的倍数。对于n1≤i≤nmn1\le i\le nmn1≤i≤nm给定参数opiop_iopi​当opi1op_i1opi​1时给定参数x,yx,yx,yx,ynix,y\lt nix,yni则AiAx∪AyA_{i} A_x\cup A_yAi​Ax​∪Ay​当opi2op_i2opi​2时给定参数x,yx,yx,yx,ynix,y\lt nix,yni则AiAx∩AyA_{i}A_x\cap A_yAi​Ax​∩Ay​当opi3op_i3opi​3时给定参数xxxxnix\lt nixni则AiU\AxA_{i}U\backslash A_xAi​U\Ax​即Ai{j:j∈U,j∉Ax}A_i\{j:j\in U,j\not\in A_x\}Ai​{j:j∈U,j∈Ax​}。定义问题的答案为AnmA_{nm}Anm​。给定正整数nnn和目标集合B⊆{1,2,…,n}B\subseteq \{1,2,\ldots,n\}B⊆{1,2,…,n}。构造非负整数mmm和一组对应的参数使得上述问题的答案为BBB。你需要保证0≤m≤1050\le m\le 10^50≤m≤105。可以证明本题一定有解。输入格式第一行两个正整数n,kn,kn,k其中∣B∣k|B|k∣B∣k。第二行kkk个正整数B1,B2,…,BkB_1,B_2,\ldots,B_kB1​,B2​,…,Bk​描述BBB中的元素。输出格式输出(m1)(m1)(m1)行第一行一个非负整数mmm。接下来mmm行第iii行两个或三个正整数格式见上描述集合AniA_{ni}Ani​的生成方式。你需要保证0≤m≤1050\le m\le 10^50≤m≤105且格式符合【题目描述】中的限制。输入输出样例 #1输入 #17 4 1 2 4 6输出 #18 1 5 7 2 2 3 3 8 2 10 8 3 3 1 12 12 2 10 13 1 9 14输入输出样例 #2输入 #23 1 3输出 #20说明/提示1≤n≤5×1041\le n\le 5\times 10^41≤n≤5×104;B⊆{1,2,…,n}B\subseteq \{1,2,\ldots,n\}B⊆{1,2,…,n}。C实现#includeiostreamusingnamespacestd;inta[100005],b[100005],opt[150005],x[150005],y[150005];intmain(){intn,k;cinnk;inttin1;for(inti1;ik;i){intp;cinp;b[p]1;}opt[ti]3;x[ti]1;for(inti1;in;i){if(a[i]b[i])continue;if(a[i]0){opt[ti1]1;x[ti1]ti;y[ti1]i;ti;for(intji;jn;ji)a[j]1;}else{opt[ti1]3;x[ti1]i;opt[ti2]2;x[ti2]ti1;y[ti2]ti;ti2;for(intji;jn;ji)a[j]0;}}coutti-nendl;for(intin1;iti;i){coutopt[i] x[i] ;if(opt[i]!3)couty[i];coutendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容