注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[nbut] 1203 Chihuo IV - Evidence  

2012-11-08 21:09:52|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  这题是上面一题挖洞的升级版——填洞。思路差不多,但是这题是上一题的逆思路,从前往后填洞相当于从后往前挖洞。

这题的算法是:并查集+离线+DP;

还有这题的数据大小得定义到__int64.

贴上链接:

http://acm.nbut.cn:8081/Problem/view.xhtml?id=1203

 

代码:

 

 

 

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

 

#define Max 600
bool map[Max][Max];
__int64 sum[Max * Max];
int father[Max * Max];
__int64 rank[Max * Max];
int np[Max * Max][2];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
__int64 Maxn;

 

int Find(int x)
{
    if(father[x] == x)   return x;
    else
 {
  father[x] = Find(father[x]);
  return father[x];
 }
}

 

void Union( int x, int y)
{
  int xx = Find(x);
  int yy = Find(y);
  if(xx != yy)
  {
   rank[xx] += rank[yy];
   father[yy] = xx;
   if(rank[xx] > Maxn)
    Maxn = rank[xx];
  }
}

 

void Chu(int n)
{
  for(int i = 0;i < n * n;i++)
  {
     father[i] = i;
     rank[i] = 1;
   }
}

 

int main()
{
   int n,m;
//   freopen("data.in","r",stdin);
 //  freopen("data1.out","w",stdout);
   while(~scanf("%d",&n))
   {
      Maxn = 1;
     Chu(n);
      memset(map,0,sizeof(map));
      memset(np,0,sizeof(np));
      for(int i = n * n - 1;i >=  0;i --)
      {
       scanf("%d%d",&np[i][0],&np[i][1]);
      }
      for(int j = 0;j < n * n;j ++)
      {
        int x = np[j][0] - 1,y = np[j][1] - 1;
         map[x][y] = 1;
            for(int i = 0;i < 4;i ++)
            {
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];
                if(xx >= n || yy >= n || xx < 0 || yy < 0) continue;
                if(map[xx][yy] == 1)
                   Union(x * n + y,xx * n + yy);
            }
          
    sum[n * n - 1] = 0;
            sum[n * n - j - 2] =  Maxn;
 
      }
   for(int i = 0;i < n * n;i ++)
   {
    sum[i + 1] += sum[i];
   }
      int q; scanf("%d",&q);
      while(q -- )
      {
       int a,b;
       scanf("%d%d",&a,&b);
       a--;b--;
       if(a == 0)
        printf("%I64d\n",(__int64)sum[b]);
   if(a > 0)
   {
    printf("%I64d\n",(sum[b] - sum[a - 1]));
   
   }
    
      }
  }
}

 


/*
样例输入
3
1 1
1 3
2 2
2 3
3 2
1 2
3 3
2 1
3 1
1
1 1
样例输出
8*/

 


  评论这张
 
阅读(102)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018