Loading...

洛谷P2038 无线网络发射器选址

check评论:0 条 remove_red_eye浏览量:470 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-18

题目很简单,重要的是得到答案的过程

这道题可以采用很多种方法来快速算出一个矩阵的和,可以采用二维前缀和,递推公式即
$$f(x,y)=f(x-1,y)+a[x][y]\ \ \ y=1\ or\ y=m$$
$$f(x,y)=f(x,y-1)+a[x][y]\ \ \ x=1\ or\ x=n$$
$$f(x,y)=f(x-1,y)+f(x,y-1)-f(x-1,y-1)+a[x][y]\ \ \ x,y\neq 1\ and\ x\neq n\ and\ y\neq m$$

然乎求矩阵$(x1,y1,x2,y2)$的和差分一下即可,时间复杂度为$O(n^2)$

而如果不用前缀和呢?我们如何快速的求出矩阵的和?

二维树状数组

时间复杂度略慢于前缀和,为$O(n^2\ log^2n)$

我们来观察一下二维树状数组基本操作代码:

添加:

#define lowbit(x) (x&(-x))
void add(int x,int y,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=m;j+=lowbit(j))
        {
            c[i][j]+=k;
        }
    }
}

显然的,就是一维树状数组再纵向添加了一次,查询也类似

代码:

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
int c[130][130];
int ans=0,maxn=-0x3f3f3f3f;
void add(int x,int y,int k)
{
    for(int i=x;i<=129;i+=lowbit(i))
    {
        for(int j=y;j<=129;j+=lowbit(j))
        {
            c[i][j]+=k;
        }
    }
}
int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        for(int j=y;j>=1;j-=lowbit(j))
        {
            ans+=c[i][j];
        }
    }
    return ans;
}
int main()
{
    int d,n;
    cin>>d>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        add(x+1,y+1,k);
    }
    for(int i=1;i<=129;i++)
    {
        for(int j=1;j<=129;j++)
        {
            int i1=i-d;
            if(i1<=0)
            {
                i1=1;
            }
            int i2=(i+d);
            if(i2>=130)
            {
                i2=129;
            } 
            int j1=(j-d);
            if(j1<=0)
            {
                j1=1;
            }
            int j2=(j+d);
            if(j2>=130)
            {
                j2=129;
            } 
            int ans1=query(i2,j2)-query(i2,j1-1)-query(i1-1,j2)+query(i1-1,j1-1);
            if(ans1>maxn)
            {
                ans=1;
                maxn=ans1;
            }
            else if(ans1==maxn)
            {
                ans++;
            }
        }
    }
    cout<<ans<<" "<<maxn;
}

倍增

既然没有修改,我们为何不采用倍增的方法来求出矩阵的值?

倍增通过每次向一个点往后跳$2^j$的方式快速获得区间答案,因为其查询复杂度为$O(1)$并且将所求矩阵二进制分解需要$O(log^2n)$,故时间复杂度与二维树状数组类似,为$O(n^2\ log^2n)$

$a[i][j][k][p]$代表矩阵$(i,j)-(i+2^k,j)-(i,j+2^p)-(i+2^k,j+2^p)$的值,预处理时间复杂度也为$O(n^2)$,可以快速完成本题,这里就不发代码了。

后记:这道题虽然简单,但希望各位可以从简单的题目中探寻多种解决问题的方法,博主只是发掘了其冰山一角,只有平时更多的积累,才能在考场上胸有成竹。

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名