上海邀请赛前拿2013年的成都邀请赛热身,比赛结果大大出乎了我们的预期啊。。。没做出来的几道题可能还会更新的。
A题:
题目地址:HDU 4716
水题。。这题是我敲的。。敲麻烦了。。。sad。。。你们就当没看见吧。。。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int main() { char s[20][20]; int t, x; int i, j, num=0; scanf("%d",&t); while(t--) { num++; scanf("%d",&x); printf("Case #%d:\n",num); x=x/10; s[0][0]='*'; s[0][13]='*'; s[11][0]='*'; s[11][13]='*'; for(i=1;i<13;i++) { s[0][i]='-'; s[11][i]='-'; } for(i=1;i<11;i++) { s[i][0]='|'; s[i][13]='|'; } for(i=1;i<=10-x;i++) { for(j=1;j<=12;j++) { s[i][j]='.'; } } for(i=10-x+1;i<=10;i++) { for(j=1;j<=12;j++) { s[i][j]='-'; } } for(i=0;i<=11;i++) { for(j=0;j<=13;j++) { printf("%c",s[i][j]); } printf("\n"); } } return 0; }
题目地址:HDU4720
不是我做的。。。计算几何题不想做。。。。队友说是模板题。
代码如下:
#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; }
G题:
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4722
额。。这题听学长说是DP?好吧。。不管了,反正我推得规律做出来了。。。
这题的规律在于从XXX0到XXX9(X指任意数,任意位数,比如12340至12349或111111110至111111119这样的)中间,他们的各位和是递增1的,而且刚好递增了10,也就是说每一个这样的10个数的周期都是有且只有1个刚好能被10整除的,所以对于任意的区间内只要找到有多少个这样的周期即可。然后再遍历找出前面和后面多余的。比如5至35,遍历找到前面多余的5到9,没有,再遍历后面多余的30到35,没有,然后中间的10到29是两个周期,直接加上2.于是2就算出来了。只需要遍历最多20个数,剩下的可以计算出来。因为int64被坑了3次WA。。。
代码如下:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; __int64 num=0, i, j, x, y, t, a, b, s, sum, pos1, pos2, flag1, flag2, z; int main() { scanf("%I64d",&t); while(t--) { s=0; num++; flag1=flag2=0; scanf("%I64d%I64d",&a, &b); for(i=a; i<=b; i++) { x=i; y=i; sum=0; while(x) { z=x%10; sum+=z; x=x/10; } if(sum%10==0) { s++; } if(y%10==9) { pos1=y+1; flag1=1; break; } } if(flag1==1) { for(i=b; i>=pos1; i--) { x=i; y=i; sum=0; while(x) { z=x%10; sum+=z; x=x/10; } if(sum%10==0) { s++; } if(y%10==0) { pos2=y-1; flag2=1; break; } } } if(flag1==1&&flag2==1) s+=(pos2-pos1+1)/10; printf("Case #%I64d: %I64d\n",num,s); } return 0; }
K题:
题目地址:HDU 4726
思路是跟队友讨论的,但代码不是我敲的。。细节我也不清楚。。
具体思路是保存上下每个数字的出现次数,然后根据次数直接计算,而不是一个个查找。对于第一位数字需要特判,不能出现9+0的这种情况。然后从和为9的组合开始查找(其实不能叫查找。。直接哈希)。
代码如下:
#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; }
L题:
题目地址:HDU 4727
这题不难,但很坑!!这也是我被队友嫌弃的一道题。。sad。。。没写Case就直接提交了。。。简直sad。。。
需要注意的两个坑点是
1:第一个人也是会出错的,所以当发现后面都没出错后,那就是第一个出错了。
2:如果过程中有一个人出错了,那后面的人会跟着错误的来,而不是根据正确的来。
只要注意了这两个坑点,就很容易了。(幸亏想到了这两个坑点。。不然会更被队友嫌弃的。。。。sad。。)
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int a[1000000]; int main() { int t, num=0, n, i, j, x; scanf("%d",&t); while(t--) { num++; scanf("%d",&n); x=0; int pos; for(i=0;i<n;i++) { scanf("%d",&a[i]); } for(i=1;i<n;i++) { if(a[i]!=a[i-1]+1) { x++; pos=i; } } printf("Case #%d: ",num); if(x==1) printf("%d\n",pos+1); else printf("1\n"); } return 0; }
原文:http://blog.csdn.net/scf0920/article/details/36914331