题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6675
题目:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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。
解题思路:
签到题之二。
对于每次输入的字符,根据对应的输出字符,记录每个位置上的字符可以跳转的位置。
对n组数据,统计字符串中每个位置上的字符可以跳转的共同位置,输出时贪心的对于每个位置(1->m),输出它所能跳转的最小位置,如果有一个位置无法跳转的话,那么输出-1
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100020;
typedef long long ll;
char s1[55], s2[55];
vector<int> pos[25][55], ans, cur;
int vis[100];
void init()
{
memset(vis, 0, sizeof vis);
ans.clear();
for(int i = 0; i < 25; i++)
for(int j = 0; j < 55; j++)
pos[i][j].clear();
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t, n, m;
scanf("%d", &t);
while(t--)
{
init();
scanf("%d %d", &n, &m);
bool flag = true;
for(int k = 0; k < n; k++)
{
scanf("%s", s1); scanf("%s", s2);
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
if(s1[i] == s2[j])
pos[k][i].push_back(j);//s2中和s1[i]相同的字符的位置
/*for(int i = 0; i < m; i++)
{
printf("xxx%d:", i);
for(int j = 0; j < pos[k][i].size(); j++)
printf(" %d ", pos[k][i][j]);
cout << endl;
}*/
if(k == 0) continue;
for(int id = 0; id < m; id++)
{
cur.clear();
for(int i = 0; i < pos[k][id].size(); i++)
{
int find = 0;
for(int j = 0; j < pos[k-1][id].size(); j++)
{
if(pos[k][id][i] == pos[k-1][id][j])
{
find = 1;
break;
}
}
if(find) cur.push_back(pos[k][id][i]);
}
pos[k][id].clear();
for(int i = 0; i < cur.size(); i++)
pos[k][id].push_back(cur[i]);//只保留共有的
}
}
n--;
for(int i = 0; i < m; i++)
sort(pos[n][i].begin(), pos[n][i].end());
for(int i = 0; i < m; i++)
{
for(int j = 0; j < pos[n][i].size(); j++)
{
if(!vis[pos[n][i][j]])
{
vis[pos[n][i][j]] = 1;
ans.push_back(pos[n][i][j]);
break;
}
}
}
if(ans.size() != m) flag = false;
if(!flag) printf("-1\n");
else
{
//cout << "ans:";
for(int i = 0; i < m; i++)
{
if(i) printf(" ");
printf("%d", ans[i]+1);
}
printf("\n");
}
}
return 0;
}