首页 > ACM题库 > HDU-杭电 > hdu 2155 小黑的镇魂曲-树状数组-[解题报告]C++
2013
12-30

hdu 2155 小黑的镇魂曲-树状数组-[解题报告]C++

小黑的镇魂曲

问题描述 :

这个事情发生在某一天,当小黑和SSJ正在约会的时候,邪恶的Guner抓走了SSJ,小黑伤心万分,怒不可遏啊!但是他显然也是没有办法的,谁叫Guner比小黑邪恶,小黑打不过Guner呢!
于是,小黑利用皮肤保护色,趁夜摸黑前往Guner的城堡,准备偷偷摸摸的把SSJ拯救出来,但是只要小黑一打开SSJ身上的锁链,看门的葱头就会在M秒以内通知Guner,Guner马上超时空转移,闪到小黑身边抓住他们,于是小黑虽然跑得不快,但是他也不得不跑啊。
由于Guner的城堡构造特殊,它是由一个一个的平台搭建成的,所以小黑的逃跑路线是这样的,在时刻0的时候,他位于最高点,也就是高于所有的平台,然后他开始垂直下落,他的下落速度是1米/秒。当小黑下落到某个平台上时,他可以向左跑也可以向右跑,他的跑动速度还是1米/秒。当小黑又处于平台边缘的时候,他开始继续下落。但是小黑是个怜香惜玉的人,为了顾及怀中的SSJ,于是他每次下落的最大高度不会超过MAX米,不然SSJ摔坏了,Guner也懒得追了,小黑也会伤心致死的。但是只要小黑抱着SSJ一落到地面,Guner就再也抓不住他们了。

输入:

第一行输入一个数T(0 < T <= 10),表示测试数据的组数。每组测试数据的第一行是5个整数,N,X,Y,MAX,M,用空格分开。N(0 < N <= 1000)是台阶的数目,X,Y分别是小黑0时刻所在位置的横、纵坐标,MAX表示小黑最多能下落的高度,M表示从小黑一打开锁链葱头发觉后报告给Guner的时间,接下来有N行数据,每行数据描述一个台阶,包括3个数据,Xl[i],Xr[i],H[i],其中Xl[i](0 < Xl[i] <= 1000)表示当前台阶最左边的边的X坐标,Xr[i](0 < Xr[i] <= 1000)表示当前台阶最右边的边的X坐标,H[i](0 < H[i] < 1000)表示当前台阶离地面的高度。数据确保小黑和SSJ是能到达地面的。

输出:

第一行输入一个数T(0 < T <= 10),表示测试数据的组数。每组测试数据的第一行是5个整数,N,X,Y,MAX,M,用空格分开。N(0 < N <= 1000)是台阶的数目,X,Y分别是小黑0时刻所在位置的横、纵坐标,MAX表示小黑最多能下落的高度,M表示从小黑一打开锁链葱头发觉后报告给Guner的时间,接下来有N行数据,每行数据描述一个台阶,包括3个数据,Xl[i],Xr[i],H[i],其中Xl[i](0 < Xl[i] <= 1000)表示当前台阶最左边的边的X坐标,Xr[i](0 < Xr[i] <= 1000)表示当前台阶最右边的边的X坐标,H[i](0 < H[i] < 1000)表示当前台阶离地面的高度。数据确保小黑和SSJ是能到达地面的。

样例输入:

1
1 10 17 20 20
1 8 7

样例输出:

NO

/**
[树状数组]hdu 2155 Matrix
二维树状数组,更新区间,查询点
详解见09年国家集训队论文 
http://www.cppblog.com/klion/archive/2010/05/25/116325.html?opt=admin
*/
#include <stdio.h>
#include <string.h>

#define N 1001
#define lowbit(i) (i) & (-i)
int mat[N][N],n;
void update(int x,int y)
{
    int i,j;
    for(i = x; i <= n; i += lowbit(i))
        for(j = y; j <= n; j += lowbit(j))
            mat[i][j] ^= 1;
}
int sum(int x,int y)
{
    int ans = 0,i,j;
    for(i = x; i > 0; i -= lowbit(i))
        for(j = y; j > 0; j -= lowbit(j))
            ans += mat[i][j];
    return ans;
}
int main()
{
    int t,q,x1,y1,x2,y2,res;
    char ask[4];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        memset(mat,0,sizeof(mat));
        while(q--)
        {
            scanf("%s%d%d",ask,&x1,&y1);
            if(ask[0] == 'Q')
            {
                res = sum(x1,y1);
                printf("%d\n",res&1);
                continue;
            }
            scanf("%d%d",&x2,&y2);
            ++x2;
            ++y2;
            update(x1,y1);
            update(x2,y1);
            update(x1,y2);
            update(x2,y2);
        }
        printf("\n");
    }
    return 0;
}

解题转自:http://blog.csdn.net/cscj2010/article/details/7853556


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.