8月11号小练

水题，不解释

代码： 0ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 using namespace std;
 5 int d[26]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
 6 int main()
 7 {
 8     char a[300];
 9     int c,i,sum,len;
10     while(gets(a)&&strcmp(a,"#")!=0)
11     {
12         sum=0;
13         len=strlen(a);
14         for(i=0;i<len;i++)
15         {
16             if(a[i]==' ')
17                 continue;
18             c=(int)a[i];
19             sum+=d[c-65]*(i+1);
20         }
21         printf("%d
",sum);
22     }
23     return 0;
24 }

View Code

B 搜索，和以前的逃离迷宫很像，判断转弯的个数连连看 HDU 1175

先把代码放着 2671ms/10000ms

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 struct T
 5 {
 6    int x,y,turn;
 7 }q[1000024];
 8 int map[1024][1024],n,m,k;
 9 int d[4][2]={ 0,1,1,0,0,-1,-1,0  };
10 int hash[1024][1024];
11 int inline push( const int x,const int y,const int turn,int end )
12 {
13     T t;
14     t.x=x;t.y=y;
15     t.turn=turn;
16     q[ end++ ] = t;
17     return end;    
18 }
19 bool inline judge( int x,int y )       //判断
20 {
21    if( x>n||x<=0||y>m||y<=0 ) 
22      return false;
23    else if( map[x][y]==0 )
24          return true;
25         else return false;    
26 }
27 bool inline BFS( int X1,int Y1,int X2,int Y2 )
28 {
29     memset( hash,0,sizeof( hash ) );
30     int first=0,end=0;
31     end=push( X1, Y1, -1, end );  //存点
32     hash[X1][Y1]=1;    //标记
33     while( first< end )
34     {
35         if( q[first].turn>=2 )  
36            return false;
37         for( int i=0;i<4; i++ )
38         {
39            int dx=q[first].x + d[i][0];
40            int dy=q[first].y + d[i][1];
41            int turn=q[first].turn + 1;       //转弯+1
42            while( judge( dx,dy )||( dx==X2 && dy == Y2 ) ) 
43            {
44                 if( dx==X2 && dy == Y2 && map[dx][dy]==map[X1][Y1])     //满足条件 
45                     return true;
46                 if( !hash[dx][dy] ) 
47                 {
48                   hash[dx][dy]=1;
49                   end = push( dx,dy,turn,end );       
50                  }
51                 dx += d[i][0];   //直走
52                 dy += d[i][1]; 
53            }    
54         }
55         first++;       
56     }
57     return false;     
58 }
59 int main()
60 { 
61    int x,X1,Y1,X2,Y2;
62    while( scanf( "%d%d",&n,&m ),n||m )
63   { 
64       for( int i=1;i<=n;i++ )
65         for( int j=1;j<=m;j++ )
66             scanf( "%d",&map[i][j] );
67        scanf( "%d",&x );
68       for( int i=0;i<x; i++ )
69       {
70           scanf( "%d%d%d%d",&X1,&Y1,&X2,&Y2 );
71           if( X1==X2&&Y1==Y2 )   //同一点
72             printf( "NO
" ); 
73           else
74           {
75               if( map[X1][Y1]!=0&&map[X1][Y1]==map[X2][Y2]&&BFS( X1,Y1,X2,Y2 ) )
76                 printf( "YES
" ) ;
77               else printf( "NO
" );  
78          }  
79       }   
80    }
81    return 0;    
82 }

C 敌兵布阵 HDU 1166 可用线段树，树状数组，我是用树状数组做的。

代码：156MS

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 int n, a[50005];
 6 char b[6];
 7 void update(int i,int val)
 8 {
 9     while(i<= n)
10     {
11         a[i]+=val;
12         i+=i&(-i);
13     }
14 }
15 int sum(int i)
16 {
17     int s=0;
18     while(i>0)
19     {
20         s+=a[i];
21         i-=i&(-i);
22     }
23     return s;
24 }
25 int main()
26 {
27     int i, val, t, x, y, w= 1;
28     scanf("%d", &t);
29     while(t--)
30     {
31         memset(a, 0, sizeof(a));
32         scanf("%d", &n);
33         for(i=1; i<=n;i++)
34         {
35             scanf("%d",&val);
36             update(i,val);
37         }
38         printf("Case %d:
",w++);
39         while(scanf("%s",b))
40         {
41             if(b[0]=='E')
42                 break;
43             scanf("%d%d",&x,&y);
44             if(b[0]=='A')
45                 update(x,y);
46             else if(b[0]=='S')
47                 update(x,-y);
48             else
49             printf("%d
",sum(y)-sum(x-1));
50         }
51     }
52     return 0;
53 }

D Bone Collector HDU 2602 背包基础

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 int main()
 6 {
 7     int x[1005], y[1005],c,dp[100050],m,n,i,k;
 8     scanf("%d",&c);
 9     while(c--)
10     {
11         memset(dp, 0, sizeof(dp));
12         scanf("%d%d",&n,&m);
13         for(i=0; i<n; i++)
14             scanf("%d",&y[i]);
15         for(i=0; i<n; i++)
16             scanf("%d",&x[i]);
17         for(i=0; i<n; i++)
18                 for(k=m; k>=x[i]; k--)
19                     dp[k]=max(dp[k],dp[k-x[i]]+y[i]);
20         printf("%d
",dp[m]);
21     }
22     return 0;
23 }

E 龟兔赛跑 HDU 2059 神题Orz DP

代码： 15ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6   int n,i,j;
 7   double L,l,t,v1,v2,v3,dp[105],time,minn,p[105];
 8   while(~scanf("%lf",&L))
 9   {
10     scanf("%d%lf%lf%lf%lf%lf",&n,&l,&t,&v1,&v2,&v3);
11     for(i=1;i<=n;i++)
12       scanf("%lf",&p[i]);
13     p[0]=0;
14     p[i]=L;
15     for(i=1;i<=n+1;i++)
16       dp[i]=999999999.0;    //初始化为无穷大
17     dp[0]=0;;
18     for(i=1;i<=n+1;i++)
19       for(j=0;j<=i-1;j++)
20       {
21         if(p[i]-p[j]<=l)
22           time=t+(p[i]-p[j])/v2;
23         else
24           time=l/v2+(p[i]-p[j]-l)/v3+t;
25         if(j==0)
26           time-=t;
27         minn=dp[j]+min(time,(p[i]-p[j])/v3);
28         dp[i]=min(dp[i],minn);
29       }
30       if(dp[n+1]<L/v1*1.0)
31         printf("What a pity rabbit!
");
32       else
33         printf("Good job,rabbit!
");
34   }
35   return 0;
36 }