解题报告 LOJ133-135 二维树状数组模板

前言

这几题都是二维树状数组的模板,不得不说树状数组真是个好东西,既好写速度又快常数还小。但是二维上的处理讲真搞到了我。也使我对差分和前缀和这两个好用的工具有了更深的理解

所有题目都是基于 n\times m 的零矩阵上进行的操作。

LOJ133 单点修改,区间查询

题目链接:https://loj.ac/problem/133

不难发现,我们需要处理的树状数组变成二维的信息之后,在每次的加和查询的操作时,都只需要多考虑一维就可以了,即循环多加一层,需要注意的是这时候就不能直接将传入的 xy 进行操作了,因为每一层关于 y 的内循环都要从 y 的初始值开始考虑

这里需要注意二维前缀和的技巧:如果需要求 (a,b)(c,d) 间的矩阵的和的话,假设 s_{i,j}(1,1)(i,j) 的前缀和,则答案为

s_{c,d}-s_{a-1,d}-s_{c,b-1}+s_{a-1,b-1}

具体的证明咕咕咕了,哪天有时间再写,其实就相当于把多加了减掉,多减了的加回来而已。

具体见下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];

void add(int x,int y,int d)
{
    for(int xx=x;xx<=n;xx+=lowbit(xx))
        for(int yy=y;yy<=m;yy+=lowbit(yy))
            f[xx][yy]+=d;//和一维的很像,但只是加了一维而已
    return;
}

ll sum(int x,int y)//查询操作也一样
{
    ll ans=0;
    for(;x>0;x-=lowbit(x))
        for(int yy=y;yy>0;yy-=lowbit(yy))
            ans+=f[x][yy];
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t,a,b,c,d,k;
    while(scanf("%d",&t)!=EOF)
    {
        if(t==1)
        {
            scanf("%d %d %d",&a,&b,&k);
            add(a,b,k);
        }
        else
        {
            scanf("%d %d %d %d",&a,&b,&c,&d);
            ll ans=sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

LOJ134 区间修改,单点查询

题目链接:https://loj.ac/problem/134

涉及区间修改的时候就需要用到差分了,二维的差分和一维的差分其实本质上没有任何的区别,具体的操作和二维前缀和的有些相似,也是咕咕咕改天写。

单点查询就只需利用 BIT 求出差分的前缀和就可以了,具体见下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=(1<<12)+5;
int n,m;
ll f[maxn][maxn];

void add(int x,int y,int d)
{
    for(int xx=x;xx<=n;xx+=lowbit(xx))
        for(int yy=y;yy<=m;yy+=lowbit(yy))
            f[xx][yy]+=d;
    return;
}

ll sum(int x,int y)
{
    ll ans=0;
    for(;x>0;x-=lowbit(x))
        for(int yy=y;yy>0;yy-=lowbit(yy))
            ans+=f[x][yy];
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t,a,b,c,d,k;
    while(scanf("%d",&t)!=EOF)
    {
        if(t==2)
        {
            scanf("%d %d",&a,&b);
            printf("%lld\n",sum(a,b));
        }
        else
        {
            scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
            add(a,b,k),add(a,d+1,-k),add(c+1,b,-k),add(c+1,d+1,k);//这里是差分的处理
        }
    }
    return 0;
}

LOJ135 区间修改,区间查询

题目链接:https://loj.ac/problem/135

到这里就比较麻烦了,二维线段树我不会打,怎么办呢?只能考虑用树状数组来同时照顾前缀和和差分了。

不妨令 a_{i,j}=\displaystyle\sum_{x=1}^i\sum_{y=1}^jd_{x,y},即 d 为二维差分数组,而我们又由前缀和的定义知道 s_{k,l}=\displaystyle\sum_{x=1}^k\sum_{y=1}^ja_{i,j},因此类比一维的情况,考虑用含有差分的式子来表示前缀和,数学推导过程如下,由于我很笨,所以有可能存在小瑕疵,而且过程很不简洁:

\begin{aligned}
&\sum_{k=1}^x\sum_{l=1}^ya_{k,l}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^k\sum_{j=1}^l d_{i,j}\
=&\sum_{k=1}^x\sum_{l=1}^y\sum_{i=1}^kd_{i,l}\times(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(x-k+1)(y-l+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy-ky+y-xl+kl-l+x-k+1)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times(xy+x+y+1-l-k+kl-xl-ky)\
=&\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\times[xy+x+y+1-l(1+x)-k(1+y)+kl]\
=&(x+1)(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}-(x+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l-(y+1)\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k+\sum_{k=1}^x\sum_{l=1}^yd_{k,l}kl
\end{aligned}

其中 a_{k,l}=\displaystyle\sum_{i=1}^k\sum_{j=1}^l d_{i,j}

所以需要维护四个 BIT,分别是 \displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}l\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}k\displaystyle\sum_{k=1}^x\sum_{l=1}^yd_{k,l}lk

每次修改的时候四个 BIT 要联动修改,当推出了公式之后,剩下的事情就很简单了,写出代码实现即可,我不会告诉你我抄错了我自己推的式子导致 WA 两次。注意不要漏了要乘的东西就可以了,代码如下:

#include <cstdio>
#define lowbit(x) (x&-x)
typedef long long ll;

const int maxn=2058;
ll f1[maxn][maxn],f2[maxn][maxn],f3[maxn][maxn],f4[maxn][maxn];
int n,m;

void add(ll x,ll y,ll d)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            f1[i][j]+=d,
            f2[i][j]+=x*d,
            f3[i][j]+=y*d,
            f4[i][j]+=x*y*d;
    return;
}

ll sum(ll x,ll y)
{
    ll ans1=0,ans2=0,ans3=0,ans4=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            ans1+=f1[i][j],
            ans2+=f2[i][j],
            ans3+=f3[i][j],
            ans4+=f4[i][j];
    return ans1*(x+1)*(y+1)-ans2*(y+1)-ans3*(x+1)+ans4;
}

int main()
{
    scanf("%d %d",&n,&m);
    ll t,a,b,c,d,x;
    while(scanf("%lld %lld %lld %lld %lld",&t,&a,&b,&c,&d)!=EOF)
    {
        if(t==1)
        {
            scanf("%lld",&x);
            add(a,b,x),add(a,d+1,-x),add(c+1,b,-x),add(c+1,d+1,x);
        }
        else
            printf("%lld\n",sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1));
    }
    return 0;
}

大概就是这么多,先睡了,明天再继续肝。

解题报告 P2324/LOJ2151 [SCOI2005]骑士精神

题目内容

洛谷2324

LOJ2151

大意:在一个 5\times5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士,且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为 1,纵坐标相差为 2 或者横坐标相差为 2,纵坐标相差为 1 的格子)移动到空位上。

