USACO Section1.2 Name That Number 解题报告

　　　　namenum解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　你有一个手机，键盘如下所示：
　　　　2: A,B,C 5: J,K,L 8: T,U,V
　　　　3: D,E,F 6: M,N,O 9: W,X,Y
　　　　4: G,H,I 7: P,R,S
　　你还有一本字典，就是本目录下的"dict.txt"。里面有许多英文字符串，一行一个，是按照字典序排好的。
　　现在给你一个输入，是数字字符串。请你从字典中找到所有能与之匹配的英文字符串，一行一个，按照字典序输出，一个没有输出"NONE"。
　　所谓匹配是指：按照手机键盘，你可以将两个串对应起来，并且长度相同。
【数据范围】
　　数字串长度可能是1~12
　　英文串不到5000个
【输入样例】
　　4734
【输出样例】
　　GREG
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　没有难度。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　1.字典本身是按照字典序排好的，注意到这个，就不用对答案再排序了……（我就没看到，又写了个快排）
　　2.题目没说字符串有多长，于是我用的string去规避这个问题，其实搞个比较大的char数组也是可以的。
　　3.这题比较奇葩……有个dict.txt，在网页上给出链接了，但其内容很大。我不知道他想要我当做输入文件去读，还是直接存到代码里。
　　当我用ifstream去读时，发现读不到，不知是不是我读错了。于是我把它写到了代码的初始化部分，代码瞬间变成了100K，USACO服务器真好……

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

1、namenum.cpp

 /*

 ID: icedrea1

 PROB: namenum

 LANG: C++

 */

 #include <iostream>

 #include <fstream>

 using namespace std;

 void qsort(string str[],int l,int r)

 {

     if(l>=r) return;

     int i=l,j=r;

     string x=str[(l+r)>>];

     while(true)

     {

         while(str[i]<x) ++i;

         while(str[j]>x) --j;

         if(i>j) break;

         swap(str[i],str[j]);

         ++i; --j;

     }

     qsort(str,l,j); qsort(str,i,r);

 }

 bool same(string name,string num)

 {

     if(name.size()!=num.size()) return false;

     for(int i=;i!=num.size();++i)

     {

         switch(num[i])

         {

             case '':

                 if(name[i]!='A' && name[i]!='B' && name[i]!='C') return false;

                 break;

             case '':

                 if(name[i]!='D' && name[i]!='E' && name[i]!='F') return false;

                 break;

             case '':

                 if(name[i]!='G' && name[i]!='H' && name[i]!='I') return false;

                 break;

             case '':

                 if(name[i]!='J' && name[i]!='K' && name[i]!='L') return false;

                 break;

             case '':

                 if(name[i]!='M' && name[i]!='N' && name[i]!='O') return false;

                 break;

             case '':

                 if(name[i]!='P' && name[i]!='R' && name[i]!='S') return false;

                 break;

             case '':

                 if(name[i]!='T' && name[i]!='U' && name[i]!='V') return false;

                 break;

             case '':

                 if(name[i]!='W' && name[i]!='X' && name[i]!='Y') return false;

                 break;

         }

     }

     return true;

 }

 void init(string dict[]);

 int main()

 {

     ifstream in("namenum.in");

     ofstream out("namenum.out");

     int n,s=;

     string num,r[],dict[];

     getline(in,num); init(dict);

     for(int i=;i!=s;++i)

     {

         if(same(dict[i],num)) r[++n]=dict[i];

     }

     if(!n) out<<"NONE"<<endl;

     else

     {

         qsort(r,,n);

         for(int i=;i<=n;++i) out<<r[i]<<endl;

     }

     in.close();

     out.close();

     return ;

 }

 void init(string dict[])

 {

     // 用下面的代码生成

 }

2、生成字典的代码

 #include <iostream>

 #include <fstream>

 using namespace std;

 int main()

 {

     ifstream in("dict.txt");

     ofstream out("doc.txt");

     string name;

     for(int i=;getline(in,name);++i)

         out<<"\tdict["<<i<<"]=\""<<name<<"\";"<<endl;

     in.close();

     out.close();

     return ;

 }

巴特西

USACO Section1.2 Name That Number 解题报告

最新文章

热门文章