8-11-Exercise

链接：第四次小练

A.POJ 3094   Quicksum

水题中的水题啊~

直接上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

char a[300];

int main()
{
    while(1)
    {
        memset(a,0,sizeof(a));
        gets(a);
        if(a[0]=='#') break;
        int i,j,sum=0,k;
        int n=strlen(a);
        for(i=0;i<n;i++)
        {
            k=a[i]-'A'+1;
            if(a[i]==' ') k=0;
            sum+=k*(i+1);
        }
        printf("%d
",sum);
    }
    return 0;
}

//memory：160KB  time：0ms

B.HDU 1175   连连看

与以前那道逃离迷宫其实很像..................这道题中采用的是先往一个方向走，到没有路了，换一个方向的时候，就是转弯的时候，记录转弯次数~

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

class Node
{
public:
    int x,y,turn;
}q[1000024];

int n,m,a[1010][1010],x1,x2,y1,y2,add[4][2]={{0,1},{0,-1},{1,0},{-1,0}},hash[1010][1010];

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>0 && y<=m && y>0 && a[x][y]==0)
        return true;
    else return false;
}

bool inline bfs(int x,int y)
{
    memset(hash,0,sizeof(hash));
    int f=0,end=0;
    end=push(x,y,-1,end);
    hash[x][y]=1;
    while(f<end)
    {
        if(q[f].turn>=2) return false;
        for(int i=0;i<4;i++)
        {
            int dx=q[f].x+add[i][0];
            int dy=q[f].y+add[i][1];
            int turn=q[f].turn+1;
            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]=1;
                    end=push(dx,dy,turn,end);
                }
                dx+=add[i][0];                 //在往该方向还能走的时候，继续往该方向走~
                dy+=add[i][1];
            }

        }
        f++;
    }
    return false;
}

int main()
{
    while(scanf("%d%d",&n,&m),n,m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;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]==0 || a[x2][y2]==0 || a[x1][y1]!=a[x2][y2]) {printf("NO
");continue;}
            if(bfs(x1,y1))
                printf("YES
");
            else
                printf("NO
");
        }
    }
    return 0;
}

//memory：8308KB   time：3562ms

C.HDU 1166   敌兵布阵

其实......哎这道题做过╮(╯▽╰)╭......链接：→_→

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX=55555;
int a[MAX<<2];

void build(int l,int r,int x)
{
    if(l==r)
    {
        scanf("%d",&a[x]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,x<<1);
    build(mid+1,r,x<<1|1);
    a[x]=a[x<<1]+a[x<<1|1];
}

void update(int p,int w,int l,int r,int x)
{
    if(l==r)
    {
        a[x]+=w;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(p,w,l,mid,x<<1);
    else
        update(p,w,mid+1,r,x<<1|1);
    a[x]=a[x<<1]+a[x<<1|1];
}

int query(int le,int ri,int l,int r,int x)
{
    if(le<=l && ri>=r)
        return a[x];
    int mid=(l+r)>>1,re=0;
    if(le<=mid) re+=query(le,ri,l,mid,x<<1);
    if(ri>mid) re+=query(le,ri,mid+1,r,x<<1|1);
    return re;
}

int main()
{
    int t,n,cas=0;
    char str[10];
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d:
",++cas);
        scanf("%d",&n);
        build(1,n,1);
        while(1)
        {
            scanf("%s",str);
            if(str[0]=='E') break;
            int a,b;
            scanf("%d%d",&a,&b);
            if(str[0]=='Q') printf("%d
",query(a,b,1,n,1));
            else
                if(str[0]=='S') update(a,-b,1,n,1);
            else
                update(a,b,1,n,1);
        }
    }
    return 0;
}

//memory：768KB  time：218ms

D.HDU 2602   Bone Collector

很水~DP

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int w[1111],v[1111],f[43333];

int main()
{
    int t,N,V,i,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        scanf("%d%d",&N,&V);
        for(i=1;i<=N;i++)
            scanf("%d",&v[i]);
        for(i=1;i<=N;i++)
            scanf("%d",&w[i]);
        for(i=1;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
",f[V]);
    }
    return 0;
}

//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=1;i<=n;i++)
            scanf("%d",&a[i]);
        a[0]=0;
        dp[0]=0.0;
        a[n+1]=l;
        for(int i=1;i<=n+1;i++)
        {
            dp[i]=DBL_MAX;
            for(int j=0;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+1]>rabit_time)
            printf("Good job,rabbit!
");
        else
            printf("What a pity rabbit!
");
    }
    return 0;
}

//memory：284KB  time：15ms