Stanford's ACM Training Course—Chapter#01 Introduction

Training Course—Chapter#01 Introduction"/>

Stanford's ACM Training Course—Chapter#01 Introduction

最近想要完成Stanford's ACM Training Course，我会将课件和练习题发上来。

Coding Exercise

Assignment 1: Coding Exercise

·1000 A+B Problem (0)

这道题目没有什么好说的。。。

View Code

#include <stdio.h>int main()
{int a,b;scanf("%d %d",&a, &b);printf("%d\n",a+b);return 0;
}

·1004 Financial Management (0)

和上一道一样，没有什么好解释的。

View Code

#include <stdio.h>int main()
{double ans=0,tmp;int i;for (i=0;i<12;i++){scanf("%lf",&tmp);ans+=tmp;}ans/=12;printf("$%.2lf\n",ans);return 0;
}

·1003 Hangover (1)

模拟题目的描述即可。

View Code

/*
Author: nevergo
Task: POJ 1003 HangOver
Language: C 
*/
#include <stdio.h>
#include <stdlib.h>int main()
{double tar,sta;int ans;while (scanf("%lf",&tar)){if (tar==0.00) break;ans=1; sta=0;while (1){sta+=1.0/(ans+1);if (sta>=tar) break; ans++;}printf("%d card(s)\n",ans);}return 0;
}

·1007 DNA Sorting (2)

简单字符串排序题目。

View Code

#include <stdio.h>
typedef char str[60];str s[110];
int sort[110],id[110];
int n,m;int main()
{int i,j,k;while (scanf("%d%d\n",&n,&m)!=EOF){for (i=1;i<=m;i++){id[i]=i;scanf("%s",s[i]);sort[i]=0;for (j=0;j<n;j++)for (k=j+1;k<n;k++)if (s[i][j]>s[i][k]) sort[i]++;}for (i=1;i<=m;i++)for (j=1;j<=m-i;j++)if (sort[j]>sort[j+1]){sort[0]=sort[j]; sort[j]=sort[j+1]; sort[j+1]=sort[0];id[0]=id[j]; id[j]=id[j+1]; id[j+1]=id[0];}for (i=1;i<=m;i++) printf("%s\n",s[id[i]]);}return 0;
}

·2136 Vertical Histogram (2)

统计字母出现的个数，就是输出有一点恶心。

View Code

#include <stdio.h>int main()
{int count[26];int i,j,max;char tmp;memset(count,0,sizeof(count));while (scanf("%c",&tmp)!=EOF){if (tmp>='A'&&tmp<='Z')count[tmp-'A']++;}max=0;for (i=0;i<26;i++)if (count[i]>max) max=count[i];for (i=max;i>0;i--)for (j=0;j<26;j++){if (count[j]<i) printf(" ");else printf("*");if (j<25) printf(" ");else printf("\n");}for (i=0;i<26;i++){printf("%c",i+'A');if (i<25) printf(" ");else printf("\n");}printf("\n");return 0;
}

·2140 Herd Sums (3)

简单数学题，不解释。。。

View Code

#include <stdio.h>
#include <math.h>int main()
{int m, i, n, sum = 0;scanf("%d",&m);n = (int)(sqrt(((double)(1+8*m))+1)/2);for (i = 1; i <= n; i++){if ((i % 2 == 1) && (m % i == 0)) sum ++;if ((i % 2 == 0) && (m % (i/2) == 0) && (m % i != 0)) sum ++;}printf("%d\n",sum);return 0;
}

·1504 Adding Reversed Numbers (3)

简单题目，考虑到可能出现高精度数，就用了高精度加法。。。

View Code

#include <stdio.h>
#include <string.h>char s1[100],s2[100];
int a[100],b[100];void add()
{int i=1,x=0;if (b[0]>a[0]) a[0]=b[0];for (i=1;i<=a[0];i++){a[i]+=b[i]+x;x=a[i]/10;a[i]%=10;}if (x) { a[0]++; a[a[0]]=x; }
}int main()
{int N,i;scanf("%d",&N);while (N--){scanf("%s%s",s1,s2);memset(a,0,sizeof(a));memset(b,0,sizeof(b));a[0]=strlen(s1);b[0]=strlen(s2);for (i=1;i<=a[0];i++) a[i]=s1[i-1]-'0';for (i=1;i<=b[0];i++) b[i]=s2[i-1]-'0';add();for (i=1;i<=a[0];i++)if (a[i]) break;for (;i<=a[0];i++)printf("%d",a[i]);printf("\n");}return 0;
}

·1806 Manhattan 2025 (4)

模拟一个点广搜扩展的情况，可以采用递归输出，这样比较简单。。。

View Code

