HDU 4331 Image Recognition

HDU 4331 Image Recognition

本题题目大意在一个01方阵中找出四条边全都是1的正方形的个数,对于正方形内部则没有要求。

一个直观的想法是首先用N^2的时间预处理出每一个是1的点向上下左右四个方向能够延伸的1的最大长度,记为四个数组l, r, u, d。然后我们观察到正方形有一个特征是同一对角线上的两个顶点在原方阵的同一条对角线上。于是我们可以想到枚举原来方阵的每条对角线,然后我们对于每条对角线枚举对角线上所有是1的点i,那么我们可以发现可能和i构成正方形的点应该在该对角线的 [i, i + min(r[i], d[i]) – 1] 闭区间内, 而在这个区间内的点 j 只要满足 j – i + 1 <= min(l[j], u[j]) 也就是满足j – min(l[j], u[j]) + 1 <= i,这样的 (i, j) 就能构成一个正方形。也就是说对于每条对角线,我们可以构造一个数组 a, 使得a[i] = i – min(l[i], u[i]) + 1

然后对这个数组有若干次查询,每次查询的是区间 [i, i + min(r[i], d[i]) – 1]内有多少个数满足 a[j] <= i,所有这些问题答案的和就是该问题的结果。对于这个问题,我们可以通过离线算法,先保存所有查询的区间端点,并对所有端点排序。然后使用扫描线算法,如果扫描到的是第i次查询的左端点,就让当前结果减去当前扫描过的数中 <= i的个数,如果扫描到的是第i次查询的有短点,则让当前结果加上当前扫描过的数中 <= i的个数,最后所有结果相加即可。

维护当前数出现的个数可以使用树状数组。这样对于每条对角线求结果的复杂度为O(nlogn),算法总的复杂度为O(n^2logn)。

HDU 4331 Image Recognition
HDU 4331 Image Recognition
View Code

View Code 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<cstring>
#include<vector>
#include<string>
#define LL long long
using namespace std;
int map[1024][1024],l[1024][1024],u[1024][1024],d[1024][1024],r[1024][1024],a[2024],c[2024];
class Node{
public:
      bool left;
      int x,id;    
}p[2024];
bool cmp( Node a, Node b ){
    if( a.x == b.x ) return a.left;
    return a.x < b.x;    
}
int lowbit( int x ){
    return x&(-x);    
}
void Updata( int x, int n ){
    for( int i = x ; i <= n ; i += lowbit(i) )
          c[i] ++;    
}
int Query( int x ){
    int ans = 0;
    for( int i = x; i > 0 ; i -= lowbit(i) )
         ans += c[i];
    return ans;    
}
int res( int n, int m ){
    int ans = 0;
    memset( c , 0 , sizeof( c ) );
    sort( p , p + m , cmp );
    for( int i = 0 ; i < m ; i ++ )
         if( p[i].left ) {
                ans -= Query( p[i].id );
                Updata( a[p[i].x] ,n );
         }
         else ans +=Query( p[i].id );
//    printf( "__%d\n",ans );
    return ans;
}
int Solve( int n )
{
    int ans=0;
    for( int i =1 ; i <= n ; i ++ ){
        int m = 0;
        for( int j = 1 ; j <= i ; j ++ ){
                int x=n-i+j,y=j;         
                if( map[x][y] == 1 ){
                    a[y] = y - min( l[x][y],u[x][y] ) + 1;
                    p[m].left = true;p[m].id=y;p[m].x=y,p[m].id=y;
                    m++;
                    p[m].left=false;p[m].x=y+min( r[x][y],d[x][y] )-1;p[m].id=y;
                    m++;
                    }        
            }   
        ans += res( n ,m ); 
//        printf( "ans=%d\n",ans );   
      }    
      for( int i =2 ; i <= n ; i ++ ){
        int m = 0;
        for( int j = 1 ; j <= n - i + 1 ; j ++ ){
                  int x=j,y=i+j-1;             
                if( map[x][y] == 1 ){
                    a[y] = y - min( l[x][y],u[x][y] ) + 1;
                    p[m].left = true;p[m].id=y;p[m].x=y;
                    m++;
                    p[m].left=false;p[m].x=y+min( r[x][y],d[x][y] )-1;p[m].id=y;
                    m++;
                    }        
            }  
        ans += res( n ,m );   
//        printf( "ans=%d\n",ans ); 
      }    
      return ans;
}
int main(  ){
    int T,n;
    while( scanf( "%d",&T )==1 ){
        for( int cas = 1 ; cas <= T ;cas++ ){
            memset( u , 0 , sizeof( u ) );
            memset( d , 0 , sizeof( d ) );
            memset( l , 0 , sizeof( l ) );
            memset( r , 0 , sizeof( r ) );
             scanf( "%d",&n );
             LL cnt = 0,ans=0;
             for( int i = 1 ; i <= n ; i ++ )
                  for( int j = 1; j <= n ; j ++ ){
                       scanf( "%d",&map[i][j] ); 
                       if( map[i][j] == 0 ) u[i][j] = l[i][j] = 0;
                      else{
                        u[i][j] = u[i-1][j]  + 1;
                        l[i][j] = l[i][j-1] + 1;
                     }
                  }
            for( int i = n ; i >0  ; i -- ){
                 for( int j = n ;j > 0 ; j -- ){
                        if( map[i][j] == 0 ) d[i][j] = r[i][j] = 0;
                        else{
                        d[i][j] = d[i+1][j] + 1;
                        r[i][j] = r[i][j+1] + 1;
                       }
                     }
                }
            printf( "Case %d: %d\n",cas,Solve( n ) );
       }
   }
    //system( "pause" );
    return 0;
}

 

 

