【美团杯2020】魔塔

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 786433
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
	modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
	modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
	modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
	template<class I>friend modint operator +(modint a,I b){return a+=b;}
	template<class I>friend modint operator -(modint a,I b){return a-=b;}
	template<class I>friend modint operator *(modint a,I b){return a*=b;}
	template<class I>friend modint operator /(modint a,I b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

// r b g = 0 1 2
char mp[20][20];
char str[100];
int cnt[3]={0,0,0};
void getmp(){
	int o=0;
	while(1){
		cin.getline(str,100);
		if(str[0]!='#')continue;
		int l=strlen(str);
		For(j,0,l-1)mp[o][j]=str[j];
		++o;
		if(o>1&&str[5]=='#')break;
	}
	cin.getline(str,100);
	int l=strlen(str);
	o=0;
	For(j,0,l-1)
		if(isdigit(str[j]))
			cnt[o++]=str[j]-'0';
//	cerr<<"getmap"<<endl;
}

int outc=0,lun=0;
void work(){
//	cerr<<lun<<endl;
	if(lun%3==1){
		cout<<"D"<<endl;
		return;
	}
	if(lun%3==2){
		cout<<"W"<<endl;
		return;
	}
	if(lun%3==0){
//		For(i,0,2)cerr<<cnt[i]<<' ';cerr<<endl;
		if(cnt[0])cerr<<"r";
		if(cnt[1])cerr<<"b";
		if(cnt[2])cerr<<"g";
		++outc;
		if(outc>=30000)exit(0);
		cout<<"R"<<endl;
		return;
	}
}


signed main()
{
	freopen("in.in","w",stderr);
//	cout<<99565380<<endl;
//	for(char X:qaq)getmp(),cout<<X<<endl;
//	cerr <<" done" << endl;
//	exit(0);
	while(1){
		getmp();
		++lun;
		work();
	}
	return 0;
}
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

char s[maxn]; int np=1,p;
int cnt[3];
string ret;

void skip(){
	cout<<"DWR";
	++np;
}

int gen(){
	char c=s[p]; ++p;
	if(c=='r')return 0;
	if(c=='b')return 1;
	return 2;
}

int x,y;
void Dmove(int dx,int dy){
	cout<<"move "<<dx<<" "<<dy<<endl;
	if(x!=dx){
		while(y!=5){
			if(y>5)--y,ret+="A",cout<<"A";
			else ++y,ret+="D",cout<<"D";
		}
		while(x!=dx){
			if(x>dx)--x,ret+="W",cout<<"W";
			else ++x,ret+="S",cout<<"S";
		}
	}
	while(y!=dy){
		if(y>dy)--y,ret+="A",cout<<"A";
		else ++y,ret+="D",cout<<"D";
	}puts("    qaq");
}

void move(int dx,int dy){
	//cout<<"move "<<dx<<" "<<dy<<endl;
	if(x!=dx){
		while(y!=5){
			if(y>5)--y,ret+="A";//cout<<"A";
			else ++y,ret+="D";//cout<<"D";
		}
		while(x!=dx){
			if(x>dx)--x,ret+="W";//cout<<"W";
			else ++x,ret+="S";//cout<<"S";
		}
	}
	while(y!=dy){
		if(y>dy)--y,ret+="A";//cout<<"A";
		else ++y,ret+="D";//cout<<"D";
	}//puts("    qaq");
}

void init(){
	ret="DWD";
	char c=s[p]; ++p;
	if(c=='r')ret+="WDDSS";
	if(c=='b')ret+="SDD";
	if(c=='g')ret+="DDS";
	x=11,y=5;
	cnt[0]=cnt[1]=cnt[2]=0;
	c=s[p]; ++p;
	if(c=='r')++cnt[0];
	if(c=='b')++cnt[1];
	if(c=='g')++cnt[2];
}


//rbg = 012
int nd[114][7]={
	{0,0,0,0,0,0,0},
{1,8,0,1,0   ,0,1},
{9,7,1,0,0   ,0,0},
{3,7,0,0,1   ,0,0},
{5,13,1,1,1  ,0,5},//len=5
{9,13,0,1,0  ,8,3},//len=3
{7,11,0,0,1  ,9,3},//len=3
{3,12,0,1,0  ,10,2},//len=2
{9,9,0,0,1   ,2,1},
{7,7,0,0,1   ,0,1},
{3,9,1,0,0   ,3,1}
};
int ndlen=10;

// x,y,from,to,qian,qian2
int sw[114][7]={
	 {0,0,0,0,0,0},
{3,1,0,-1,4,0},
{5,1,2,-1,5,0},
{7,1,1,-1,6,0},
{3,3,0,1,0,0},
{5,3,2,0,0,0},
{7,3,1,2,0,0},
{7,13,0,1,0,6},
{9,15,1,2,0,5},
{1,10,2,0,0,1}
};
int swlen=9;

bool ndvis[114],swvis[114];

void OK(){
//	cout<<"np: "<<np<<endl;
//	For(i,1,20)cout<<s[np+i-1];puts("");
	np=p;
	move(11,15);
//	puts("");For(_,0,10)cout<<s[np+_];puts("");
	cout<<ret;
}

bool work(){
	p=np;
	init();
	memset(ndvis,0,sizeof ndvis);
	memset(swvis,0,sizeof swvis);
	ndvis[0]=swvis[0]=1;
	while(cnt[0]+cnt[1]+cnt[2]<9){
		bool bo=0;
		For(i,1,10)
			if(!ndvis[i] && cnt[0]>=nd[i][2]&&cnt[1]>=nd[i][3]&&cnt[2]>=nd[i][4]
				&&ndvis[nd[i][5]]){
					bo=1;
					move(nd[i][0],nd[i][1]);
					ndvis[i]=1;
					if(i<=3){
						if(i==1) cnt[gen()]++;
					}else{
						cnt[0]-=nd[i][2],cnt[1]-=nd[i][3],cnt[2]-=nd[i][4];
						For(_,1,nd[i][6]) cnt[gen()]++;
					}
				//	cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
					break;
				}
		if(bo)continue;
		Rep(c,2,0)
			if(!cnt[c]){
				For(i,1,9)
					if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
						&& sw[i][3]==c){
				//			cout<<"WA: \n";
				//			cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
				//			For(_,0,5)cout<<sw[i][_]<<" ";puts("");
							bo=1;
							move(sw[i][0],sw[i][1]);
							swvis[i]=1;
							++cnt[c];
							--cnt[sw[i][2]];
				//			cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
							break;
						}
				if(bo)break;
				For(i,1,9)
					if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
						&& sw[i][3]==-1){
							bo=1;
							move(sw[i][0],sw[i][1]);
							swvis[i]=1;
							++cnt[gen()];
							--cnt[sw[i][2]];
			//				cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
							break;
						}
				if(bo)break;
				For(i,1,9)
					if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
						&& sw[i][3]==(c+2)%3){
							bo=1;
							move(sw[i][0],sw[i][1]);
							swvis[i]=1;
							++cnt[sw[i][3]];
							--cnt[sw[i][2]];
			//				cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
							break;
						}
				if(bo)break;
			}
		if(!bo)return 0;
	}
	
	//swap
	while(max(cnt[0],max(cnt[1],cnt[2]))>3){
		pii orz=mkp(-1,-1);
		For(i,0,2)orz=max(orz,mkp(cnt[i],i));
		int c=orz.se;
		bool bo=0;
		For(i,1,9)
			if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
					&& sw[i][3]==c){
						bo=1;
						move(sw[i][0],sw[i][1]);
						swvis[i]=1;
						++cnt[c];
						--cnt[sw[i][2]];
				//		cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
						break;
					}
		if(bo)continue;
			For(i,1,9)
				if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
					&& sw[i][3]==-1){
						bo=1;
						move(sw[i][0],sw[i][1]);
						swvis[i]=1;
						++cnt[gen()];
						--cnt[sw[i][2]];
				//		cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
						break;
					}
		if(bo)continue;
		For(i,1,9)
				if(!swvis[i] && cnt[sw[i][2]] && swvis[sw[i][4]] && ndvis[sw[i][5]]
					&& sw[i][2]!=c){
						if(sw[i][3]==-1)exit(1);
						bo=1;
						move(sw[i][0],sw[i][1]);
						swvis[i]=1;
						++cnt[sw[i][3]];
						--cnt[sw[i][2]];
				//		cout<<"cnt: "<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl; 
						break;
					}
		if(bo)continue;
		return 0;
	}
	
	OK();
	return 1;
}

signed main()
{
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	cin>>s+1;
//	For(i,1,10)cout<<s[i];puts("---");
For(_,1,100){

	while(!work()){
		skip(); 
	} 
}
	return 0;
}
$$\Huge \text{Goodbye OI}$$
原文地址:https://www.cnblogs.com/Rainbowsjy/p/15791091.html