HDU 6675 度度熊与排列【2019百度之星初赛二1002】

- 日理万妓 2024-04-17 05:39 68阅读 0赞

### 题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6675 ###

## 度度熊与排列 ##

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 472    Accepted Submission(s): 151**

### Problem Description ###

度熊有一个机器，这个机器有一个 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。

### Input ###

有多组询问，第一行包含一个正整数 T 代表有几组询问。

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

\* 1≤T≤100

\* 1≤N≤20

\* 1≤M≤50

\* 字符串由英文小写字母('a' 至 'z') 组成

### Output ###

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

### Sample Input ###

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

### Sample Output ###

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。

### 解题思路： ###

以上面输出为2431为例

①定义并初始结果集。

vector<int>ret[M];
    //  // 初始集合：
    //  1 2 3 ... M
    //  1 2 3 ... M
    //      ...
    //  1 2 3 ... M
    //  此处 M 等于 4

②输入一组字符（两行），统计字符串中每个位置上的字符可以跳转的位置，存入tmp集合。

vector<int>tmp[M];
    //  遍历记下可能位置
    //  2 3 4
    //  2 3 4
    //  2 3 4
    //  1

③求 ret与 tmp交集 tmp\_ret, 然后ret = tmp\_ret

vector<int>tmp_ret[M];
    //  求交集。tmp_ret = ret 交 tmp;
    //  更新结果集。 ret = tmp_ret;
    //  ret:
    //  2 3 4
    //  2 3 4
    //  2 3 4
    //  1

④循环重复②③步骤，得到最终结果集ret。

//  ret:
    //  2 3
    //  4
    //  2 3
    //  1

⑤分析ret，贪心，找最小跳转位置，看能否得到ans。

输出时贪心的对于每个位置（1->m），输出它所能跳转的最小位置，如果有一个位置无法跳转的话，那么输出-1

# ac代码： #

#include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    #include<vector>
    using namespace std;
    
    #define  N  21
    #define  M  52
    
    char src[M][N];
    char des[M][N];
    
    vector<int>ret[M];
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	int T, n, m;
    	cin>>T;
    	while(T--){
    		memset(src, 0, sizeof(src));
    		memset(des, 0, sizeof(des));
    		for(int i=0;i<M;i++){
    			ret[i].clear();
    			for(int j=1;j<=M;j++){
    				ret[i].push_back(j);
    			} 
    		} 	
    		cin>>n>>m;
    		for(int ii=0;ii<n;ii++){
    			cin>>src[ii];
    			cin>>des[ii];
    			vector<int>tmp[M];
    			// 求可能的位置存入tmp 
    			for(int j=0;j<m;j++){
    				for(int k=0;k<m;k++){
    					if(src[ii][j]==des[ii][k]){
    						tmp[j].push_back(k+1);
    					}
    				}
    			}
    			
    			vector<int>tmp_ret[M];
    			// 求 ret与 tmp交集 
    			for(int i=0;i<m;i++){				
    				for(int j=0;j<tmp[i].size();j++){
    					int a;
    					for(a=0;a<ret[i].size();a++){
    						if(ret[i][a]==tmp[i][j]){
    							break;
    						}
    					}
    					if(a<ret[i].size()){
    						// 找到目标，tmp[i][j]属于交集元素，则存入tmp_ret 
    						tmp_ret[i].push_back(tmp[i][j]);
    					}
    				}
    				// 将tmp_ret的结果交给ret 
    				ret[i].clear();
    				sort(tmp_ret[i].begin(), tmp_ret[i].end());
    				for(int j=0;j<tmp_ret[i].size();j++){
    					ret[i].push_back(tmp_ret[i][j]);
    				}
    				tmp_ret[i].clear();	
    			}
    		}
    		
    		int vis[m+1];
    		memset(vis, 0, sizeof(vis));
    		// 求一个可能的组合 
    		vector<int>ans; 
    		for(int i=0;i<m;i++){
    			for(int j=0;j<ret[i].size();j++){
    				if(vis[ret[i][j]]==0){
    					vis[ret[i][j]]=1;
    					ans.push_back(ret[i][j]);
    					break;
    				}	
    			}	
    		} 
    		if(ans.size()!=m){
    			cout<<-1<<endl;
    		}
    		else{
    			for(int index = 0; index < m-1; index++){
    				cout<<ans[index]<<" ";
    			}
    			cout<<ans[m-1]<<endl;
    		}
    
    	}	
    	return 0;
    }

#      #