「十连赛NOIPday7」密码游戏 - 搜索

题目大意

$YJC$很喜欢玩游戏，今天他决定和朋友们玩密码游戏。
密码游戏的规则是这样的：初始时有两个大小为$m$的数组$a[],b[]$，分别是$0\rightarrow m-1$的一个排列。每一次操作在$0\rightarrow m-1$之间选一个数$x$，求出结果 $y=b[a[x]]$，把$x$和$y$写下来。之后，$a[]$向前循环移动一次，即$(a[0],a[1],…,a[m-2],a[m-1])$变成$(a[1],a[2],…,a[m-1],a[0])$。当$a[]$变回初始状态时，$b[]$向前循环移动一次。现在知道所有的$x$和$y$，如果 $YJC$能求出任意一组符合条件的$a$和$b$的初值，$YJC$就赢了。
$YJC$很想赢得游戏，但他太笨了，他想让你帮他算出$a$和$b$的初值。

---

题目分析

暴力出奇迹，直接爆搜，每一次检查选择排列是否被使用过。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=35;
int n,m,a[maxn],b[maxn],x[100005],y[100005],rev[maxn],vst[maxn];
struct Edge {
	int from,to,v;
};
vector<Edge>edges[maxn];
bool Hash[maxn][maxn];
void AddEdge(int x,int y,int v) {
	if(Hash[x][y])return;
	edges[x].push_back((Edge) {
		x,y,v
	}); 
	Hash[x][y]=1;
}
void Dfs(int Depth) {
	if(Depth==m) {
		for(int i=0; i<m; i++)b[rev[i]]=i;
		for(int i=0; i<m; i++)printf("%d ",a[i]);
		putchar('\n');
		for(int i=0; i<m; i++)printf("%d ",b[i]);
		exit(0);
	}
	int tmprev[maxn];
	memcpy(tmprev,rev,sizeof(rev));
	for(int x=0; x<m; x++) {
		if(vst[x])continue;
		bool bj=1;
		for(Edge& e:edges[Depth]) {
			int Next=e.to,v=e.v,t=(x+v)%m;
			if(rev[Next]!=-1&&rev[Next]!=t) {
				bj=0;
				break;
			}
		}
		if(!bj)continue;
		vst[x]=1;
		a[Depth]=x;
		for(Edge& e:edges[Depth]) {
			int Next=e.to,v=e.v,t=(x+v)%m;
			rev[Next]=t;
		}
		Dfs(Depth+1);
		vst[x]=0;
		a[Depth]=-1;
		memcpy(rev,tmprev,sizeof(tmprev));
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)x[i]=Get_Int();
	for(int i=1; i<=n; i++)y[i]=Get_Int();
	for(int i=1; i<=n; i++)AddEdge((x[i]+i-1)%m,y[i],(i-1)/m);
	memset(a,-1,sizeof(a));
	memset(rev,-1,sizeof(rev));
	Dfs(0);
	return 0;
}