20/7/2012 ICPC培训 第五天
今天是第二次内部比赛。
共六题，刷出来两题。都是搜索。排在第二名，第一刷出3题，然后有好几个刷出2题的。
还需努力呀！
（明天看过结题报告后再把题目、代码、测试数据传到共享里）
另外，今天还刷了HDU上的2题，依旧都是搜索。明天开始做DP了。大神说要从背包开始。
第一题（HDU1181）
题目意思很好懂。就是输入一系列单词，每个单词的首尾字母可以到达，问是否能从b->m。
我的做法是建图，然后dfs。唯一的遗憾的是为了是代码简洁些，我把输入及建图写到一个
函数input()里，然后在main()中写了：
int main(){ while(1) { input(); dfs(); } return 0;}结果你懂的，TLE。我还在想怎么测试数据怎么变态！！！脑残了、2B。。。
然后，发觉了这个问题，把while(1)写成while(cin.peek()!=EOF)。结果WA了。。。
代码：
#include<iostream>#include<cstring> using namespace std;const int maxSize=27;const int finalPoint='m'-'a'+1; const int startPoint='b'-'a'+1; bool map[maxSize][maxSize];bool visited[maxSize][maxSize];bool flag; void dfs(int x){ if(x==finalPoint) { flag=true; return; } for(int i=1;i<=26;i++) { //if(flag) return; if(map[x][i] && !visited[x][i]) { visited[x][i]=true; map[x][i]=false; dfs(i); //if(flag) return; visited[x][i]=false; map[x][i]=true; } }} int main(){ char temp[maxSize*2]; int len,row,col; while(cin>>temp) { memset(visited,false,sizeof(visited)); memset(map,false,sizeof(map)); len=strlen(temp); row=temp[0]-'a'+1; col=temp[len-1]-'a'+1; if(row!=col) { map[row][col]=true; } while(cin>>temp) { if(strcmp(temp,"0")==0) break; len=strlen(temp); row=temp[0]-'a'+1; col=temp[len-1]-'a'+1; if(row!=col) { map[row][col]=true; } } flag=false; dfs(startPoint); if(flag) { cout<<"Yes."; } else { cout<<"No."; } cout<<endl; } return 0;} 第二题（HDU1495）
做了这题很激动呀。很久之前就做了，没做好的。今天终于结果它了！
这是一道好题。大家都懂的，搜素就是从一个状态通过一定的规则转换到另一个状态。
而这题就难在状态不好扩展。
就没有题会老老实实的被刷出来！算法设计的没错，可是代码却不是完全符合自己的算法
逻辑！！！最纠结的是自己还以为代码逻辑是对的，这还怎么检查这类错误呀？？？！！！
代码中有一处当x<yy-y时，把x全给y，再把x赋0。
我却写成了：
else if(x<yy-y) { x=0; y+=x; } 找这个错我可是费尽周折
。。。
代码：
#include<iostream>#include<cstring>#include<queue> using namespace std;const int maxLoad=101; bool appeal[maxLoad][maxLoad][maxLoad];bool flag;int minStep; int s,n,m;int sss,nnn,mmm; struct node{ int ss,nn,mm,step;};void stateChange(int &x,int &y,int yy){ if(x==yy-y) { x=0; y=yy; } else if(x>yy-y) { x-=yy-y; y=yy; } else if(x<yy-y) { y+=x; //居然把这两行写反了！！！ x=0; } } void preDeal(int i){ if(i==1) { stateChange(sss,nnn,n); } else if(i==2) { stateChange(sss,mmm,m); } else if(i==3) { stateChange(nnn,sss,s); } else if(i==4) { stateChange(mmm,sss,s); } else if(i==5) { stateChange(mmm,nnn,n); } else { stateChange(nnn,mmm,m); } } bool average(int x,int y,int z){ if((x==0 && y==z) || (y==0 && x==z) || (z==0 && x==y)) { return true; } return false;} void bfs(){ node temp1,temp2; queue<node> myQ; temp1.ss=s;temp1.nn=0;temp1.mm=0;temp1.step=0; myQ.push(temp1); memset(appeal,false,sizeof(appeal)); appeal[s][0][0]=true; flag=false; while(!myQ.empty() && !flag) { temp1=myQ.front(); myQ.pop(); for(int i=1;i<=6;i++) //从temp1状态转移到temp2状态 { sss=temp1.ss; nnn=temp1.nn; mmm=temp1.mm; //cout<<"1 "<<sss<<" "<<nnn<<" "<<mmm<<endl; preDeal(i); if(average(sss,nnn,mmm)) { flag=true; minStep=temp1.step+1; return; } if(!appeal[sss][nnn][mmm]) { //cout<<"2 "<<sss<<" "<<nnn<<" "<<mmm<<endl; appeal[sss][nnn][mmm]=true; temp2.ss=sss; temp2.nn=nnn; temp2.mm=mmm; temp2.step=temp1.step+1; myQ.push(temp2); } } }} int main(){ while(cin>>s>>n>>m,s||n||m) { if(s%2==1) { cout<<"NO"<<endl; continue; } bfs(); if(flag) { cout<<minStep<<endl; } else { cout<<"NO"<<endl; } } return 0;} 最后，要告诉自己，要好好刷DP了。。。
加油，ACMer