专栏首页owentPOJ PKU 2155 Matrix 解题报告

POJ PKU 2155 Matrix 解题报告

这道题是我专门为了了解和学习树状数组而写的

这题用树状数组记录翻转次数,然后mod一个2,也可以不断地取反

还要用到二维的树状数组.于是我专门写了个模板用

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

题意大致是输入语句,Q表示要求输出A(x,y)是1还是0.C表示把(x1,y1)->(x2,y2)间的矩形中所有元素的1变成0,0变成1

开始我试过一维树状数组+线性.结果TLE.无奈写了个二维的400+ms

贴代码:

#include<iostream>
using namespace std;


//树状数组模块
//基于0,Based 0
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av);
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n);

DG_Ran teg[DG_MAXN][DG_MAXN];
int main()
{
    int x;
    long n,t,x1,y1,x2,y2,i,j;
    char cmd;
    scanf("%d",&x);
    while(x --)
    {
        scanf("%ld %ld",&n,&t);
        for(i = 0 ; i < n ; i ++)
            for(j = 0 ; j < n ; j ++)
                teg[i][j] = 0;
        while(t --)
        {
            getchar();
            scanf("%c",&cmd);
            if(cmd == 'Q')
            {
                scanf("%ld %ld",&x1,&y1);
                printf("%ld\n",DGCUp2(teg,x1 - 1,y1 - 1,n) % 2);
            }
            else
            {
                scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
                DGDown2(teg,x2 - 1,y2 - 1,1);
                DGDown2(teg,x1 - 2,y2 - 1,-1);
                DGDown2(teg,x2 - 1,y1 - 2,-1);
                DGDown2(teg,x1 - 2,y1 - 2,1);
            }
        }
        if(x)
            putchar('\n');
    }
    return 0;
}

//树状数组的翻转
//二维  复杂度(log(n))^2
//小于等于指定位置的元素操作(0,0)->(x,y)
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av)
{
    while(x >= 0)
    {
        DG_Num tmp = y;
        while (tmp >= 0)
        {
            g[x][tmp] += av;
            tmp = DGBrother(tmp);
        }
        x = DGBrother(x);
    }
}
//获取大于等于pos位置的元素翻转次数的和
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n)
{
    DG_Ran t = 0;
    while(x < n)
    {
        DG_Num tmp = y;
        while (tmp < n)
        {
            t += g[x][tmp];
            tmp = DGFather(tmp);
        }
        x = DGFather(x);
    }
    return t;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树状数组模块(个人模板)

    owent
  • atsf4g-co的进化:协程框架v2、对象路由系统和一些其他细节优化

    年前就计划把以前项目的一些理念和设计方案融合到sample里来。但是内容比较多,一直也没太多时间去完成它。所幸虽然断断续续但终归是完成了。并且在之前的一些实现上...

    owent
  • JQuery扩展插件--提示信息

    https://github.com/owt5008137/SimpleMetro

    owent
  • 树状数组模块(个人模板)

    owent
  • WebService是什么?他究竟和WebSocket有什么关系?

    其以 HTTP 协议为基础,通过 XML 进行客户端和服务器端通信的框架 / 组件。

    良月柒
  • python实现从ftp上下载文件的实例方法

    到此这篇关于python实现从ftp上下载文件的实例方法的文章就介绍到这了,更多相关python怎么实现从ftp上下载文件内容请搜索ZaLou.Cn以前的文章或...

    砸漏
  • 聊聊canal-go的SimpleCanalConnector

    canal-go-v1.0.7/client/simple_canal_connector.go

    codecraft
  • 聊聊canal-go的SimpleCanalConnector

    canal-go-v1.0.7/client/simple_canal_connector.go

    codecraft
  • IT盛世下的蝼蚁:每一位开发者都足以改变世界

    毕业已经2年了,从最开始进入互联网公司成为一名开发人员到现在,遇到了各种类型的问题,也处理了很多问题,但总感觉冥冥之中有股黑暗的力量制约着我,直到8月31日我遇...

    Rainbond开源
  • HTML被恶意注入JS弹广告

    继续查看http://45.126.123.80:118/t.php 一堆代码,获取各种信息。。。

    Light413

扫码关注云+社区

领取腾讯云代金券