给定一个初始的棋盘,怎样才能经过移动变成给定目标棋盘:

解题思路

该题明显是一个裸的搜索,但是暴搜铁定超时,再看到限制15步以内,于是想到打随机化使用来迭代加深。

同时这里还可以使用启发式搜索来进行剪枝,这里的估价函数可设为不在应有位置的骑士个数,然后每次枚举移动步数进行迭代加深即可。

像这种移动棋子的题选择移动空位会更好想一点,然后记得处理读入

代码(这个代码不知道为什么洛谷上没输出 LOJ 就 AC 了:

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int tar[5][5]={//目标状态,1表示黑子,0表示白子,2表示空位
    {1,1,1,1,1},
    {0,1,1,1,1},
    {0,0,2,1,1},
    {0,0,0,0,1},
    {0,0,0,0,0}
};
int board[5][5],idt;
const int fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1};//移动的数组

int h()//估价函数
{
    int res=0;//统计多少枚棋子不在目标位置上
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            if(board[i][j]!=tar[i][j]) res++;
    return res;
}

bool dfs(int x,int y,int d)//x,y为空位坐标,d为当前枚举的深度
{
    if(d+h()>idt+1) return false;//如果估价函数显示这个限制深度铁定过不了就剪枝
    if(!h()) return true;//如果已经到达目标状态,直接返回true
    for(int k=0;k<8;k++)//枚举各个方向
    {
        int x1=x+fx[k],y1=y+fy[k];
        if(x1>4||x1<0||y1>4||y1<0) continue;//判定越界
        swap(board[x][y],board[x1][y1]);//否则交换棋子和空位的位置
        if(dfs(x1,y1,d+1)) return true;//继续dfs,如果搜到了目标状态,返回
        swap(board[x][y],board[x1][y1]);//回溯
    }
    return false;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)//毒瘤题目有很多组数据
    {
        int x0,y0;
        for(int i=0;i<5;i++)
        {
            char s[5];
            scanf("%s",s);
            for(int j=0;j<5;j++)
            {
                if(isdigit(s[j])) board[i][j]=s[j]-'0';
                if(s[j]=='*')
                {
                    board[i][j]=2;
                    x0=i;
                    y0=j;
                }
            }
        }
        bool flag=0;
        for(idt=1;idt<=15;idt++)//枚举深度
        {
            if(dfs(x0,y0,0)){flag=1;break;}//如果当前限制搜到了,那么停止
        }
        printf("%d\n",flag?idt:-1);
    }
    return 0;
}