#include <stdio.h>
#include <memory.h>int a[30][30];
int slice;void print(int n)
{int i,j;printf("slice #%d:\n",slice);for (i=1;i<=n;i++){for (j=1;j<=n;j++)if (a[i][j]<0) printf(".");else printf("%d",a[i][j]);printf("\n");}
}void expend(int x,int y)
{if (a[x+1][y]<0) a[x+1][y]=a[x][y]+1;if (a[x-1][y]<0) a[x-1][y]=a[x][y]+1;if (a[x][y+1]<0) a[x][y+1]=a[x][y]+1;if (a[x][y-1]<0) a[x][y-1]=a[x][y]+1;
}void dfs(int dep,int u)
{int i,j;int b[30][30];slice++;print(u*2+1);if (dep==u+1) return;for (i=1;i<=u*2+1;i++)for (j=1;j<=u*2+1;j++){b[i][j]=a[i][j];a[i][j]--;}for (i=1;i<=u*2+1;i++)for (j=1;j<=u*2+1;j++)if (a[i][j]==u-1) expend(i,j);dfs(dep+1,u);for (i=1;i<=u*2+1;i++)for (j=1;j<=u*2+1;j++)a[i][j]=b[i][j];slice++;print(u*2+1);
}int main()
{int test,i;int u;scanf("%d",&test);for (i=1;i<=test;i++){memset(a,-1,sizeof(a));printf("Scenario #%d:\n",i);scanf("%d",&u);a[u+1][u+1]=u;slice=0;if (u==0) printf("slice #1:\n0\n");else dfs(1,u);printf("\n");}return 0;
}

·1001 Exponentiation (5)

高精度小数乘法，和普通乘法一样，我们只要在计算时将小数点拿掉，最后在结果上加入小数点。这道题目的坑还是挺多的。。。

View Code

#include <stdio.h>
#include <string.h>
#include <memory.h>
#include <stdlib.h>int a[1000];
char s[10];
int n,b;void mul(int n)
{int i,x=0;for (i=1;i<=a[0];i++){a[i]=a[i]*n+x;x=a[i]/10;a[i]=a[i]%10;}while (x){a[0]++;a[a[0]]=x%10;x=x/10;}
}int main()
{int point,i;int l, r;while (scanf("%s %d",s,&n)!=EOF){memset(a,0,sizeof(a));b=point=0;l=0; r=5;while (s[l]=='0') l++;while (s[r]=='0') r--;for (i=r;i>=l;i--)if (s[i]=='.') point=r-i;else{a[0]++;a[a[0]]=s[i]-'0';}for (i=l;i<=r;i++)if (s[i]!='.') b=b*10+s[i]-'0';for (i=1;i<n;i++)mul(b);point=point*n;while (a[a[0]]==0) a[0]--;if (a[0]<point) a[0]=point;for (i=a[0];i>point;i--) printf("%d",a[i]);if (point>0) printf(".");for (i=point;i>0;i--) printf("%d",a[i]);printf("\n");}return 0;
}

·1922 Ride to School (5)

题目描述看着挺长的，其实就是求出哪一个同学最早到Yanyuan（不考虑出发时间为负的同学）。。

View Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>int n,v,t;
double ans;int main()
{while (scanf("%d",&n)!=EOF&&n!=0){ans=1e20;while (n--){scanf("%d%d",&v,&t);if ((t>=0)&&(ans>4.5/v*3600+t)) ans=4.5/v*3600+t;}printf("%.0lf\n",ceil(ans));}return 0;
}

·3251 Big Square (6, challenge problem)

这是一道巨坑无比的题目。。。一开始没有注意到正方形的边可能不与边界平行，然后利用几何关系求解坐标的时候，没考虑到dx和dy的正负号。。。。

这道题目网上流传两种算法：1.二分图最大匹配（至今未了解原因，以后补上）；2.暴搜+剪枝。我是采用方法2解决的。

我们考虑知道了正放形的什么我们可以确定一个正方形呢？答案就是对角线，于是我们就可以枚举正方形的对角线，然后利用全等关系求出另一条对角线的端点坐标，这时候判断一下即可。接下里讲一下端点的求法：我们设(x₁,y₁),(x₂,y₂)是两对角线的坐标，中点坐标为(x=(x₁+x₂)/2,y(y₁+y₂)/2)，那么另外两点坐标为(x₃=x+dy,y₃=y-dx)，(x₄=x-dy, y₄=y+dx)其中dx=(x₁-x₂)/2，dy=(y₁-y₂)/2，这个可以画图验证。

View Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 110char map[MAXN][MAXN];
double Jx[MAXN*MAXN],Jy[MAXN*MAXN];
double x2,x,x3,x4,dx;
double y2,y,y3,y4,dy;
int n,ans,m,i,j;
int a,b,c,d;
double e=1e-6;int main()
{double x1,y1;scanf("%d\n",&n);m=ans=0;for (i=1;i<=n;i++){for (j=1;j<=n;j++){scanf("%c",&map[i][j]);if (map[i][j]=='J'){Jx[m]=i; Jy[m]=j;m++;}}scanf("%c",&map[i][j]);}for (i=0;i<m;i++)for (j=i+1;j<m;j++){x1=Jx[i]; y1=Jy[i];x2=Jx[j]; y2=Jy[j];if (pow(x1-x2,2)+pow(y1-y2,2)<=ans<<1) continue;x=(x1+x2)/2; y=(y1+y2)/2;dx=(x1-x2)*1.0/2; dy=(y1-y2)*1.0/2;x3=x+dy; y3=y-dx;x4=x-dy; y4=y+dx;a=floor(x3+0.5); b=floor(y3+0.5);c=floor(x4+0.5); d=floor(y4+0.5);if (a<1||a>n||b<1||b>n) continue;if (c<1||c>n||d<1||d>n) continue;if (fabs(a-x3)>e||fabs(b-y3)>e||fabs(c-x4)>e||fabs(d-y4)>e) continue;if (map[a][b]=='B'||map[c][d]=='B') continue;if (map[a][b]=='J'||map[c][d]=='J')ans=((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))/2;}printf("%d\n",ans);return 0;
}

·1403 Hotline (9, challenge problem)

难度9的题目，不会做啊。。。。。

转载于:.html