题解：P11912 [PA 2025] 集合 2 / Zbiory 2

gcx12012 · 2025-03-27 10:12:05 · 题解

前言

小清新构造题。

Solution

首先设当前集合为 S，目标集合为 T，初始时 S 为空集。

我们将 x 从小到大依次考虑，如果 x\in S 且 x\in T，或者 x\not\in S 且 x\not\in T 就不管。否则我们分两类讨论：

• 当 x\in S 且 x\not\in T 时，考虑如何删除元素 x。这时我们可以通过 3 操作将集合变为 U 的补集，然后与 A_x 取并之后再取一次补集即可。
• 否则，直接 S\cup A_i\to S 即可。

直接做的操作次数最多是 3n 次的，考虑如何优化。

我们发现集合 S 在每一次考虑时只有两种状态，于是我们平衡一下即可做到最多 2n 次操作。

以下代码最多进行 2n+1 次操作，但是能过。

Code

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 500010
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define mk make_pair
#define pb emplace_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
struct node{
    int op,x,y;
};
vector<node >ans;
int a[N],b[N];
int n,k,now=0;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    n=read(),k=read();
    For(i,1,k) a[read()]=1;
    int m=n;
    m++;
    ans.pb((node){3,1,0});
    For(i,1,n){
        if(!b[i] && a[i]){
            if(now){
                now^=1;
                m++;
                ans.pb((node){3,m-1,0});
            }
            for(int j=i;j<=n;j+=i) b[j]=1;
            ans.pb((node){1,m,i});
            m++;
        }else if(b[i] && !a[i]){
            if(!now){
                now^=1;
                m++;
                ans.pb((node){3,m-1,0});
            }
            for(int j=i;j<=n;j+=i) b[j]=0;
            ans.pb((node){1,m,i});
            m++;
        }
    }
    if(now){
        now^=1;
        m++;
        ans.pb((node){3,m-1,0});
    }
    cout<<(int)ans.size()<<endl;
    for(node i:ans){
        if(i.op==3) cout<<i.op<<' '<<i.x<<endl;
        else cout<<i.op<<' '<<i.x<<' '<<i.y<<endl;
    }
    return 0;
}
/*

*/