18/7/2012 ICPC培训 第三天
今天看了五题，刷出来四题。各种无语呀！
首先看第一题吧。（HDU1217）
这题花了整整一上午，就快4个小时了。结果还是在百度的配合下搞定的
！
本以为是简单的字符串操作，首先的想法也就是那样的。结果才发现根本的不对。然后用深搜，
结果TLE。当然，深搜也是错的。因为，一次搜索一个节点只能用一次！或许可以用多次。题目
没规定。最后，还是度娘帮着解决了。Floyd算法，三重for循环。当然，首先你的建图。
说到这就有的说了。这两天做题就发觉：我们得有能力把实际问题抽象出来，知道输入输出、利
用经典算法或者做些变形或者直接自己设计算法、把算法的逻辑用代码准确的表达出来。
再来看看我做的第二、三题吧。（HDU1218、1220）
这是两道水题。1218是对二维数组进行操作。1220是道简单数论题。
然后，再看下第四题。（HDU1221）
其实，这也是道简单题。是道几何体，判断两图形是否相交。可还是被卡了很长时间。先是没有
想出好的算法，然后想到了算法。可是坑爹的事发生了。WA数次，想到各种可能错误。耗了大量
时间，还是WA！差点就忍不住找度娘。突然，发觉，代码逻辑和我的算法有点点不一样，一点手
误，在判断语句if 前面多加了else！！！
最后呢，要感谢王飞飞同学关于搜索、DP的报告。看清了自己懂搜索的真实面目——还是不懂！！！
也和他小讨论了一下，觉得有收获啊。这两天好好刷搜索和DP，希望后天下午的比赛可以打的更好。
代码：
1217：
#include<iostream>using namespace std;const int maxSize=41;const int maxLen=201;double map[maxSize][maxSize];int n,m,cas=1;char name[maxSize][maxLen];int findIndex(char ch[]){ for(int i=0;i<n;i++) { if(strcmp(ch,name[i])==0) { return i; } } return -1;}void init(){ for(int i=0;i<n;i++) { scanf("%s",name[i]); } scanf("%d",&m); char c1[maxLen],c2[maxLen]; double d; int row,col; memset(map,0,sizeof(map)); for(int j=0;j<m;j++) { scanf("%s%lf%s",&c1,&d,&c2); row=findIndex(c1); col=findIndex(c2); map[row][col]=d; //建图 }}void Floyd(){ for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(map[i][j]<map[i][k]*map[k][j]) { map[i][j]=map[i][k]*map[k][j]; } } } } bool flag=false; for(int i=0;i<n;i++) { if(map[i][i]>1) { flag=true; break; } } printf("Case %d: ",cas++); if(flag) printf("Yes\n"); else printf("No\n");} int main(){ while(cin>>n,n) { init(); Floyd(); } return 0;}
1218：
#include<iostream>using namespace std;const int MAX=10;int row,col;char start[MAX+5],end[MAX-5];int in[MAX][MAX],out[MAX][MAX];void input(){ cin>>row>>col; char temp; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { cin>>temp; in[i][j]=temp-'0'; } } cin>>end;}void deal(){ for(int i=0;i<row-1;i++) { for(int j=0;j<col-1;j++) { out[i][j]=in[i][j]+in[i][j+1]+in[i+1][j]+in[i+1][j+1]; out[i][j]/=4; } }} void output(){ for(int i=0;i<row-1;i++) { for(int j=0;j<col-1;j++) { cout<<out[i][j]; } cout<<endl; }} int main(){ while(cin>>start) { if(strcmp(start,"ENDOFINPUT")==0) break; input(); deal(); output(); } return 0;}
1220：
#include<iostream>using namespace std;int main(){ int n; __int64 a,b; while(cin>>n) { if(n==1) { cout<<0<<endl; continue; } a=n*n*n; if(a%2==0) { a=a/2*(a-1); } else { a=(a-1)/2*a; } b=3*n*n*(n-1); cout<<a-b<<endl; } return 0;}
1221：
#include<iostream>#include<cmath>using namespace std;int main(){ double cx,cy,r; double rx1,rx2,ry1,ry2; double x1,x2,y1,y2; int cas; bool flag1,flag2,flag3,flag4; cin>>cas; while(cas--) { cin>>cx>>cy>>r>>rx1>>ry1>>rx2>>ry2; x1=rx1>rx2?rx2:rx1; x2=rx1>rx2?rx1:rx2; y1=ry1>ry2?ry2:ry1; y2=ry1>ry2?ry1:ry2; flag1=flag2=flag3=flag4=false; double temp1,temp2; if((r*r-(rx1-cx)*(rx1-cx))>=0) { temp1=sqrt(r*r-(rx1-cx)*(rx1-cx))+cy; temp2=-sqrt(r*r-(rx1-cx)*(rx1-cx))+cy; if((temp1>=y1 && temp1<=y2) || (temp2>=y1 && temp2<=y2)) { flag1=true; } } if((r*r-(rx2-cx)*(rx2-cx))>=0) //if前多加了else { temp1=sqrt(r*r-(rx2-cx)*(rx2-cx))+cy; temp2=-sqrt(r*r-(rx2-cx)*(rx2-cx))+cy; if((temp1>=y1 && temp1<=y2) || (temp2>=y1 && temp2<=y2)) { flag2=true; } } if((r*r-(ry1-cy)*(ry1-cy))>=0) //if前多加了else { temp1=sqrt(r*r-(ry1-cy)*(ry1-cy))+cx; temp2=-sqrt(r*r-(ry1-cy)*(ry1-cy))+cx; if((temp1>=x1 && temp1<=x2) || (temp2>=x1 && temp2<=x2)) { flag3=true; } } if((r*r-(ry2-cy)*(ry2-cy))>=0) //if前多加了else { temp1=sqrt(r*r-(ry2-cy)*(ry2-cy))+cx; temp2=-sqrt(r*r-(ry2-cy)*(ry2-cy))+cx; if((temp1>=x1 && temp1<=x2) || (temp2>=x1 && temp2<=x2)) { flag4=true; } } if(flag1 || flag2 || flag3 || flag4) { cout<<"YES"; } else { cout<<"NO"; } cout<<endl; } return 0;}