快速进步的最好方法是
查看原帖
快速进步的最好方法是
1252534
mc_nxd楼主2024/11/25 09:52

帮我调了这道题。

祝大家NOIP RP++!(滑稽

因为看不懂题解就只好来讨论区了

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
deque<int> dq[350];
int dqsiz[350],cur,freedq;
//双端队列模拟栈  cur表示单词current目前操作的栈  freedq表示空闲栈
int t,n,m,k; 
//就是输入的那些变量
int a[1000000]; 
//输入的卡牌数组
vector<pair<int,int> > ans; 
//记录ans,至于如何记录的,见下文输出
void cam(int fi,int se){
	ans.push_back(make_pair(fi,se)); 
	//写了一个函数方便记录ans,同时增加可读性
}
int main(){
	// freopen("meow2.in","r",stdin);
	// freopen("meow2.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		memset(dqsiz,0,sizeof(dqsiz));
		memset(a,0,sizeof(a));
		for(int i=1;i<=349;i++){
			while(!dq[i].empty()){
				dq[i].pop_front();
			}
		}
		// ↑这些就是初始化,将数组都清空
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=m;i++){
			cin>>a[i];
		}
		//下面这个n==1特判
		if(n==1){
			for(int i=1;i<=m;i++){
				cout<<"1 1\n";
			}
			continue;
		}
		cur=1,freedq=n;//初始化这两个变量
		for(int i=1;i<=m;i++){
			//--------------↓这个循环里头的是找能消除的两个栈底,提前消除
			for(int j=1;j<=n;j++){
				for(int k=j+1;k<=n;k++){
					if(!dq[j].empty()&&!dq[k].empty()&&dq[j].back()==dq[k].back()){
						dq[j].pop_back();
						dq[k].pop_back();
						cam(j,k);//cam做记录
					}
				}
			}
			//---找空闲栈↓---
			for(int j=1;j<=n;j++){
				if(dqsiz[j]==0){
					freedq=j;
					break;
				}
			}
			bool isbreak=0;//接下来我是否要停下
			for(int j=1;j<=n;j++){
				if(dq[j].empty())continue;
				int tmp=dq[j].front();
				if(tmp==a[i]){ //如果某一个栈顶和当前要放入的元素相同,就直接消除
					dq[j].pop_front();
					dqsiz[j]--;
					isbreak=1; //然后break
					cam(0,j);
					break;
				}
			}
			if(isbreak)continue; //到这里continue
			isbreak=0;
			for(int j=1;j<=n;j++){
				if(dq[j].empty())continue;
				int tmp=dq[j].back();
				if(tmp==a[i]){ //如果某一个栈底和当前要放入的元素相同,就直接消除
					dq[j].pop_back();
					dqsiz[j]--;
					isbreak=1; //然后break
					cam(0,freedq);
					cam(j,freedq);
					break;
				}
			}
			if(isbreak)continue;
			if(dqsiz[cur]<2){ //如果当前栈的大小小于2
				dq[cur].push_front(a[i]);
				dqsiz[cur]++;
				cam(0,cur);
			}
			else if(cur<=n-1){ //否则如果我当前栈不等于n
				cur=1;
				while(dqsiz[cur]>=2&&cur<=n){
					cur++;
				}
				dq[cur].push_front(a[i]);
				dqsiz[cur]++;
				cam(0,cur);
			}
			else{ //否则分类讨论
				int nxt=a[i+1],pos=0;
				isbreak=0;
				for(int j=1;j<=n;j++){
					if(dq[j].empty())continue;
					int tmp=dq[j].back();
					if(tmp==nxt){ //如果下一个要放入的牌和某一个栈底相同
						pos=j;
						isbreak=1;
						break;
					}
				}
				if(isbreak){
					dq[pos].push_front(a[i]); //我就把当前牌放到目标位置的栈顶
					dqsiz[pos]++;//如果不出所料,栈的大小此时为3
					cam(0,pos);
					continue;
				}
				dq[freedq].push_front(a[i]);//那否则我就把当前牌放到空闲栈
				dqsiz[freedq]++;
				cam(0,freedq);
			}
		}
		for(int j=1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(!dq[j].empty()&&!dq[k].empty()&&dq[j].back()==dq[k].back()){ //最后再遍历一遍,能消除的都消除掉
					dq[j].pop_back();
					dq[k].pop_back();
					cam(j,k);
				}
			}
		}
		cout<<ans.size()<<'\n';//输出答案
		for(auto ed:ans){
			if(ed.first!=0) cout<<2<<" "<<ed.first<<" "<<ed.second<<'\n';
			else cout<<1<<" "<<ed.second<<'\n';
		}
		ans.clear();//清空答案数组
	}
	return 0;
}

测试点信息

我把代码的注释都加上了,求调!

2024/11/25 09:52
加载中...