「十连赛NOIPday7」密码游戏 - 搜索 | Bill Yang's Blog

「十连赛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$的初值。


题目分析

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}
姥爷们赏瓶冰阔落吧~
0%