技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置：首页 --> 算法 --> 百度AStar2008的一道题：成语纠错

百度AStar2008的一道题：成语纠错

浏览:2302次  出处信息

有个小盆友正好问我这个问题，当年这个题在Astar我是满分pass了，贴出来参考下，无技术含量。

问题背景
成语是中华民族的文化瑰宝，作为历史的缩影、智慧的结晶、汉语言的精华，闪烁着睿智的光芒。
你的任务是给一个错误的四字成语进行纠错，找到它的正确写法。具体来说，你只允许修改四个汉字中的其中一个，使得修改后的成语在给定的成语列表中出现。原先的错误成语保证不在成语列表中出现。

有时，这样的“纠错”结果并不惟一。例如“一糯千金”可以改为“一字千金”也可以改成“一诺千金”。但由于“糯”和“诺”是同音字，“一糯千金”实为“一诺千金”的可能性比较大。
因此，我们还将提供一个汉字分类表，要求修改前后的两个字必须属于同一个分类。
在这样的限制下，我们保证成语纠错的结果惟一。
注意
1、汉字均采用GBK编码(参见FAQ)
2、每个汉字分类至少包含两个汉字，同一个汉字可能出现在多个类别中。
3、成语列表中的成语都是真实存在的四字成语。成语列表和待纠错成语中的所有汉字均在汉字分类表中的至少一个分类中出现。
输入格式
输入第一行包含两个整数n, m(1<=n<=200, 1<=m<=20000)。n表示汉字类别的个数，m表示成语的个数。
以下n行每行用一个无空白分隔符（空格、TAB）的汉字串表示一个分类中的所有汉字。注意，该汉字串最多可能包含200个汉字。
以下m行为成语列表，每行一个成语，恰好四个汉字。
最后一行为待纠错的成语，恰好四个汉字，且不在成语列表中出现。
输出格式
仅一行，为一个四字成语。在“修改必须在同一分类中进行”的限制下，输入数据保证纠错结果惟一。
样例输入
7 3
糯诺挪喏懦
字自子紫籽
前钱千牵浅
进近今仅紧金斤尽劲
完万
水睡税
山闪衫善扇杉
一诺千金
一字千金
万水千山
一糯千金
样例输出
一诺千金

#include <iostream>#include <string>#include <vector>usingnamespace std;
 
int hashkey(char ch1,char ch2){return((unsignedchar)ch1-129)*190+((unsignedchar)ch2-64)-(unsignedchar)ch2/128;}
 
int checksame(string str1,string str2,string &strn,string &strm){int count =0;for(int i =0; i <4;++i)if((str1[i*2]==str2[i*2])&&(str1[i*2+1]==str2[i*2+1]))++count;else{
                strn.resize(2);
                strm.resize(2);
                strn[0]= str1[i*2];
                strn[1]= str1[i*2+1];
                strm[0]= str2[i*2];
                strm[1]= str2[i*2+1];}//cout << "Check:" << str1 << "," << str2//<< ":" << count//<< "--" << strn[0] << strn[1]//<< "|" << strm[0] << strm[1] <<endl;return count;}
 
int main(){int n,m;int count;int GBKindex,GBKindex1;
    vector< vector<int>> hashn;
    vector< vector < vector<int>>> hashm;
    string str,tmp1,tmp2;
    string kind[200],word[20000];
 
    cin>> n >> m;
 
    hashn.resize(25000);for(int i =0; i <25000;++i)
        hashn[i].resize(1,0);for(int i =0; i < n;++i){cin>> kind[i];//cout << kind[i].size() << endl;for(int j =0; j <(kind[i].size()/2);++j){
            GBKindex = hashkey(kind[i][j*2],kind[i][j*2+1]);
            count =++hashn[GBKindex][0];
            hashn[GBKindex].resize(count+1);
            hashn[GBKindex][count]= i;//cout << GBKindex << ":" << hashn[GBKindex][0] << ":"//<< i << ":" <<kind[i][j*2] << kind[i][j*2+1] <<endl;}}
 
    hashm.resize(4);for(int i =0; i <4;++i)
        hashm[i].resize(25000);for(int i =0; i <4;++i)for(int j =0; j <25000;++j)
            hashm[i][j].resize(1,0);for(int i =0; i < m;++i){cin>> word[i];for(int j =0; j <4;++j){
            GBKindex = hashkey(word[i][j*2],word[i][j*2+1]);
            count =++hashm[j][GBKindex][0];
            hashm[j][GBKindex].resize(count+1);
            hashm[j][GBKindex][count]= i;//cout << GBKindex << ":" << hashm[j][GBKindex][0] << ":"//<< i << ":" << word[i][j*2] << word[i][j*2+1] <<endl;}}
 
    cin>> str;
 
    for(int i =0; i <4;++i ){
        GBKindex = hashkey(str[i*2],str[i*2+1]);//cout << GBKindex <<endl;//cout << hashm[i][GBKindex][0] <<endl;for(int j =1; j <= hashm[i][GBKindex][0];++j){if(checksame(str,word[hashm[i][GBKindex][j]],tmp1,tmp2)==3){
                GBKindex1 = hashkey(tmp2[0],tmp2[1]);for(int k =1; k <= hashn[GBKindex1][0];++k){//cout << kind[hashn[GBKindex1][k]] <<endl;if(kind[hashn[GBKindex1][k]].find(tmp1)!= string::npos){cout<< word[hashm[i][GBKindex][j]]<< endl;return0;}}}}}//system("pause");return0;}


QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：房租分配问题
后一篇：跳跃表的实现和测试 >>
文章信息
© 2009 - 2024 by blogread.cn 微博：@IT技术博客大学习

京ICP备15002552号-1