密码游戏

Posted on In

题目大意：YJC 很喜欢玩游戏，今天他决定和朋友们玩密码游戏。 密码游戏的规则是这样的：初始时有两个大小为 m 的数组a 和b，分别是 0~m-1 的一个排列。每 一次操作在 0~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
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

const int N = 66, G = 1e5 + 66;

int a[N], b[N]; bool aa[N], bb[N], key; //在a中某一个数是否被使用过
int n, m, cnt, dx, dy;
int x[G], y[G], head[N];

int re[30][30]; //对应关系, re[i][j]表示a[i]对应的b[(a[i]+j)%m]等于多少

void Print_res()
{
    for (int i = 0; i < m; i ++) printf("%d ", a[i]);
    printf("\n");
    for (int i = 0; i < m; i ++) printf("%d ", b[i]);
    return;
}

void dfs(int t) //在a中填数,记录a[]与b[]的对应关系,在a中填一个数就把有对应关系的数全部填上
{
    if (t == m) return (void)(key = 1, Print_res());
    for (int k = 0; k < m; k ++)
    {
        if (aa[k]) continue;
        a[t] = k;
        bool ok = 1; //填这个数是否可行
        bool temp[30] = {0}; //记录哪些数是这一次新填入的　回溯时便于区分
        for (int e = 0; e < m; e ++)
        {
            if (re[t][e] == -1) continue;
            int v = (a[t] + e) % m;
            int val = re[t][e]; //要填的数
            //先看能不能填这个数　先不要往里面填数
            if ((b[v] == -1 && bb[val] == 0) || b[v] == val);
            else {ok = 0;break;}
        }
/*
    printf("在第%d位上填%d　ok=%d ",t,k,ok);
    printf("a=");
    for (int i=0;i<m;i++) printf("%d ",a[i]);
    printf("b=");
    for (int i=0;i<m;i++) printf("%d ",b[i]);
    printf("\n");
*/
        if (ok == 0) continue;
        aa[k] = 1;
        for (int e = 0; e < m; e ++)
        {
            if (re[t][e] == -1) continue;
            int v = (a[t] + e) % m;
            int val = re[t][e];
            if (b[v] == -1)
            {
                b[v] = val;
                bb[val] = 1;
                temp[v] = 1; //说明这个数是这次新填入的
            }
        }
        dfs(t + 1);
        if (key) return;
        for (int i = 0; i < m; i ++)
        {
            if (temp[i]) {
                bb[b[i]] = 0;
                b[i] = -1; //回溯　删除这一次新填的数　但是不能删除以前填过的而在这一次又满足条件的数
            }
        }
        aa[k] = 0;
    }
    return;
}

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) x[i] = read();
    for (int i = 1; i <= n; i ++) y[i] = read();
    for (int i = 0; i < m; i ++) a[i] = b[i] = -1; //未填数
    memset(re, -1, sizeof(re));
    while (cnt < n)
    {
        ++ cnt;
        re[(x[cnt] + dx) % m][dy] = y[cnt];
        ++ dx;
        if (dx == m) dx = 0, ++ dy;
        if (dy == m) dy = 0;
    }
    dfs(0);
    return 0;
}