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}。

构造(n+m)(n+m)(n+m)个集合A1,A2,…,An+mA_1,A_2,\ldots,A_{n+m}A1​,A2​,…,An+m​：

1. 对于1≤i≤n1\le i\le n1≤i≤n，AiA_iAi​里的元素为UUU中iii的倍数。
2. 对于n+1≤i≤n+mn+1\le i\le n+mn+1≤i≤n+m，给定参数opiop_iopi​：

• 当opi=1op_i=1opi​=1时，给定参数x,yx,yx,y（x,y<n+ix,y\lt n+ix,y<n+i），则Ai=Ax∪AyA_{i} =A_x\cup A_yAi​=Ax​∪Ay​；
• 当opi=2op_i=2opi​=2时，给定参数x,yx,yx,y（x,y<n+ix,y\lt n+ix,y<n+i），则Ai=Ax∩AyA_{i}=A_x\cap A_yAi​=Ax​∩Ay​；
• 当opi=3op_i=3opi​=3时，给定参数xxx（x<n+ix\lt n+ix<n+i），则Ai=U\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​}）。

定义问题的答案为An+mA_{n+m}An+m​。

给定正整数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中的元素。

输出格式

输出(m+1)(m+1)(m+1)行：

第一行，一个非负整数mmm。

接下来mmm行，第iii行两个或三个正整数（格式见上），描述集合An+iA_{n+i}An+i​的生成方式。

你需要保证0≤m≤1050\le m\le 10^50≤m≤105，且格式符合【题目描述】中的限制。

输入输出样例 #1

输入 #1

7 4 1 2 4 6

输出 #1

8 1 5 7 2 2 3 3 8 2 10 8 3 3 1 12 12 2 10 13 1 9 14

输入输出样例 #2

输入 #2

3 1 3

输出 #2

0

说明/提示

• 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++实现

#include<iostream>usingnamespacestd;inta[100005],b[100005],opt[150005],x[150005],y[150005];intmain(){intn,k;cin>>n>>k;intti=n+1;for(inti=1;i<=k;i++){intp;cin>>p;b[p]=1;}opt[ti]=3;x[ti]=1;for(inti=1;i<=n;i++){if(a[i]==b[i])continue;if(a[i]==0){opt[ti+1]=1;x[ti+1]=ti;y[ti+1]=i;ti++;for(intj=i;j<=n;j+=i)a[j]=1;}else{opt[ti+1]=3;x[ti+1]=i;opt[ti+2]=2;x[ti+2]=ti+1;y[ti+2]=ti;ti+=2;for(intj=i;j<=n;j+=i)a[j]=0;}}cout<<ti-n<<endl;for(inti=n+1;i<=ti;i++){cout<<opt[i]<<" "<<x[i]<<" ";if(opt[i]!=3)cout<<y[i];cout<<endl;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容