Decoding Baby Boos
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83008#problem/A
Description
Osantu has been tagged as the best Bangladeshi contestant of present time by many and now he is mostly busy with the sweetest problem of his life — a baby boy. But Osantu often struggles to decode the sound that the baby makes throughout the year and so he asks for your help. He has converted the sound that the baby makes into a huge string. He thinks that sound made by the baby is often hard to understand because he replaces one character with another character. So in his diary he has prepared a list of replacement rules. Your job is to reverse these replacements and find the actual text that the baby wanted to say although in many cases the rules are not reversible.
Input
First line of the input file contains a positive integer T (T ≤ 6) which denotes how many test cases are there in the input file. The description of each test case is given below:
First line of each test case contains a non-empty string S (containing only uppercase characters and underscore). The length of this string can be up to 1000000. Next line contains a positive integer R (R ≤ 10000), which denotes how many character replacement sequences follow. Each of the next R lines contains two characters ai and bi (both ai and bi are uppercase letters and separated by a single space) which denotes that while pronouncing the baby replaces character ai with character bi . As this replacement list is prepared by Osantu (who has short term memory) so the list can contain the same replacement rules twice, there can be cyclic rules like ‘A’ is replaced with ‘B’, ‘B’ is replaced with ‘C’ and ‘C’ is replaced with ‘A’ and also there can be contradicting rules like ‘A’ is replaced with ‘B’ and ‘A’ is replaced with ‘C’ etc. So what you simply need to do is apply the reverse of those rules in the order they appear in the input although it may not seem logical.
Output
For each set of input produce one line of output. This line contains the string that is found by applying all the R replacement rules.
Illustration of the 2nd sample input:
First replacement rule says the baby replaces ‘A’ with ‘B’. So to reverse that rule all ‘B’ s are replaced with ‘A’. So the string becomes “AAAACCY”. The 2nd rule says ‘B’ is replaced with ‘C’ and so to reverse this rule we replace all ‘C’s with ‘B’ and so the string becomes “AAAABBY”. The 3rd rule says that ‘C’ is replace with ‘A’ and so to reverse that we now replace all ‘A’s with ‘C’ and so the string finally becomes “CCCCBBY”.
Sample Input
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A
Sample Output
ABBU_TUMI_CODING_PARO_NAH
CCCCBBY
HINT
题意
给你一个字符串，以及一些替换，要求你把这些单词换成另外的单词
问你最后这个字符串是什么样子
题解：
直接暴力换就好了~
代码
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** int flag[30]; int main() { int t=read(); for(int cas=1;cas<=t;cas++) { for(int i=0;i<30;i++) flag[i]=i; string s; cin>>s; int q=read(); while(q--) { char a,b; cin>>a>>b; for(int i=0;i<30;i++) { if(flag[i]==b-'A') flag[i]=a-'A'; } } for(int i=0;i<s.size();i++) { if(s[i]>'Z'||s[i]<'A') cout<<s[i]; else printf("%c",flag[s[i]-'A']+'A'); } printf(" "); } }