首页 > 代码库 > 上海邀请赛之热身赛2_2013成都邀请赛
上海邀请赛之热身赛2_2013成都邀请赛
先写总结。
感觉这次跟scf和sjc组队有种瞬间碉堡了的感觉,虽然是临时组建的队伍凑齐准备去上海参加邀请赛,从这次比赛磨练配合。
今天比赛难度比前天那次的难度低,感觉更适合我们来练习。
话说好像比赛提早了5分钟,我们三个人都不知道,五分钟后一看A题学长已经A了,一想肯定特水。。。我就没看题,sjc和scf两个看了题,scf就开始敲了,我刚开始负责翻译题,虽然我英语是个渣渣。。。没办法,没翻译他们几乎做不出题。。。我就没做题,翻译了B和G。scf敲了貌似好久才完成(赛后重做,特水,基本3分钟就可以出题)。我翻译完B和G,sjc开始想思路,这是已经有出L题,我也没看题,scf直接看题敲了,一次wa,就让我翻译L题(没翻译完就敢做。。。),接着少了“case”。。。一会也A了,sjc说G是找规律,于是scf和sjc两人就找规律去了,我一人想B,等scf开始敲G题,我跟sjc说了B的思路,他也觉得应该可以。。。(其实翻译错题意了。。。)趁着scf敲G题,我又翻译了几题,手里积累了好几题,感觉都是可做的,sjc一个人积了K和B,scf自己调试G题,我自己看了E题,几何,又跟sjc交流了下,感觉可以套模板。。。找了模板上机敲了。。。
貌似敲得太久,scf调试完了也要机子,只好先让他敲。。。G题错了3次也A了。。。我又继续敲模板,一会又让给sjc敲B题,自己构思E。结果sjc的B题错了,大家才觉得翻译错了。。。榜上好像还没人出B。。。我继续敲E。scj和scf两人就讨论K,我敲完E貌似测试一直错了,让sjc敲K题,自己才发现少考虑情况了,而且连模板都敲错了,家才K题出来了就是WA,scf说是翻译错了数据范围,还真是,于是又讨论去了,我也敲了E题,结果忘了注释给错了一次。。。后来的好久就看sjc敲K题,其他题都没有出的。。。
N久后K题顺利过了,排名瞬间上去了,那感觉。。。最后一个小时,scj找了一题DP的题,我和scf看了一题图论的,我一开始感觉可行,上机敲了一些,就感觉可能超内存,scf说可能超时,结果就放弃了。。。最后是5题结束,感觉世界都萌萌哒了。。。
第一次和scf,sjc配合,出乎意料的好,不过暴露了一些小问题,scf罚时太多。。。自己也忘了注释。。。还有翻译。。。
下面是部分题的题解。。。
Ahttp://acm.hdu.edu.cn/showproblem.php?pid=4716
A题我还是贴我的代码吧,不吐槽scf了。。。一水。。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { int t,k=1,n,i; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("Case #%d:\n",k++); printf("*------------*\n"); for(i=0;i<10-n/10;i++) { printf("|............|\n"); } for(i=0;i<n/10;i++) printf("|------------|\n"); printf("*------------*\n"); } return 0; }
Ehttp://acm.hdu.edu.cn/showproblem.php?pid=4720
几何模板题,求最小圆覆盖,要分情况讨论,当三角形是锐角最小圆就是外接圆,如果三角形是钝角,最小圆就是以最大边为直径的圆。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; struct Point { double x; double y; } pt[1005]; struct Circle { struct Point center; double r; }; struct Traingle { struct Point p[3]; }; double Dis(struct Point p,struct Point q) { double dx=p.x-q.x; double dy=p.y-q.y; return sqrt(dx*dx+dy*dy); } double Area(struct Traingle ct) { return fabs((ct.p[1].x-ct.p[0].x)*(ct.p[2].y-ct.p[0].y)-(ct.p[2].x-ct.p[0].x)*(ct.p[1].y-ct.p[0].y))/2.0; } struct Circle CircumCircle(struct Traingle t) { struct Circle tmp; double a,b,c,c1,c2; double xA,yA,xB,yB,xC,yC; a=Dis(t.p[0],t.p[1]); b=Dis(t.p[1],t.p[2]); c=Dis(t.p[2],t.p[0]); tmp.r=(a*b*c)/(Area(t)*4.0); xA=t.p[0].x; yA=t.p[0].y; xB=t.p[1].x; yB=t.p[1].y; xC=t.p[2].x; yC=t.p[2].y; c1=(xA*xA+yA*yA-xB*xB-yB*yB)/2.0; c2=(xA*xA+yA*yA-xC*xC-yC*yC)/2.0; tmp.center.x=(c1*(yA-yC)-c2*(yA-yB))/((xA-xB)*(yA-yC)-(xA-xC)*(yA-yB)); tmp.center.y=(c1*(xA-xC)-c2*(xA-xB))/((yA-yB)*(xA-xC)-(yA-yC)*(xA-xB)); return tmp; }; int main() { struct Traingle tt; Point qq; Circle cc; double l1,l2,l3; int t,k=1; scanf("%d",&t); while(t--) { scanf("%lf %lf",&tt.p[0].x,&tt.p[0].y); scanf("%lf %lf",&tt.p[1].x,&tt.p[1].y); scanf("%lf %lf",&tt.p[2].x,&tt.p[2].y); scanf("%lf %lf",&qq.x,&qq.y); l1=Dis(tt.p[0],tt.p[1]); l2=Dis(tt.p[0],tt.p[2]); l3=Dis(tt.p[2],tt.p[1]); if(((l1*l1)+(l2*l2)<(l3*l3))||((l3*l3)+(l2*l2)<(l1*l1))||((l1*l1)+(l3*l3)<(l2*l2))) { if(((l1*l1)+(l2*l2)<(l3*l3))) { cc.r=l3/2.0; cc.center.x=(tt.p[1].x+tt.p[2].x)/2.0; cc.center.y=(tt.p[1].y+tt.p[2].y)/2.0; } else if(((l3*l3)+(l2*l2)<(l1*l1))) { cc.r=l1/2.0; cc.center.x=(tt.p[1].x+tt.p[0].x)/2.0; cc.center.y=(tt.p[1].y+tt.p[0].y)/2.0; } else if(((l1*l1)+(l3*l3)<(l2*l2))) { cc.r=l2/2.0; cc.center.x=(tt.p[0].x+tt.p[2].x)/2.0; cc.center.y=(tt.p[0].y+tt.p[2].y)/2.0; } } else{ cc=CircumCircle(tt); } //printf("%.2lf %.2lf\n",cc.center.x,cc.center.y); //printf("%.2lf %.2lf\n",cc.r,Dis(qq,cc.center)); printf("Case #%d: ",k++); if(Dis(qq,cc.center)<=cc.r) printf("Danger\n"); else printf("Safe\n"); } return 0; }
Khttp://acm.hdu.edu.cn/showproblem.php?pid=4726
两个规则,1是加法不进位,2是数中任意位可以对掉,不出现前导零的情况。
贪心,第一次只能取非零的最大。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; char str1[2000000] ; char str2[2000000] ; int main() { int k , i , j , l ; int s1[11] , s2[11] , ss[11] ; int t , tt ; scanf("%d", &t); for(tt = 1 ; tt <= t ; tt++) { memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s1)); memset(ss,0,sizeof(ss)); scanf("%s%s", str1, str2); l = strlen(str1) ; for(i = 0 ; i < l ; i++) { s1[ str1[i]-'0' ]++ ; s2[ str2[i]-'0' ]++ ; } if( l == 1 && ( s1[0] == 1 || s2[0] == 1 ) ) { if(s1[0] == 1) { printf("Case #%d: %c\n", tt, str2[0]); } else { printf("Case #%d: %c\n", tt, str1[0]); } continue ; } printf("Case #%d: ", tt); int mm = -1 , m , mi , mj ; for(i = 1 ; i <= 9 ; i++) for(j = 1 ; j <= 9 ; j++) { if( s1[i] && s2[j] ) { m = i + j ; m %= 10 ; if(m >mm) { mm = m ; mi = i ; mj = j ; } } } printf("%d", mm); if(mm == 0) { printf("\n"); continue ; } s1[mi]-- ; s2[mj]-- ; for(k = 9 ; k >= 0 ; k--) { if(k == 7) k = 7 ; for(i = 0 ; i <= 9 ; i++) for(j = 0 ; j <= 9 ; j++) { if( s1[i] && s2[j] && (i+j)%10 == k ) { m = min(s1[i],s2[j]) ; ss[k] += m ; s1[i] -= m ; s2[j] -= m ; } } } for(i = 9 ; i >= 0 ; i--) { for( j = ss[i] ; j > 0 ; j--) { printf("%d", i) ; } } printf("\n"); } return 0; }
Lhttp://acm.hdu.edu.cn/showproblem.php?pid=4727
貌似也是水题,赛后我做的时候用cin竟然超时了。。。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; int t,n,k=1,num[100010]; int main() { int i,j; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0; i<n; i++) scanf("%d",&num[i]); printf("Case #%d: ",k++); int x=0,p; for(i=1; i<n; i++) { if(num[i]!=num[i-1]+1) { p=i+1; x++; } } if(x!=1)printf("1\n"); else printf("%d\n",p); } return 0; }