自动搬运

查看原文

来自洛谷，原作者为

	gcx12012 每一个不曾起舞的日子，都是对生命的辜负。

搬运于2025-08-24 23:11:19，当前版本为作者最后更新于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;
}
/*

*/