首页 > ACM题库 > HDU-杭电 > HDU 3640-I, zombie-分治-[解题报告]HOJ
2014
11-30

HDU 3640-I, zombie-分治-[解题报告]HOJ

I, zombie

问题描述 :

The "endless" model in "I, zombie" of "Plants vs. Zombies" is my favourite.
The aim of the game is to put down the zombies most reasonable in the right-most , to eat the brain protected by Plants in the left-most.
Go , SuSu

To simplify the problem ,we provide only one kind of Zombies : normal Zombies with 50 hp each.
The map contains one row only, and we provide two kinds of plants : Peashooter (with 10hp) and Potato Mine.
The operating steps of every second are as below(Warning: make sure your program strictly follow the order of these steps):

1.Put some or none zombies in the right-most grid one by one. (In the right grid of the right-most plant at beginning).
2.Judge every survived zombie, whether he’s standing on a grid with a Peashooter.
    2.1.If it’s true, he attacks the Peashooter in his grid, and the Peashooter decreases 1 hp. The Peashooter’s hp may be negative at that moment, but it’s still alive!
    2.2.If it’s false, he moves left for one grid.
3.If there are still some zombies in the map, every survived Peashooter will shoot a pea to the zombie who was put earliest. (the zombie’s hp decreases 1 hp for each pea, the zombie’s hp can be negative at that moment, but it’s still alive!)
4.If there are zombies in the grids where Potato Mine stands , then the Potato Mine explodes , all the zombies’ hp in this grid become 0.
5.The plants and zombies with non-positive hp disappear(until now they are dead).

Now, given the map, you are to tell me how many zombies are needed at least, in order to eat the brain in the left-most?

输入:

The first line is a number T (1<=T<=100), represents the number of cases.
The next T line with n(0<n<=100) characters ,represents each case ,’P’ represents Peashooters ,’M’ represents Potato Mine ,no other character in the input.

输出:

The first line is a number T (1<=T<=100), represents the number of cases.
The next T line with n(0<n<=100) characters ,represents each case ,’P’ represents Peashooters ,’M’ represents Potato Mine ,no other character in the input.

样例输入:

5
PM
PP
PPP
MMMMM
PPMM

样例输出:

Case 1: 2
Case 2: 1
Case 3: 2
Case 4: 6
Case 5: 3

题目:I, zombie

题意:

植物大战僵尸的模拟题,地图只有一行,两种植物,一种会射弹,一种是炸弹,求僵尸胜利的最小个数。

解题思路:

第一感觉是没感觉,然后觉得好繁杂,各种情况。经过长久琢磨后,思路慢慢清晰,然后AC。觉得还是挺好的一道模拟题。

模拟时主要有三个问题要维护,一是植物的长度,二是最右边的植物种类,三是僵尸最左的位置。如果僵尸碰到的是炸弹,那么下一回合可以认为僵尸的最左位置为炸弹的左边。如果碰到的不是炸弹,则不停向左统计植物个数,直到遇到第一个炸弹,然后二分可以吃掉这些植物的最少僵尸个数,二分时要根具条件进行模拟。

 #include <iostream>
 #include <cstdio>
 #include <string>
 #include <cstring>
 #include <algorithm>
 #include <vector>
 #include <map>
 
 using namespace std;
 
 const int MAX = 100 + 10;
 char Plant[MAX];
 int P, M;
 int Flag;
 int E;
 int MozNum;
 void init(char plant[])
 {
     MozNum = 0;
     E = strlen(plant) - 1;
     P = M = 0;
     for(int i = 0; i <= E; ++i)
     {
         if(plant[i] == 'P')
             ++P;
         else
             ++M;
     }
 }
 
 int run(int apNum, int ppNum, int mozNum)
 {
     int flag = Flag;
     int pLife = 10, mozLife = 50;
     while(ppNum > 0 && mozNum > 0)
     {
         if(flag > 0)
         {
             --flag;
             mozLife -= apNum;
         }
         else
         {
             pLife -= mozNum;
             mozLife -= apNum;
         }
         if(pLife <= 0)
         {
             pLife = 10;
             apNum--;
             ppNum--;
             flag = 1;
         }
         if(mozLife <= 0)
         {
             mozLife = 50;
             mozNum--;
         }
     }
     if(ppNum <= 0 && mozNum > 0)
         return 1;
     if(ppNum <= 0 && mozNum <= 0)
         return 0;
     if(ppNum > 0)
         return -1;
 }
 int main()
 {
     freopen("in.txt", "r", stdin);
     int T;
     scanf("%d", &T);
     for(int t = 1; t <= T; ++t)
     {
         scanf("%s", Plant);
         init(Plant);
         if(Plant[E] == 'M')
         {
             E--;
             MozNum++;
             Flag = 2;
         }
         else
             Flag = 1;
         while(E >= 0)
         {
             if(Plant[E] == 'M')
             {
                 if(Flag > 1)
                 {
                     --Flag;
                     if(P >= 50)
                         ++MozNum;
                     continue;
                 }
                 else
                     MozNum++;
                 M--;
                 E--;
                 Flag = 2;
             }
             else
             {
                 int pNum = 0;
                 for(int i = E; i >= 0; --i)
                 {
                     if(Plant[i] == 'M')
                         break;
                     else
                         pNum++;
                 }
                 int left = 1, right = 2 * MAX, mid;
                 while(left < right)
                 {
                     mid = (left + right) >> 1;
                     if(run(P, pNum, mid) > 0)
                         right = mid;
                     else
                         left = mid + 1;
                 }
                 MozNum += left;
                 P -= pNum;
                 E -= pNum + 1;
                 Flag = 2;
             }
         }
         if(Plant[0] == 'M')
             ++MozNum;
         printf("Case %d: %d\n", t, MozNum);
     }
     return 0;
 }

参考:http://www.cnblogs.com/Kenfly/archive/2011/10/05/2199647.html


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept