6675. 度度熊与排列

6675. 度度熊与排列

 
  HDOJ
  ,
  9 分钟 读完 (大约 1289 个字)   0次访问

HDOJ 6675. 度度熊与排列

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

题目：6675. 度度熊与排列

问题描述：

度熊有一个机器，这个机器有一个 1∼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 都有 aj=bj 且 ai<bi。

输入：

有多组询问，第一行包含一个正整数 T 代表有几组询问。
每组询问的第一行包含两个正整数 N,M，分别代表度熊丢进机器的字符串数目以及参数的长度。接下来还有 2×N 行，每行有一个长度为 M 的字符串，当中的第 2×i−1 行的字符串代表度熊丢进去机器的第 i 个字符串，而第 2×i 行的字符串代表机器对于第 i 个字符串的输出结果。
1≤T≤100
1≤N≤20
1≤M≤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

注意：

第一组询问中， $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。

方法：枚举

思路：先确定第一个字符串的第一个机器参数，再判断其他字符串是否满足该机器参数，满足则继续确定第一个字符串的下一个机器参数，否则将重新确定第一个字符串的第一个机器参数，且从刚刚的位置开始找，若找不到其他的机器参数则认为其没有满足条件的机器参数，直接结束，若找到了，依次类推继续判断其他字符串是否满足这个机器参数。

运行数据：执行用时：343MS，内存消耗：11356K

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
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {

            int n = sc.nextInt();
            int m = sc.nextInt();
            String instr[] = new String[n];
            String outstr[] = new String[n];
            for (int i = 0; i < n; i++) {
                instr[i] = sc.next();
                outstr[i] = sc.next();
            }
            fun(instr, outstr, n, m);
        }
    }

    private static void fun(String[] instr, String[] outstr, int n, int m) {
		
        // 记录机器参数
        int result[] = new int[m];

        // 标记第一字符串已确定为机器参数的输出字符串序号
        boolean flag[] = new boolean[m];

        // 记录第一个输出字符串的位置
        int number = 0;

        // 搜索每个位置的机器参数
        for (int i = 0; i < m; i++) {

            // 搜索第一个字符串的机器参数
            boolean searchFlag = false;
            for (int k = number; k < m; k++) {
                if (instr[0].charAt(i) == outstr[0].charAt(k) && !flag[k]) {
                    number = k + 1;
                    searchFlag = true;
                    break;
                }
            }

            // 判断是否有机器参数
            if (!searchFlag) {
                System.out.println("-1");
                return ;
            }

            // 遍历除第一个字符串外的其他字符串是否都满足第一个字符串的机器参数
            boolean tempFlag = false;
            for (int j = 1; j < n; j++) {
                if (instr[j].charAt(i) != outstr[j].charAt(number - 1)) {
                    tempFlag = true;
                    break;
                }
            }

            // 满足则继续寻找下一个机器参数，否则重新确定当前位置的机器参数
            if (!tempFlag) {
                result[i] = number;
                flag[number - 1] = true;
                number = 0;
            } else {
                i--;
            }
        }

        // 输出结果
        for (int i = 0; i < m; i++) {
            System.out.print(result[i]);
            if (i == m - 1) {
                System.out.println();
            } else {
                System.out.print(" ");
            }
        }
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！

  , 

喜欢这篇文章？打赏一下作者吧

215. 数组中的第K个最大元素
6674. 度度熊与数字
关注我
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×