• 欢迎光临~

P8866 [NOIP2022] 喵了个喵

开发技术 开发技术 2022-11-29 次浏览

(mathcal Link)

(k=2n-2):保证任意时刻每种元素只出现一次,并保留一个空栈,让其他栈大小不超过 (2) 即可。

(k=2n-1):延续上面的做法,对于多出来的第 (2n-1) 元素 (x) ,意识到空栈只在进行操作二时有用,因此考虑对下一个出现的非栈顶元素 (x') 分类讨论。

  • (x=x'):此时直接将 (x) 放入空栈。
  • (x') 上方元素在扫描过程中出现奇数次:此时将 (x) 放入空栈后,进行到 (x') 时,(x') 上方无元素,可以直接消掉后得到新的空栈。
  • 若出现偶数次:将 (x) 放在 (x') 所在栈最上方,然后将偶数次的元素放入空栈消光,用操作二消去 (x') 即可。

代码实现有难度。

#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
	x=0;int w=0;char c=GetC();
	for(;!isdigit(c);w|=c=='-',c=GetC());
	for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
	if(w) x=-x;
	return in;
}
const int N=305,M=2e6+5;
int a[M];
int is[N*2];
int sz[N],val[N][3];
struct ans_t{int op,s1,s2;};
#define pb push_back
int main(){
	int T;io>>T;
	while(T--){
		vector<ans_t> v;
		queue<int> q1,q2;
		int n,m,k;io>>n>>m>>k;
		for(int i=1;i<=m;++i) io>>a[i];
		for(int i=1;i<=n;++i) sz[i]=0,val[i][1]=val[i][2]=0;
		for(int i=1;i<n;++i) q1.push(i),q2.push(i);
		for(int i=1;i<=k;++i) is[i]=0;
		int point=n;
		for(int i=1;i<=m;++i){
			if(is[a[i]]){
				int pos=is[a[i]];
				if(val[pos][sz[pos]]==a[i]){
					v.pb({1,pos,0});
					if(sz[pos]==2) q2.push(pos);
					else q1.push(pos);
					--sz[pos];
				}
				else{
					v.pb({1,point,0});
					v.pb({2,pos,point});
					val[pos][1]=val[pos][2];
					--sz[pos];
					q2.push(pos);
				}
				is[a[i]]=0;
			}
			else{
				if(!q1.empty()){
					int pos=q1.front();q1.pop();
					v.pb({1,pos,0});
					is[a[i]]=pos;
					val[pos][++sz[pos]]=a[i];
				}
				else if(!q2.empty()){
					int pos=q2.front();q2.pop();
					v.pb({1,pos,0});
					is[a[i]]=pos;
					val[pos][++sz[pos]]=a[i];
				}
				else{
					bitset<N*2> s;
					s.reset();
					int j=i+1;
					for(;j<=m;++j){
						if(a[j]==a[i]||val[is[a[j]]][1]==a[j]) break;
						s.flip(a[j]);
					}
					int tmp=j;
					if(a[tmp]==a[i]){
						v.pb({1,point,0});
						for(j=i+1;j<tmp;++j){
							if(is[a[j]]){
								int pos=is[a[j]];
								v.pb({1,pos,0});
								--sz[pos];
								q2.push(pos);
								is[a[j]]=0;
							}
							else{
								int pos=q2.front();q2.pop();
								v.pb({1,pos,0});
								is[a[j]]=pos;
								val[pos][++sz[pos]]=a[j];
							}
						}
						v.pb({1,point,0});
					}
					else if((int)s[val[is[a[tmp]]][2]]==1){//挂了,记之
						v.pb({1,point,0});
						for(j=i+1;j<tmp;++j){
							if(a[j]==val[is[a[tmp]]][2]){
								v.pb({1,is[a[tmp]],0});
								is[a[j]]=0;
							}
							else if(is[a[j]]){
								int pos=is[a[j]];
								v.pb({1,pos,0});
								--sz[pos];
								is[a[j]]=0;
								q2.push(pos);
							}
							else{
								int pos=q2.front();q2.pop();
								v.pb({1,pos,0});
								is[a[j]]=pos;
								val[pos][++sz[pos]]=a[j];
							}
						}
						v.pb({1,is[a[tmp]],0});
						sz[point]=1;
						val[point][1]=a[i];
						q2.push(point);
						is[a[i]]=point;

						sz[is[a[tmp]]]=0;
						point=is[a[tmp]];
						is[a[tmp]]=0;
					}
					else{
						v.pb({1,is[a[tmp]],0});
						for(j=i+1;j<tmp;++j){
							if(a[j]==val[is[a[tmp]]][2]) v.pb({1,point,0});//挂了,记之。
							else if(is[a[j]]){
								int pos=is[a[j]];
								v.pb({1,pos,0});
								--sz[pos];
								is[a[j]]=0;
								q2.push(pos);
							}
							else{
								int pos=q2.front();q2.pop();
								v.pb({1,pos,0});
								is[a[j]]=pos;
								val[pos][++sz[pos]]=a[j];
							}
						}
						v.pb({1,point,0});
						v.pb({2,is[a[tmp]],point});
						int pos=is[a[tmp]];
						val[pos][1]=val[pos][2];
						val[pos][2]=a[i];
						sz[pos]=2;
						is[a[i]]=pos;
						is[a[tmp]]=0;
					}
					i=tmp;
				}
			}
		}
		printf("%dn",(int)v.size());
		for(auto tmp:v){
			if(tmp.op==1) printf("1 %dn",tmp.s1);
			if(tmp.op==2) printf("2 %d %dn",tmp.s1,tmp.s2);
		}
	}
	return 0;
}

Bug 合集:

考场代码:删除未更新 is[],插入未更新 val[]

35pts: bitset 类型未转为 int 就比较。

50pts: i,j, tmp 分不清。

程序员灯塔
转载请注明原文链接:P8866 [NOIP2022] 喵了个喵
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com