Stanford's ACM 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 AB Problem (0)

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

View Code

#include <stdio.h>int main()
{int a,b;scanf(%d %d,&a, &b);printf(%d\n,ab);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;
}

·100 Hangover (1)

模拟题目的描述即可。

View Code

/*
Author: nevergo
Task: POJ 100 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/(ans1);if (sta>=tar) break; ans;}printf(%d card(s)\n,ans);}return 0;
}

·1007 DA 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=j1;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[j1]){sort[0]=sort[j]; sort[j]=sort[j1]; sort[j1]=sort[0];id[0]=id[j]; id[j]=id[j1]; id[j1]=id[0];}for (i=1;i<=m;i) printf(%s\n,s[id[i]]);}return 0;
}

·216 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 ()

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

View Code

#include <stdio.h>
#include <math.h>int main()
{int m, i, n, sum = 0;scanf(%d,&m);n = (int)(sqrt(((double)(18*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 umbers ()

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

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 ,i;scanf(%d,&);while (--){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[0][0];
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[x1][y]<0) a[x1][y]=a[x][y]1;if (a[x-1][y]<0) a[x-1][y]=a[x][y]1;if (a[x][y1]<0) a[x][y1]=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[0][0];slice;print(u*21);if (dep==u1) return;for (i=1;i<=u*21;i)for (j=1;j<=u*21;j){b[i][j]=a[i][j];a[i][j]--;}for (i=1;i<=u*21;i)for (j=1;j<=u*21;j)if (a[i][j]==u-1) expend(i,j);dfs(dep1,u);for (i=1;i<=u*21;i)for (j=1;j<=u*21;j)a[i][j]=b[i][j];slice;print(u*21);
}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[u1][u1]=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]*nx;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*10s[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*600t)) ans=4.5/v*600t;}printf(%.0lf\n,ceil(ans));}return 0;
}

·251 Big Square (6, challenge problem)

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

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

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

View Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 110char map[MAX][MAX];
double Jx[MAX*MAX],Jy[MAX*MAX];
double x2,x,x,x4,dx;
double y2,y,y,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=i1;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=(x1x2)/2; y=(y1y2)/2;dx=(x1-x2)*1.0/2; dy=(y1-y2)*1.0/2;x=xdy; y=y-dx;x4=x-dy; y4=ydx;a=floor(x0.5); b=floor(y0.5);c=floor(x40.5); d=floor(y40.5);if (a<1||a>n||b<1||b>n) continue;if (c<1||c>n||d<1||d>n) continue;if (fabs(a-x)>e||fabs(b-y)>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;
}

·140 Hotline (9, challenge problem)

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

转载于:.html