首页 > 编程语言 > 详细

洛谷 P2038 无线网络发射器选址 —— 二维树状数组

时间:2018-09-13 19:19:23      阅读:161      评论:0      收藏:0      [点我收藏+]

题目:https://www.luogu.org/problemnew/show/P2038

大水题暴露出我的愚蠢。

用二维树状数组,然而居然忘了它应该那样写,调了一个小时;

正方形可以超出外面,只要中心在里面即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=200;
int d,n,t[maxn][maxn],ans,num,mx,my;
void add(int x,int y,int v)
{
  // for(;x<=mx;x+=(x&-x))
  //for(;y<=my;y+=(y&-y))
  for(int i=x;i<=mx+d;i+=(i&-i))
    for(int j=y;j<=my+d;j+=(j&-j))
      t[i][j]+=v;
}
int query(int x,int y)
{
  int ret=0;
  //  for(;x;x-=(x&-x))
  //    for(;y;y-=(y&-y))
  for(int i=x;i;i-=(i&-i))
    for(int j=y;j;j-=(j&-j))
      ret+=t[i][j];
  return ret;
}
int main()
{
  scanf("%d%d",&d,&n); mx=129; my=129;
  for(int i=1,x,y,k;i<=n;i++)
    {
      scanf("%d%d%d",&x,&y,&k); x++; y++;
      add(x,y,k);
    }
  for(int i=d+1;i<=mx+d;i++)
    for(int j=d+1;j<=my+d;j++)
      {
    int x=max(0,i-2*d-1),y=max(0,j-2*d-1);
    int v=query(i,j)-query(x,j)-query(i,y)+query(x,y);
    if(v>ans)ans=v,num=1;//!
    else if(v==ans)num++;
      }
  printf("%d %d\n",num,ans);
  return 0;
}

 

洛谷 P2038 无线网络发射器选址 —— 二维树状数组

原文:https://www.cnblogs.com/Zinn/p/9642290.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!