POJ 2503-Babelfish Babelfish Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 33433 Accepted: 14347 Description You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them. Input Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters. Output Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as “eh”. Sample Input dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay Sample Output cat eh loops Hint Huge input and output,scanf and printf are recommended. Source Waterloo local 2001.09.22
水题。题目说明了“No foreign word appears more than once in the dictionary”，又要快速查找，马上想到用MAP来当字典，然后查找。这题稍微有点麻烦是的输入输出，因为题目没有给出具体的输入结束标志，需要自己判断，输入的又是字符串，且含有空格空行等，虽然题目hint建议用printf或scanf，但是我选择了用C++的getline，看起来更加优雅。 getline的优点是一次读入一行，不管有没有空格，而且它还能读入空行，所以我们可以使用下面的代码来读取一行并判断跳出循环条件： [cpp] while(getline(cin,s)) { if(s=="") break; } [/cpp] 其他的就是常规的字符串处理，map查找输出。具体代码如下： [cpp] #include<iostream> #include<string> #include<map> #include<vector> using namespace std; int main() { string s; map<string,string> mss; vector<string> vs; while(getline(cin,s)) { if(s=="") break; int blankPos=s.find(" ");//找到空格位置 mss[s.substr(blankPos+1)]=s.substr(0,blankPos);//插入map } while(getline(cin,s)) { if(s=="") break; if(mss.find(s)!=mss.end()) { vs.push_back(mss[s]); //cout<<mss[s]<<endl; } else //cout<<"eh"<<endl; vs.push_back("eh"); } int v_size=vs.size(); for(int i=0;i<v_size;i++) { cout<<vs[i]; if(i!=v_size-1) cout<<endl; } return 0; } [/cpp] 本代码提交AC，用时1000MS，内存14648K，效率比较低，如果使用scanf和printf估计会好些。]]>
现在我们分析红色那组字符，首先s[0]==s[2]不成立，可以把s[0]改成A；也可以把s[2]改成C，如果我们把s[2]改成C的话，虽然s[0]==s[2]成立，但是s[2]==s[4]又不成立了，又要修改s[4]；但是如果我们把s[0]改成A的话，则s[0]==s[2]==s[4]都成立，且修改次数更少。那么要怎样才能使修改的次数最少呢？
我们回到问题的本源：使用红色那组字符都相同，为了使修改次数最少，我们当然是将所有字符统一成当前出现次数最多的那个字符咯，这样只需要修改较少的非同一字符，在这个例子中，就是修改成出现次数最多的A。
如果前k个字符串和后k个字符串没有重叠，那就很简单了，只需依次检查对应字符是否相等。
理解了以上内容，代码很快就能写出来了：
[cpp]
#include<iostream>
#include<string>
using namespace std;
//求4个数的最大值
int max4(int a,int b,int c,int d)
{
int maxab=a>b?a:b;
int maxcd=c>d?c:d;
return maxab>maxcd?maxab:maxcd;
}
int main()
{
int t,k,n,d,ans;//t,k为题意；n为字符串长度；d为n-k相隔为d的字符需要相等；ans表示需要修改的碱基数量。
string s;
cin>>t;
while(t–)
{
ans=0;
cin>>s>>k;
n=s.size();
d=n-k;
if(2*k<=n)//如果最前k个碱基和最后k个碱基没有重叠的话
{
for(int i=0;i<k;i++)
if(s[i]!=s[i+d])//只需要依次检查对应字符是否相等即可
ans++;
}
else//如果有重叠，则另行讨论
{
for(int i=0;i<d;i++)//把所有碱基分成d组，需要确保每组都是同一个字符
{
int A=0,T=0,G=0,C=0,num=0;
for(int j=i;j<n;j+=d)//对于每一组，求出该组中出现次数最多的碱基的个数
{
num++;
if(s[j]==’A’)
A++;
else if(s[j]==’T’)
T++;
else if(s[j]==’G’)
G++;
else
C++;
}
int maxATGC=max4(A,T,G,C);//该组全部修改成出现次数最多的碱基
int change_num=num-maxATGC;//用该组中所有碱基个数减去出现次数最多的碱基个数，就是需要修改的碱基个数
ans+=change_num;
}
}
cout<<ans<<endl;
}
return 0;
}
[/cpp]
本代码提交AC，用时1MS，内存0MB。
]]>