A.POJ 3094 Quicksum
水题中的水题啊~
直接上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; char a[]; int main()
{
while()
{
memset(a,,sizeof(a));
gets(a);
if(a[]=='#') break;
int i,j,sum=,k;
int n=strlen(a);
for(i=;i<n;i++)
{
k=a[i]-'A'+;
if(a[i]==' ') k=;
sum+=k*(i+);
}
printf("%d\n",sum);
}
return ;
}
//memory：160KB time：0ms
B.HDU 1175 连连看
与以前那道逃离迷宫其实很像..................这道题中采用的是先往一个方向走，到没有路了，换一个方向的时候，就是转弯的时候，记录转弯次数~
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; class Node
{
public:
int x,y,turn;
}q[]; int n,m,a[][],x1,x2,y1,y2,add[][]={{,},{,-},{,},{-,}},hash[][]; int inline push(int x,int y,int turn,int end)
{
Node t;
t.x=x;
t.y=y;
t.turn=turn;
q[end++]=t;
return end;
} bool inline judge(int x,int y) //判断该点是否能走......
{
if(x<=n && x> && y<=m && y> && a[x][y]==)
return true;
else return false;
} bool inline bfs(int x,int y)
{
memset(hash,,sizeof(hash));
int f=,end=;
end=push(x,y,-,end);
hash[x][y]=;
while(f<end)
{
if(q[f].turn>=) return false;
for(int i=;i<;i++)
{
int dx=q[f].x+add[i][];
int dy=q[f].y+add[i][];
int turn=q[f].turn+;
while(judge(dx,dy)||(dx==x2 && dy==y2))
{
if(dx==x2 && dy==y2 && a[dx][dy]==a[x][y])
return true;
if(!hash[dx][dy])
{
hash[dx][dy]=;
end=push(dx,dy,turn,end);
}
dx+=add[i][]; //在往该方向还能走的时候，继续往该方向走~
dy+=add[i][];
} }
f++;
}
return false;
} int main()
{
while(scanf("%d%d",&n,&m),n,m)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
int k;
scanf("%d",&k);
while(k--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(a[x1][y1]== || a[x2][y2]== || a[x1][y1]!=a[x2][y2]) {printf("NO\n");continue;}
if(bfs(x1,y1))
printf("YES\n");
else
printf("NO\n");
}
}
return ;
}
//memory：8308KB time：3562ms
C.HDU 1166 敌兵布阵
其实......哎这道题做过╮(╯▽╰)╭......链接：→_→
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int MAX=;
int a[MAX<<]; void build(int l,int r,int x)
{
if(l==r)
{
scanf("%d",&a[x]);
return;
}
int mid=(l+r)>>;
build(l,mid,x<<);
build(mid+,r,x<<|);
a[x]=a[x<<]+a[x<<|];
} void update(int p,int w,int l,int r,int x)
{
if(l==r)
{
a[x]+=w;
return;
}
int mid=(l+r)>>;
if(p<=mid) update(p,w,l,mid,x<<);
else
update(p,w,mid+,r,x<<|);
a[x]=a[x<<]+a[x<<|];
} int query(int le,int ri,int l,int r,int x)
{
if(le<=l && ri>=r)
return a[x];
int mid=(l+r)>>,re=;
if(le<=mid) re+=query(le,ri,l,mid,x<<);
if(ri>mid) re+=query(le,ri,mid+,r,x<<|);
return re;
} int main()
{
int t,n,cas=;
char str[];
scanf("%d",&t);
while(t--)
{
printf("Case %d:\n",++cas);
scanf("%d",&n);
build(,n,);
while()
{
scanf("%s",str);
if(str[]=='E') break;
int a,b;
scanf("%d%d",&a,&b);
if(str[]=='Q') printf("%d\n",query(a,b,,n,));
else
if(str[]=='S') update(a,-b,,n,);
else
update(a,b,,n,);
}
}
return ;
}
//memory：768KB time：218ms
D.HDU 2602 Bone Collector
很水~DP
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int w[],v[],f[]; int main()
{
int t,N,V,i,j;
scanf("%d",&t);
while(t--)
{
memset(f,,sizeof(f));
memset(w,,sizeof(w));
memset(v,,sizeof(v));
scanf("%d%d",&N,&V);
for(i=;i<=N;i++)
scanf("%d",&v[i]);
for(i=;i<=N;i++)
scanf("%d",&w[i]);
for(i=;i<=N;i++)
for(j=V;j>=w[i];j--)
{
int temp=f[j-w[i]]+v[i];
f[j]=max(f[j],temp);
}
printf("%d\n",f[V]);
}
return ;
}
//memory：428KB time：15ms
E.HDU 2059 龟兔赛跑
DP
代码：
#include <stdio.h>
#include <iostream>
#include <float.h>
using namespace std; #define MAX 110
int a[MAX];
double dp[MAX]; int main()
{
int l,n,c,t,vr,v1,v2;
while(~scanf("%d%d%d%d%d%d%d",&l,&n,&c,&t,&vr,&v1,&v2))
{
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
a[]=;
dp[]=0.0;
a[n+]=l;
for(int i=;i<=n+;i++)
{
dp[i]=DBL_MAX;
for(int j=;j<i;j++)
{
double len=1.0*(a[i]-a[j]);
double temp=(len>=c)?((c*1.0)/v1+(len-c)*1.0/v2):((len*1.0)/v1);
if(j) temp+=t;
dp[i]=min(dp[i],dp[j]+temp);
}
}
double rabit_time=(l*1.0)/vr;
if(dp[n+]>rabit_time)
printf("Good job,rabbit!\n");
else
printf("What a pity rabbit!\n");
}
return ;
}
//memory：284KB time：15ms