此次练习的地址：  http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26732#overview

密码 acmore

Problem A(POJ1753)

题目：

直接拿二进制模拟暴力枚举

之前已经做过了的

这次又WA了两次才AC，细心细心再细心！！！代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define MAX(a,b) (a) > (b)? (a):(b)10 #define MIN(a,b) (a) < (b)? (a):(b)11 #define mem(a) memset(a,0,sizeof(a))12 #define INF 100000000713 #define MAXN 2000514 using namespace std;15 16 int ma;17 int m;18 int ok;19 int meiju(int st)20 {21 int i;22 for(i=0;i<16;i++)23 {24 if((1<
              
               =4)28 {29 m ^= (1<<(i-4));30 }31 if(i%4>0)32 {33 m ^= (1<<(i-1));34 }35 if(i%4<3)36 {37 m ^= (1<<(i+1));38 }39 if(i+4<16)40 {41 m ^= (1<<(i+4));42 }43 }44 }45 if(m == 0 || m == (1<<16)-1)return 1;46 return 0;47 }48 49 int main()50 {51 ok =0;52 ma =0;53 int i,j;54 char str[4];55 for(i=0;i<4;i++)56 {57 scanf("%s",str);58 for(j=0;j<4;j++)59 {60 if(str[j] == 'b')61 ma ^= (1<<(i*4+j));62 }63 }64 int min =INF;65 for(i=0;i<(1<<16);i++)66 {67 m = ma;68 if(meiju(i))69 {70 int ans =0;71 for(j=0;j<16;j++)72 {73 if((1<
              
             
            
           
          
         
        
       
      

 

Problem B（POJ2965）

题目：

与上题一样，同样两次没过==！ 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define MAX(a,b) (a) > (b)? (a):(b)10 #define MIN(a,b) (a) < (b)? (a):(b)11 #define mem(a) memset(a,0,sizeof(a))12 #define INF 100000000713 #define MAXN 2000514 using namespace std;15 16 int ma;17 int m;18 int meiju(int st)19 {20 int i;21 for(i=0;i<16;i++)22 {23 if((1<
              
                ans)65 {66 min = ans;67 key = i;68 }69 }70 }71 printf("%d\n",min);72 for(i =0 ;i<16;i++)73 {74 if((1<
              
             
            
           
          
         
        
       
      

 

problem C

我的方法是直接用一个数组  sum[i][j]存入从左上角为0,0，右下角为（i，j）的矩形的树的个数。

这样的话边长为a， b的矩形内部的树的个数就是

                                         sum[i][j]-sum[i-a][j]-sum[i][j-b]+sum[i-a][j-b];

枚举小矩形的起点就行

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define MAX(a,b) (a) > (b)? (a):(b)10 #define MIN(a,b) (a) < (b)? (a):(b)11 #define mem(a) memset(a,0,sizeof(a))12 #define INF 100000000713 #define MAXN 2000514 using namespace std;15 16 int map[101][101];17 int sum[101][101];18 int n,width,height;19 20 int shuru()21 {22 mem(map);23 mem(sum);24 while(scanf("%d",&n)!=EOF && n)25 {26 int j,i,a,b;27 for(i=0;i<=n;i++)28 {29 scanf("%d%d",&a,&b);30 map[b][a] = 1;31 }32 for(i=1;i<=100;i++)33 {34 for(j=1;j<=100;j++)35 {36 sum[i][j] = map[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];37 }38 }39 scanf("%d%d", &width, &height);40 return 1;41 }42 return 0;43 }44 45 int f()46 {47 int i,j;48 int max = 0;49 for(i=height;i<=100;i++)50 {51 for(j=width;j<=100;j++)52 {53 max = MAX(sum[i][j]-sum[i][j-width]-sum[i-height][j]+sum[i-height][j-width], max);54 }55 }56 return max;57 }58 59 int main()60 {61 while(shuru())62 {63 printf("%d\n",f());64 }65 return 0;66 }
             
            
           
          
         
        
       
      

 

problem D

 坑爹的题目啊，之前做一直wa，后来实在是没办法，就参见了大神的代码，发现原来自己完全理解错了题目意思了。题目大意是说要让他不能亏，但是每次都是最坏的情况，也就是说每次投注之后，中的都是最少的哪一个。

最后还是参见了大神的思路，按投注的硬币的个数枚举，但每次放一个硬币时都是放在目前能都得到的最少的那一堆。所以复杂度就是O(coins)

代码：

 

1 #include 
      
        2 #include 
       
         3 #define MAX(a,b) (a)>(b)?(a):(b) 4 int main() 5 { 6     double x,y,z; 7     int coins; 8     int T; 9     while(~scanf("%d",&T))while(T--)10     {11         int get[3]={
    0},put[3]={
    0},mul[3];12         scanf("%d%lf%lf%lf", &coins, &x, &y, &z);13         mul[0] = (int)floor(x*100 + 0.5);14         mul[1] = (int)floor(y*100 + 0.5);15         mul[2] = (int)floor(z*100 + 0.5);16         int i,index = 0;17         int ans = coins;18         for(i=1;i<=coins;i++)19         {20             put[index] ++ ;21             get[index] = put[index] * mul[index]/100;22             index = get[0] < get[1] ? 0 : 1;//找到能够得到的最少的那一堆23             index = get[index] < get[2] ? index : 2;24             ans = MAX(ans, get[index]+coins-i);25         }26         printf("%d\n", ans);27     }28     return 0;29 }
       
      

 

 

 

 

problem E

WA了

 

problem F

起初觉得可以拿母函数做但是却发现，有个坑爹的条件就是Your program should be able to handle up to 100 coins.这句话，银币数目不可以超过100个

于是我换了一个想法，用记忆化的搜索，d[i][j][k]表示要凑齐i数值，开始用第j种硬币，还可以用k个硬币，为了不超时，记忆化一下。结果居然0Ms过了，真是奇迹~~~~

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define MAX(a,b) (a) > (b)? (a):(b)10 #define MIN(a,b) (a) < (b)? (a):(b)11 #define mem(a) memset(a,0,sizeof(a))12 #define INF 100000000713 #define MAXN 2000514 using namespace std;15 16 int f[251][6][101],vis[251][6][101];17 int val[6]={ 0,1,5,10,25,50};18 19 20 int dfs(int v,int c,int rest)21 {22 if(vis[v][c][rest])return f[v][c][rest];23 vis[v][c][rest] = 1;24 if(c == 1 && rest >= 0 && v<=rest)return f[v][c][rest]=1;25 else if(c == 1 && (rest <0 || v > rest))return 0;26 int i,m = v/val[c];27 f[v][c][rest] = 0;28 for(i=0;i<=m;i++)29 {30 f[v][c][rest]+=dfs(v-val[c]*i, c-1, rest-i);31 }32 return f[v][c][rest];33 }34 35 int main()36 {37 mem(f);38 mem(vis);39 int n;40 while(~scanf("%d",&n))41 {42 int k;43 if(n == 0){printf("1\n");continue;}44 if(n<5)k=1;45 else if(n<10)k=2;46 else if(n<25)k=3;47 else if(n<50)k=4;48 else k =5;49 printf("%d\n",dfs(n,k,100));50 }51 return 0;52 }