首页 > ACM题库 > HDU-杭电 > hdu 2678 TimeLimit-树状数组-[解题报告]C++
2014
02-12

hdu 2678 TimeLimit-树状数组-[解题报告]C++

TimeLimit

问题描述 :

Magina is surround by hundreds of monsters. Can he survive in T unit times?
Now matter Magina or monster have three attributes(ATI, DEF, HP), but Magina have another attributes (MaxHP). Magina can own some equipments as a hero , there are six kinds of equipment ("Head", "Weapon", "Armor","Shoes", "Trump","Cuff") in this world. Equipment have three attributes (A, D, MH), each standing the value can increase to ATI, DEF and MaxHP of Magina.
To every some kinds of equipment, Magina can only choose one to use. So when he have some kinds of equipments, he will choose the one have the bigger value. The value of equipments define as A*3 + D*2 + MH. If the value of equipments is equal to the one Magina have, he will not choose to change his equipment.




Now describe a fighting between A and B.
We know A hurt B first, the value of harm define as P.
P = MAX(1,(int)((A’s ATI – B’s DEF) / ( abs(Xa-Xb) + abs(Ya-Yb) + 1))). (Xa,Ya) and (Xb,Yb) is the position of A and B. So B’s HP will reduce P.
Than B hurt A. A will loss MAX(1,(int)((B’s ATI – A’s DEF) / ( abs(Xa-Xb) + abs(Ya-Yb) + 1))).
Every one will die if his HP is small or equal to 0.

In the 2d-world. Magina standing in the position (0,0) and never moving, in T unit time, n monsters will move nearly to attack he. To every unit time we divide it to four processes.
First Magina choose K monsters to attack once each continuously .(He will attack all if there are no K monsters survived ) If a monster die by attacking, he will drop a equipment. Than Magina can choose weather to use it. The way Magina choose is according to the P which is the value of his hurting to the monster. The first K higher monsters will be selected at the every unit time’s begining, if two monsters have some P, the smaller ID of monsters will be selected.
Second every monster survived will hurt Magina once continuously. If Magina die, game over.

Third every monster survived will move to Magina one unit. If the monster is standing the place of Magina, he will not move. One unit is meaning X or Y to change only one.

Fourth Magina will revert W HP. W = (int) ( MaxHP*0.05 ). The maximum of HP can not bigger than MaxHP.

输入:

The input contains multiple test cases.
First line give the integer n (1<= n <=400)
Next line ATI, DEF, MaxHP,K,T. (T<=100). Magina is HP = MaxHP and have no equipment at the begin.
Next follow n line, each line expressing a monster by increasint ID.The input form as ATI, DEF,HP,X,Y, Kind’smane, A, D, MH. All integer are nonnegative.Last four expressing the equipment this monster owned.Kind’smane is the kind name of equipment.It can only be one of six describing foregoing

输出:

The input contains multiple test cases.
First line give the integer n (1<= n <=400)
Next line ATI, DEF, MaxHP,K,T. (T<=100). Magina is HP = MaxHP and have no equipment at the begin.
Next follow n line, each line expressing a monster by increasint ID.The input form as ATI, DEF,HP,X,Y, Kind’smane, A, D, MH. All integer are nonnegative.Last four expressing the equipment this monster owned.Kind’smane is the kind name of equipment.It can only be one of six describing foregoing

样例输入:

1
30 2 100 1 3
3 0 10 2 2 Head 1 0 0

5
192 114 29 3 64
22 3 140 15 5 Head 32 18 4
45 15 114 4 11 Trump 34 47 48
44 9 186 19 2 Cuff 28 46 12
32 3 2 10 18 Armor 45 40 15
27 3 104 1 3 Trump 37 2 22

5
30 130 33 2 85
34 4 163 13 15 Head 32 9 15
11 3 8 3 12 Cuff 7 22 4
11 14 143 3 18 Weapon 48 17 35
5 14 27 10 1 Cuff 9 25 41
34 17 135 13 1 Weapon 48 0 33

样例输出:

Magina get the Head
Magina killed 1 Monster!

Magina get the Trump
Magina update the Trump
Magina get the Armor
Magina get the Head
Magina get the Cuff
Magina killed 5 Monster!

Magina get the Cuff
Magina death !


#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1001;
struct point
{
    int x,y,z;
} p[15001];
int c[maxn][maxn];
int s[15001];
int cmp(point a,point b)
{
    if(a.z!=b.z) return a.z<b.z;
    else if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
inline int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int y,int p)
{
    for(int i=x; i<maxn; i+=lowbit(i))
        for(int j=y; j<maxn; j+=lowbit(j))
            c[i][j]+=p;
}
int sum(int x,int y)
{
    int ans=0;
    for(int i=x; i>0; i-=lowbit(i))
        for(int j=y; j>0; j-=lowbit(j))
            ans+=c[i][j];
    return ans;
}
int main()
{
    int n,x,y,z;
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<=n;i++) s[i]=0;        
        memset(c,0,sizeof(c));
        for(int i=0; i<n; i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            p[i].x=x,p[i].y=y,p[i].z=z;
        }
        sort(p,p+n,cmp);
        for(int i=0; i<n; i++)
        {
            s[sum(p[i].x+1,p[i].y+1)]++;
            update(p[i].x+1,p[i].y+1,1);
        }
        for(int i=0; i<n-1; i++)
            printf("%d ",s[i]);
        printf("%d\n",s[n-1]);
    }
    return 0;
}

解题转自:http://blog.csdn.net/ehi11/article/details/8581382


  1. 有时候格斗你看着很慢,实际体验会觉得很快;就像你看方程式赛车过弯的时候觉得好慢啊一点不精彩,但坐在车上估计要吓尿