【题解】 P1092虫食算

【题解】P1092 虫食算

老题了，很经典。

用到了一些搜索套路。

可行性剪枝,劣者靠后,随机化,\(etc......\)

搜索设参也很有技巧，设一个\(adjustment\)参数可以很方便地在两个方程之间切换。

调试递归最好在递归到下一层递归之前输出关键信息。

// luogu-judger-enable-o2

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<bitset>

#include<vector>

#include<map>

#include<ctime>

#include<cstdlib>

#include<set>

#include<bitset>

#include<stack>

#include<list>

#include<cmath>

using namespace std;

#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)

#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)

#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)

#define Max(a,b) ((a)<(b)?(b):(a))

#define Min(a,b) ((a)<(b)?(a):(b))

#define TMP template<class ccf>

#define lef L,R,l,mid,pos<<1

#define rgt L,R,mid+1,r,pos<<1|1

#define midd register int mid=(l+r)>>1

#define chek if(R<l||r<L)return

#define all 1,n,1

#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]

typedef long long ll;

TMP inline ccf qr(ccf k){

    char c=getchar();

    ccf x=0;

    int q=1;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    if(q==-1)

	x=-x;

    return x;

}

const int maxn=27;

int ans[maxn];

int arcans[maxn];

bool usd[maxn];

int data[maxn][maxn];

int n;

inline int trs(char c){

    return c-'A'+1;

}

inline bool jde(int x){

    RP(t,x+1,n){

	bool flg=0;

	RP(i,1,3)

	    if(!usd[data[t][i]])

	       flg=1;

	if(flg)

	    continue;

	int sav=ans[data[t][1]]+ans[data[t][2]];

	int to=ans[data[t][3]];

	if(sav!=to&&sav!=to-1&&sav!=to+n&&sav!=to+n-1)

	    return 1;

    }

    return 0;

}

int dx[maxn];

void dfs(int now,int pos,int adj){

    if(ans[data[n][1]]+ans[data[n][2]]>=n&&usd[data[n][1]]&&usd[data[n][2]]||jde(now))

	return;

    if(pos==3&&now==n){

	DRP(i,n-1,0){

	    register int t=dx[i];

	    if(!arcans[t]){

		usd[(data[now][3])]=1;

		ans[(data[now][3])]=t;

		arcans[t]=(data[now][3]);

		if(adj==ans[(data[now][3])]){

		    RP(t,1,n)

			cout<<ans[t]<<' ';

		    cout<<endl;

		    exit(0);

		}

		usd[(data[now][3])]=0;

		ans[(data[now][3])]=0;

		arcans[t]=0;

	    }

	}

	if(adj==ans[(data[now][3])]){

	    RP(t,1,n)

		cout<<ans[t]<<' ';

	    cout<<endl;

	    exit(0);

	}

	return;

    }

    if(pos==3){

	if(usd[(data[now][3])]){

	    if(adj==ans[(data[now][3])])

		dfs(now+1,1,0);

	    if(adj==ans[(data[now][3])]+n)

		dfs(now+1,1,1);

	}

	else{

	    DRP(i,n-1,0){

		register int t=dx[i];

		if(!arcans[t]){

		    arcans[t]=(data[now][pos]);

		    ans[(data[now][pos])]=t;

		    usd[(data[now][pos])]=1;

		    if(adj==ans[(data[now][3])])

			dfs(now+1,1,0);

		    if(adj==ans[(data[now][3])]+n)

			dfs(now+1,1,1);

		    arcans[t]=0;

		    ans[(data[now][pos])]=0;

		    usd[(data[now][pos])]=0;

		}

	    }

	}

	return;

    }

    if(usd[(data[now][pos])]){

	dfs(now,pos+1,ans[(data[now][pos])]+adj);

    }

    else{

	DRP(i,n-1,0){

	    register int t=dx[i];

	    if(!arcans[t]){

		arcans[t]=(data[now][pos]);

		ans[(data[now][pos])]=t;

		usd[(data[now][pos])]=1;

		dfs(now,pos+1,ans[(data[now][pos])]+adj);

		arcans[t]=0;

		ans[(data[now][pos])]=0;

		usd[(data[now][pos])]=0;

	    }

	}

    }

    return;

}

int main(){

    // freopen("alpha.in","r",stdin);

    // freopen("alpha.out","w",stdout);

    srand(time(NULL));

    char c;

    n=qr(1);

    RP(t,1,3){

	RP(i,1,n){

	    cin>>c;

	    data[n+1-i][t]=trs(c);

	}

    }

    RP(t,0,n-1)

	dx[t]=t;

    random_shuffle(dx,dx+n);

    dfs(1,1,0);

    return 0;

}