自动搬运

查看原文

来自洛谷，原作者为

	meyi 明日黄花

搬运于2025-08-24 22:53:29，当前版本为作者最后更新于2023-12-21 13:58:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不会做，但是乱搞过了。

直接分治乘或合并果子面对五十万个 1 要操作九百九十七万次，几乎是题目限制的两倍，但这已经是前两个操作的最优结果，所以考虑用第三个操作进行优化。

有一个很 naive 的想法是把所有长度为二的连续段的第一个元素用操作一构造出来，再用操作三平移构造第二个元素，最后合并果子。在 1 很稠密的时候这个东西确实能优化很多，但是仍然会被五十万个 1 薄纱。。。

五十万个 1 疑似有点极端稠密了。。。于是我们也极端一点，把长度为三的连续段也用前述方式构造出来再合并果子，注意控制好阈值，然后这个东西薄纱五十万个 1 了。。。然后在五十万个 1 里随机加 0 拍了一千组也轻松薄纱。。。然后交上去过了。

实际上这个阈值貌似瞎取也没太大问题。

不会证也不会 hack，给出参考代码供大家薄纱。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
#ifdef ONLINE_JUDGE
static char pbuf[1000000],*p1=pbuf,*p2=pbuf,obuf[1000000],*o=obuf;
#define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (o-obuf<1000000)?(*o++=(x)):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*o++=(x))
struct flusher{~flusher(){fwrite(obuf,o-obuf,1,stdout);}}autoflush;
#endif
inline int qr(){
    int in=0;char ch;
    while(!isdigit(ch=getchar()));
    do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar()));
    return in;
}
template<class T>
void qw(T out){
    if(out>9)qw(out/10);
    putchar(out%10|48);
}
inline char gc(){
    char ch;
    while(!isupper(ch=getchar()));
    return ch;
}
int main(){
    int n=qr();
    V<char>a;
    a.reserve(n);
    char ch;
    while(!isdigit(ch=getchar()));
    do a.pb(ch);while(isdigit(ch=getchar()));
    V<V<int>>ans;
    V<int>siz;
	auto cmp=[&](int x,int y){return siz[x]>siz[y];};
    priority_queue<int,V<int>,decltype(cmp)>q(cmp);
    if(count(ALL(a),49)>=300000){
    	priority_queue<int,V<int>,decltype(cmp)>_q(cmp);
		For(i,n-2)if((a[i]^48)&&(a[i+1]^48)&&(a[i+2]^48))a[i]=a[i+1]=a[i+2]=48,ans.pb({1,i+1}),siz.pb(1),_q.push(ans.size()-1);
		while(_q.size()>1){
			int x=_q.top();_q.pop();
			int y=_q.top();_q.pop();
			ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),_q.push(ans.size()-1);
		}
		int nw=ans.size();
		ans.pb({3,nw,1}),siz.pb(siz[nw-1]);
		ans.pb({3,nw+1,1}),siz.pb(siz[nw]);
		ans.pb({2,nw,nw+1}),siz.pb(siz[nw-1]+siz[nw]);
		ans.pb({2,nw+2,nw+3}),siz.pb(siz[nw+1]+siz[nw+2]);
		q.push(nw+3);
	}
	if(count(ALL(a),49)>=150000){
    	priority_queue<int,V<int>,decltype(cmp)>_q(cmp);
		For(i,n-1)if((a[i]^48)&&(a[i+1]^48))a[i]=a[i+1]=48,ans.pb({1,i+1}),siz.pb(1),_q.push(ans.size()-1);
		while(_q.size()>1){
			int x=_q.top();_q.pop();
			int y=_q.top();_q.pop();
			ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),_q.push(ans.size()-1);
		}
		int nw=ans.size();
		ans.pb({3,nw,1}),siz.pb(siz[nw-1]);
		ans.pb({2,nw,nw+1}),siz.pb(siz[nw]<<1);
		q.push(nw+1);
	}
	For(i,n)if(a[i]^48)ans.pb({1,i+1}),siz.pb(1),q.push(ans.size()-1);
	while(q.size()>1){
		int x=q.top();q.pop();
		int y=q.top();q.pop();
		ans.pb({2,x+1,y+1}),siz.pb(siz[x]+siz[y]),q.push(ans.size()-1);
	}
    qw(ans.size()),putchar(10);
    for(auto &i:ans){
        for(int j:i)qw(j),putchar(32);
        putchar(10);
    }
    return 0;
}