传话游戏
时间限制: 1000ms 内存限制: 256MB
描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。
由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。
输出
对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。
数据范围
1 ≤ T ≤ 100
小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100
样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear
主算法：
define 输出集合L
get T
for 1 to T
get N,M
for 1 to M-1
get 词对
get 会变词集合
把 变化词集合重构为 循环变化词集 和 传递变化词集合
get 变化语句(words)
for-each word word属于words
if 会 变词集合 contains(word)
依据 循环变化词集 和 传递变化词集合 加上N 对word进行变化
L.add(words)
print L
时间限制: 1000ms 内存限制: 256MB
描述
Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。
由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。
输入
输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。
输出
对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。
数据范围
1 ≤ T ≤ 100
小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10
大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100
样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear
主算法：
define 输出集合L
get T
for 1 to T
get N,M
for 1 to M-1
get 词对
get 会变词集合
把 变化词集合重构为 循环变化词集 和 传递变化词集合
get 变化语句(words)
for-each word word属于words
if 会 变词集合 contains(word)
依据 循环变化词集 和 传递变化词集合 加上N 对word进行变化
L.add(words)
print L
代码：
import java.util.*;
public class Main {
final static int FLAG=-1;
public static void main(String[] args){
int T=0;
int N=0;
int M=0;
Scanner sc=new Scanner(System.in);
T=Integer.valueOf(sc.nextLine());
String[] list=new String[T];
/*分别对每组数据进行处理*/
for(int i=0;i<T;i++){
String str1=sc.nextLine();
String[] nums=str1.trim().split(" ");
N=Integer.valueOf(nums[0]);
M=Integer.valueOf(nums[1]);
String[][] twoWords=new String[M][2];
for(int j=0;j<M;j++){
String str2=sc.nextLine();
String[] words=str2.trim().split(" ");
twoWords[j][0]=words[0];;
twoWords[j][1]=words[1];
}
// 要交换的词
String[]exWords=getExWords(twoWords);
/* 一下全部是基于词下标的处理*/
int[][] twos=getTwos(twoWords,exWords);
/*处理集合，circulate是循环体，transmit是传递体，要是传递体的最后一个元素是-1，那么它是一个复合体*/
List<List<Integer>> circulate=new ArrayList<List<Integer>>(11);
List<List<Integer>> transmit=new ArrayList<List<Integer>>(11);
/* 为处理集合赋值*/
handleWords(circulate,transmit,twos,exWords);
/* 处理集合所包含的词集*/
int[] wordsC=getWordSet(circulate);
int[] wordsT=getWordSet(transmit);
String sentence=sc.nextLine();
String[] words=sentence.split(" ");
/*对词进行处理*/
for(int j=0;j<words.length;j++){
int temp=getIndex(words[j],exWords); //把要处理的词变化为可处理词集的编号，要是-1则不处理
if(words[j].length()>0 && temp!=-1){
if(!disContains(temp,wordsC)){
/* 要处理的词在循环体词集中*/
swap(words,j,circulate,N,exWords);
}else if(!disContains(temp,wordsT)){
/* 要处理的词在传递体词集中*/
swap(words,j,circulate,transmit,N,exWords);
}
}
}
/*对处理后的词继续合并*/
String temp="";
for(String word:words){
temp=temp+" "+word;
}
/* 处理结果合并*/
list[i]=temp.trim();
}
/*打印处理结果*/
printResult(list);
}
/*集合中包含的不同词集*/
private static int[] getWordSet(List<List<Integer>> lists) {
ArrayList<Integer> temp=new ArrayList<Integer>(11);
for(List<Integer> list:lists){
for(int x:list){
if(!temp.contains(x))
temp.add(x);
}
}
int[] xs=new int[temp.size()];
for(int i=0;i<xs.length;i++){
xs[i]=temp.get(i);
}
return xs;
}
/*把变化词对进行编号化处理*/
private static int[][] getTwos(String[][] twoWords, String[] exWords) {
int[][] temp=new int[twoWords.length][2];
for(int i=0;i<twoWords.length;i++){
for(int j=0;j<2;j++){
temp[i][j]=getIndex(twoWords[i][j],exWords);
}
}
return temp;
}
/*把单个词语编号化*/
private static int getIndex(String str, String[] exWords) {
int temp=-1;
for(int i=0;i<exWords.length;i++){
if(str.equals(exWords[i]))
return i;
}
return temp;
}
/*得到可编号化的集合*/
private static String[] getExWords(String[][] twos) {
ArrayList<String> temp=new ArrayList<String>(10);
for(String[] words:twos)
for(String word:words)
if(!temp.contains(word))
temp.add(word);
String[] exWords=new String[temp.size()];
for(int i=0;i<temp.size();i++)
exWords[i]=temp.get(i);
return exWords;
}
/*打印结果集*/
private static void printResult(String[] list) {
for(int i=0;i<list.length;i++)
System.out.println("Case #"+(i+1)+":"+list[i]);
}
/*有循环体参与的句子中词语处理*/
private static void swap(String[] words, int j, List<List<Integer>> listC, int n,String[] exWords) {
String temp=words[j];
int intTemp=getIndex(temp,exWords);
for(List<Integer> list:listC){
if(list.contains(intTemp)){
int index=list.indexOf(intTemp);
int size=list.size();
int step=n-1;
words[j]=exWords[list.get((index+step)%size)];
return;
}
}
}
/*有传递体参与的句子中词语处理*/
private static void swap(String[] words, int j, List<List<Integer>> listC,List<List<Integer>> listT,
int n, String[] exWords) {
String temp=words[j];
int intTemp=getIndex(temp,exWords);
for(List<Integer> list:listT){
if(list.contains(intTemp)){
int index=list.indexOf(intTemp);
int size=list.size();
int step=n-1;
if(index+step<size-1)
words[j]=exWords[list.get(index+step)];
else{
int x=size-2-index;
if(list.get(size-1)==FLAG){
words[j]=exWords[list.get(size-2)];
swap(words,j,listC,n-x,exWords);
}else{
words[j]=exWords[list.get(size-1)];
}
}
return;
}
}
}
/* 为处理集合赋值*/
private static void handleWords(List<List<Integer>> circulate,
List<List<Integer>> transmit, int[][] twos, String[] exWords) {
int[] keys=get(twos,0);
int[] values=get(twos,1);
for(int i=0;i<twos.length;i++){
/* 对一个处理链条的第一个词进行处理*/
if(disContains(twos[i][0],values))
handleHead(twos[i][0],twos,circulate,transmit,values);
else{
if(test(twos[i][0],twos,keys,values)&&noCir(circulate,twos[i][0]))
handleHead(twos[i][0],twos,circulate,transmit,values);
}
}
}
private static boolean noCir(List<List<Integer>> lists, int k) {
for(List<Integer> list:lists){
if(list.contains(k))
return false;
}
return true;
}
private static boolean test(int k, int[][] twos,int[] keys, int[] values) {
int x=-10;
int temp=k;
int value=getValue(temp,twos);
if(value==-1)
return false;
while((!disContains(value,keys))&&(x<twos.length)){
value=getValue(temp,twos);
x++;
}
if(x==twos.length)
return true;
return false;
}
/*词组不包含某词编号*/
private static boolean disContains(int k, int[] values) {
for(int i=0;i<values.length;i++){
if(k==values[i])
return false;
}
return true;
}
/*得到变换词对的某一集合*/
private static int[] get(int[][] twos, int k) {
ArrayList<Integer> temp=new ArrayList<Integer>(11);
for(int i=0;i<twos.length;i++){
if(!temp.contains(twos[i][k]))
temp.add(twos[i][k]);
}
int[] intTemp=new int[temp.size()];
for(int i=0;i<intTemp.length;i++)
intTemp[i]=temp.get(i);
return intTemp;
}
/*对于某一个处理链条的词进行分类*/
private static void handleHead(int head, int[][] two,
List<List<Integer>> circulate,
List<List<Integer>> transmit, int[] values) {
List<Integer> temp=new ArrayList<Integer>(11);
temp.add(head);
int value=getValue(head,two);
while((!temp.contains(value))&&(value!=-1)){
temp.add(value);
value=getValue(value,two);
}
if(value==-1){
transmit.add(temp);
}else{
handle(circulate,transmit,temp,value);
}
}
/* 对于某一个词，得到其变换后的词*/
private static int getValue(int head, int[][] two) {
int temp=-1;
for(int i=0;i<two.length;i++){
if(head==two[i][0])
temp=two[i][1];
}
return temp;
}
/*处理包含循环的集合链条*/
private static void handle(List<List<Integer>> circulate, List<List<Integer>> transmit,
List<Integer> temp,int value) {
if(temp.indexOf(value)==0){
circulate.add(temp);
}else{
handleCir(circulate,value,temp);
temp.add(FLAG);
transmit.add(temp);
}
}
/*处理单纯循环体*/
private static void handleCir(List<List<Integer>> circulate, int value,
List<Integer> temp) {
if(noCir(circulate,value)){
return;
}
int index=temp.indexOf(value);
List<Integer> list=new ArrayList<Integer>(11);
for(int i=index;i<temp.size();i++){
list.add(temp.get(i));
}
circulate.add(list);
}
}
这是通过了小数据测试的，大数据是否能通过就不知道了。
——20130409
PS：
今天早晨数据出来了，这道题的大数据测试是三个题中唯一的一个AC。在意料之外，以为要是能AC一题也是长方形那个题。但，结果也不错。
——20130409