转载于:https://www.cnblogs.com/bo-tao/archive/2012/08/03/2622211.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110357.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • C++和Java有哪些区别

    C++和Java有哪些区别1.C++创建对象后需要在使用结束后调用delete方法将其销毁,Java有垃圾回收机制,用来监视new出来的所有对象,辨别不会再被引用的对象,然后释放内存空间2.C++可以重载操作符,Java不能重载3.当变量作为类的成员使用时,Java才确保给定默认值,以确保那些基本类型的成员变量得到初始化,但是C++没有此功能4.C++有多继承,Java只有单继承5.Java中没有sizeof(),在C++中sizeof()操作符能够告诉我们为数据项分配的字节数,因为C++中不同的数据类型在不同的机器上可能有

  • jps查看java进程(gps弱怎么办)

    JPS(JavaVirtualMachineProcessStatusTool)是JDK1.5提供的一个显示当前所有java进程pid的命令,简单实用,非常适合在linux/unix平台上简单察看当前java进程的一些简单情况。我想很多人都是用过unix系统里的ps命令,这个命令主要是用来显示当前系统的进程情况,有哪些进程,及其id。jps也是一样,它的作用是显示当前系统的j

  • Java课设–学生成绩管理系统一

    Java课设–学生成绩管理系统一写在前面这个项目是Java课程的课设,一共花了5天的时间去完成它,在这期间感谢一些博主的帮助,让我了解到了一些新的技术知识,所以打算写这一系列博客来介绍一整个课设项目,也为了帮助之后的人,如有错误,请联系我。为了更好的让读者了解到整个项目的设计流程,我将项目拆分成几个部分来就行解说,这一小节是一个总述,主要介绍课设的整个框架和最终效果,代码我会放到后面的github链接上,欢迎大家star。如果有一些参考没有加上联系,希望大家可以联系我,因为写的时候查的比较快,没有记录到博主的链接,敬请谅解!!!一、

  • 3极管npn和pnp_npn开关电路工作原理

    3极管npn和pnp_npn开关电路工作原理===================================================================三极管,全称应为半导体三极管,也称双极型晶体管、晶体三极管,是一种电流控制电流的半导体器件·其作用是把微弱信号放大成幅度值较大的电信号,也用作无触点开关。晶体三极管,是半导体基本元器件之一,具有电流放大作用,是电子电路的核心元件。三极管是在一块半导体基片上制作…

  • stm32串口工作原理_rs232串口通信原理

    stm32串口工作原理_rs232串口通信原理STM32F1xx官方资料:《STM32中文参考手册V10》-第25章通用同步异步收发器(USART)通信接口背景知识设备之间通信的方式一般情况下,设备之间的通信方式可以分成并行通信和串行通信两种。它们的区别是:并、串行通信的区别 并行通信 串行通信 传输原理 数据各个位同时传输 数据按位顺序传输 优点 速度快 占用引脚资…

  • 动画插件–AnimateCSS

    动画插件–AnimateCSS1.什么是Animate.css?其实swiper-animate就是参考Animate.css演变出来的一个插件, Animate.css和swiper-animate一样都是用于快速添加动画的, 所以会用swiper-animate就会用Animate.css2.Animate.css的使用:引入animate.css的文件 给需要执行动画的元素添加类名3.示例animated这个类名是animated.css的基类,但凡需要通过animated.css来添加动画,都需

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号