地址:http://www.bnuoj.com/bnuoj/contest_show.php?cid=2836
A题 HDU 1071
定积分题,高中的...
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int n,i;
double x0,y0,x1,y1,x2,y2,k,b,a,c,h,s;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf%lf%lf",&x0,&y0,&x1,&y1,&x2,&y2);
k=(y2-y1)/(x2-x1);
b=y1-k*x1;
h=x0;
c=y0;
a=(y1-c)/((x1-h)*(x1-h));
s=(a*x2*x2*x2/3-(2*a*h+k)*x2*x2/2+(a*h*h+c-b)*x2)-(a*x1*x1*x1/3-(2*a*h+k)*x1*x1/2+(a*h*h+c-b)*x1);
printf("%.2f\n",s);
}
return 0;
}
B题 HDU 1219
因为每次在循环里重新计算字符串长度而TLE了。..觉得实在有些逗 第一次这么T,下次注意
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int times[50];
char buf[200000];
int main()
{
int i,l;
while(gets(buf))
{
memset(times,0,sizeof(times));
l=strlen(buf);
for(i=0;i<l;i++)
{
if(isalpha(buf[i]))
times[buf[i]-'a']++;
}
for(i=0;i<26;i++)
printf("%c:%d\n",'a'+i,times[i]);
printf("\n");
}
return 0;
}
C题 HDU 1282
先是因为OJ不识别strrev函数而CE,再是第一个数一直按照n值输出而WA了几次,n值是一直变的。...
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
char a[100],b[100];
int m[50005];
void strrrev(char h[])
{
int i,j;
char c;
for(i=0,j=strlen(h)-1;i<strlen(h)/2;i++,j--)
{
c=h[i];
h[i]=h[j];
h[j]=c;
}
h[strlen(h)]='\0';
}
int main()
{
int n,i,t,k;
while(scanf("%d",&n)!=EOF)
{
k=n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(m,0,sizeof(m));
t=0;
sprintf(a,"%d",n);
strcpy(b,a);
strrrev(b);
while(strcmp(a,b)!=0)
{
n=atoi(a)+atoi(b);
memset(a,0,sizeof(a));
sprintf(a,"%d",n);
m[t]=n;
t++;
strcpy(b,a);
strrrev(b);
}
printf("%d\n",t);
printf("%d",k);
for(i=0;i<t;i++)
printf("--->%d",m[i]);
printf("\n");
}
return 0;
}
D题 poj 2386
dfs水题,但是卡了我好久,因为在dfs函数里递归我写成了中括号[ ],而且编译器没有报错.....看了半天没看出逻辑错误可是答案就是出不来...
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int visit[105][105];
char a[105][105];
int n,m;
void dfs(int i,int j)
{
if(!visit[i][j])
{
visit[i][j]=1;
if(a[i+1][j]==a[i][j]) dfs(i+1,j);
if(a[i-1][j]==a[i][j]) dfs(i-1,j);
if(a[i][j+1]==a[i][j]) dfs(i,j+1);
if(a[i][j-1]==a[i][j]) dfs(i,j-1);
if(a[i+1][j+1]==a[i][j]) dfs(i+1,j+1);
if(a[i+1][j-1]==a[i][j]) dfs(i+1,j-1);
if(a[i-1][j+1]==a[i][j]) dfs(i-1,j+1);
if(a[i-1][j-1]==a[i][j]) dfs(i-1,j-1);
}
return ;
}
int main()
{
memset(a,0,sizeof(a));
memset(visit,0,sizeof(visit));
int i,j,t=0;
char c;
scanf("%d%d",&n,&m);
c=getchar();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
scanf("%c",&a[i][j]);
c=getchar();
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(!visit[i][j]&&a[i][j]=='W')
{
dfs(i,j);
t++;
}
}
}
printf("%d\n",t);
return 0;
}
E题 POJ 2492
并查集问题,num数组分为0和1可看作是不同性别,unio时已知两异性如果num值又相同则矛盾
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int father[2005],num[2005];
int Find_set(int x)
{
if(father[x]==x) return x;
int t=Find_set(father[x]);
num[x]=(num[x]+num[father[x]])%2;
father[x]=t;
return father[x];
}
int Union(int a,int b)
{
int x,y;
x=Find_set(a);
y=Find_set(b);
if(x==y&&num[a]==num[b]) return 1;
else
{
father[x]=y;
num[x]=(num[a]+num[b]+1)%2;
}
return 0;
}
int main()
{
int t,n,i,m,flag,k=1;
int x,y;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
{
father[i]=i;
num[i]=0;
}
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
if(Union(x,y)==1) flag=1;
}
printf("Scenario #%d:\n",k++);
if(flag) printf("Suspicious bugs found!\n\n");
else printf("No suspicious bugs found!\n\n");
}
return 0;
}
F题 hdu 2544
最短路,以前做过
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
int n,m,a[105][105],i,j,k,x,y,t;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)
return 0;
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&t);
a[x][y]=t;
a[y][x]=t;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
if(a[i][j]&&a[i][k]&&(a[j][k]>a[i][j]+a[i][k]||a[j][k]==0))
a[j][k]=a[i][j]+a[i][k];
}
printf("%d\n",a[1][n]);
}
return 0;
}
G题 HDU 3232
基本没看懂题,英文水平有限..百度了一下才知道什么意思,通过数学期望得到2*L/V的公式(不记得学过)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int n,d,i,p,l,v,k=1;
double sum;
while(scanf("%d%d",&n,&d),n||d)
{
sum=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&p,&l,&v);
d-=l;
sum+=2.0*l/v;
}
sum+=d;
printf("Case %d: %.3lf\n\n",k++,sum);
}
return 0;
}
H题 POJ 1251
最小生成树,用的prim模板
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int map[50][50],dis[50];
int prim(int n) //复杂度O(N^2)
{
int result = 0;
int minCost;
int i,j,k;
dis[0] = -1; //从结点0开始
for(i = 1; i< n; i++)
dis[i] = map[0][i];
for(i = 1; i < n; i++) //找n-1条边
{
minCost = 99999999;
for(j = 1; j < n; j++) //找两个不想交集合的最小边
{
if(dis[j]>0 && dis[j]<minCost)
{
minCost = dis[j];
k = j;
}
}
dis[k] = -1; //找到，标记
result += minCost;
for(j = 1; j < n; j++) //加入这个结点后，更新两个集合的边。
{
if(map[k][j] < dis[j])
dis[j] = map[k][j];
}
}
return result;
}
int main()
{
int n,i,m,l,j;
char a,c;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
map[i][j]=99999999;
for(j=0;j<n-1;j++)
{
cin>> a>>m;
for(i=0;i<m;i++)
{
c=getchar();
cin>> c>>l;
map[a-'A'][c-'A']=l;
map[c-'A'][a-'A']=l;
}
}
printf("%d\n",prim(n));
}
return 0;
}
I题 HDU 1372
BFS裸题,我写的超繁琐
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
char visit[8][8];
struct node
{
int x,y;
}a[100];
int main()
{
char c1,c2,c;
int i;
node aa,bb,m,k;
while(scanf("%c%d %c%d",&c1,&aa.y,&c2,&bb.y)!=EOF)
{
memset(a,0,sizeof(a));
memset(visit,0,sizeof(visit));
aa.x=c1-'a'+1;
bb.x=c2-'a'+1;
queue<node> q;
q.push(aa);
visit[aa.x][aa.y]=1;
while(!q.empty())
{
m=q.front();
q.pop();
if(m.x==bb.x&&m.y==bb.y) break;
k.x=m.x+2;
k.y=m.y+1;
if(k.x<=8&&k.y<=8&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.y=m.y-1;
if(k.x<=8&&k.y>0&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.x=m.x-2;
if(k.x>0&&k.y>0&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.y=m.y+1;
if(k.x>0&&k.y<=8&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.x=m.x+1;
k.y=m.y+2;
if(k.x<=8&&k.y<=8&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.y=m.y-2;
if(k.x<=8&&k.y>0&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.x=m.x-1;
if(k.x>0&&k.y>0&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
k.y=m.y+2;
if(k.x>0&&k.y<=8&&!visit[k.x][k.y])
{
visit[k.x][k.y]=visit[m.x][m.y]+1;
q.push(k);
}
}
printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,aa.y,c2,bb.y,visit[bb.x][bb.y]-1);
c=getchar();
}
return 0;
}
总的来说这周题目比较简单,但是还是有不少问题浪费了很多时间,而且我写DFS和BFS都没有用dir二维数组的习惯,导致代码特别繁琐