首页 > 代码库 > [NOIP2002] 字串变换 宽搜+深度优化
[NOIP2002] 字串变换 宽搜+深度优化
这道题硬是让我用STL水过.......而且题解里说的什么双向宽搜，交替扩展...............
这道题反正，STL用就用吧，但是状态数可以卡到千亿级别，因为这个东西是阶乘扩展的，然后我们发现他的深度会极大地影响状态数，然而如果我们把深度缩小为0.5倍，那么他的状态数也就是百万级别的，所以我们可以多源搜索来进行深度优化。
由此可见多源搜索是一个方式，深度优化是一种十分有效的优化.
#include <map>#include <cstdio>#include <string>#include <vector>#include <iostream>namespace Hash{ const int P=10000007; const int K=133; bool hash[10000007]; inline int Hash(std::string s){ int len=s.size(),ret=0; for(int i=0;i<len;i++) ret=(ret*K%P+s[i])%P; return ret; } inline bool ex(std::string s){ return hash[Hash(s)]; }}using namespace std;vector<string> temp,now;string a,b,stage[10][2];int t;map<string,bool> just;int main(){ freopen("string.in","r",stdin); freopen("string.out","w",stdout); cin>>a>>b; while(cin>>stage[++t][0]) cin>>stage[t][1]; t--; now.push_back(a); for(int k=1;k<=10;k++){ temp.clear(); for(int i=0;i<now.size();i++) for(int j=1;j<=t;j++) if(now[i].find(stage[j][0],0)!=string::npos){ int pos=0; while(now[i].find(stage[j][0],pos)!=string::npos){ string s=now[i]; pos=now[i].find(stage[j][0],pos); s=s.replace(pos,stage[j][0].size(),stage[j][1]); if(Hash::ex(s)==0){ Hash::hash[Hash::Hash(s)]=1; if(s==b){ printf("%d",k); return 0; } temp.push_back(s); } pos+=stage[j][0].size(); } } now=temp; } printf("NO ANSWER!"); return 0;}
[NOIP2002] 字串变换 宽搜+深度优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。