hduoj 6675 度度熊与排列 - 百度之星 2019

目录

1. 输入
2. 输出
3. 输入样例
4. 输出样例
5. 来源

题目描述 http://acm.hdu.edu.cn/showproblem.php?pid=6675

度熊有一个机器，这个机器有一个 $1 \sim M$ 的排列 $p[1..M]$ 当作参数，若丢进一个长度为 $M$ 的字符串，此机器会将此字符串重新排列后再输出，重新排列的方式为：原本第 $i$ 个位置的字符会变到第 $p[i]$ 个位置。举例来说，当 $M = 3$，$p[1]=3,p[2]=1,p[3]=2$，那么丢 “abc” 进入这个机器后，机器会输出”bca”;若丢进的是 “ded”，那么机器会输出 “edd”。某天，度熊不小心忘记这个机器的参数了，只记得参数的长度是 $M$，于是他丢了 $N$ 长度为 $M$ 的字符串进去，并记录下对于每个字符串机器的输出结果，请你根据这些结果，帮度熊找回这个机器的参数。若有多组参数都满足度熊的记录，请输出字典序最小的排列作为参数。若并不存在任何参数满足度熊的记录，请输出 $-1$。注：对于两个相异的排列a: $a[1..M]$ 和 $b[1..M]$，我们称 $a$ 比 $b$ 小当且仅当 存在一个 $i$，满足对于所有小于 $i$ 的 $j$ 都有 $a_j = b_j$ 且 $a_i < b_i$。

输入

有多组询问，第一行包含一个正整数 $T$ 代表有几组询问。每组询问的第一行包含两个正整数 $N, M$，分别代表度熊丢进机器的字符串数目以及参数的长度。接下来还有 $2 \times N$ 行，每行有一个长度为 $M$ 的字符串，当中的第 $2 \times i - 1$ 行的字符串代表度熊丢进去机器的第 $i$ 个字符串，而第 $2 \times i$ 行的字符串代表机器对于第 $i$ 个字符串的输出结果。 $1 \le T \le 100$ $1 \le N \le 20$ $1 \le M \le 50$ 字符串由英文小写字母(‘a’ 至 ‘z’) 组成

输出

对于每一个询问，输出一行，若不存在任何参数满足度熊的记录，这行只包含一个整数 $-1$。否则这行包含一个排列，代表此机器所有可能的参数中字典序最小的那个。

输入样例

4
1 3
abc
bca
2 4
aaab
baaa
cdcc
cccd
3 3
aaa
aaa
bbb
bbb
ccc
ccc
1 1
a
z

输出样例

3 1 2
2 4 3 1
1 2 3
-1

Note
第一组询问中， $p[1]=3,p[2]=1,p[3]=2$ 是唯一的机器可能的参数。

第二组询问中， $p=[2,4,3,1]$ 和 $p=[3,4,2,1]$ 都是机器可能的参数，不过 $[2,4,3,1]$ 的字典序比 $[3,4,2,1]$ 还小，故必须输出 2,4,3,1。

来源

2019 年百度之星·程序设计大赛 - 初赛二

#include <cstdio> 

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        char s[44][55];
        for (int i = 0; i < n*2; i++) {
            scanf("%s", s[i]);
        }
        int f[54], p[54];
        for (int i = 0; i < m; i++) f[i] = 0;
        bool flag_found_p = true;
        for (int i = 0; i < m; i++) {
            bool flag_found_j = false;
            for (int j = 0; j < m; j++) {
                if (f[j] == 0) {
                    bool flag_ok = true;
                    for (int k = 0; k < n; k++) {
                        if (s[k*2][i] != s[k*2+1][j]) {
                            flag_ok = false;
                            break;
                        }
                    }
                    if (flag_ok) {
                        flag_found_j = true;
                        f[j] = 1;
                        p[i] = j;
                        break;
                    }
                }
            }
            if (!flag_found_j) {
                printf("-1\n");
                flag_found_p = false;
                break;
            }
        }
        if (flag_found_p) {
            for (int i = 0; i < m-1; i++) {
                printf("%d ", p[i] + 1);
            }
            printf("%d\n", p[m-1]+1);
        }
    }
}

这个问题不需要回溯，当无法找到匹配的位置时就说明无解