专栏文章

题解：P1001 A+B Problem

AAurelia_Veil
P1001题解参与者 12已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@mipczfov
此快照首次捕获于
2025/12/03 09:59
3 个月前
此快照最后确认于
2025/12/03 09:59
3 个月前
查看原文

题解：P1001 A+B Problem

正文：

我们一眼可以看出，这是要我们求出一个大小为 114×514114 \times 514 的矩阵的和，于是可以使用二维树状数组快速求出答案。 记住这是一个模板题！

我们来讲解一些二维树状数组的写法：

1. 创建树状数组：

直接创建一个大小为 114×514114 \times 514 的二维树状数组，但是最大我设为的 212×2122^{12} \times 2^{12} 的大小。
重要代码：
CPP
const int N=1<<12;
long long tree[N][N][7];

2. 填充二维线段树：

我们在输入时填充二维线段树，但是因为这是构造题，所以可以随机输出咩。
重要代码：
CPP
for(int i=3;i<=n;i++){//从 3 开始咩
    for(int j=3;j<=m;j++){
        add(i,j,rand());
    }
}
CPP
void add(int x,int y,long long z){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            tree[i][j][1]+=z;
            tree[i][j][2]+=z*x;
            tree[i][j][3]+=z*y;
            tree[i][j][4]+=z*x*y;
        }
    }
}

3. 如何区间求和：

我们需要使用位运算求出这个数的所有子集，使用 sumsum 变量统计最终结果。
重要代码：
CPP
long long sum(int x,int y){
    long long sum=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            sum+=(x+1)*(y+1)*tree[i][j][1]-(y+1)*tree[i][j][2]-(x+1)*tree[i][j][3]+tree[i][j][4];
        }
    }
    return sum;
}

4. 输入格式：

为了保证输入格式符合题目，我们要修改输入代码。
重要代码：
CPP
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    n=114;
    m=514;
    n++;
    m++;
    for(int i=3;i<=n;i++){
        for(int j=3;j<=m;j++){
            add(i,j,rand());
        }
    }
    int k,t=3;
    while(t){
        if(t==3){
            k=1;
        }else if(t==2){
            k=1;
        }else{
            k=2;
        }
        if(k==1){
            int ax,ay,bx,by,z;
            if(t==3){
                ax=1;
                ay=1;
                bx=1;
                by=1;
                z=a;
            }else{
                ax=2;
                ay=1;
                bx=2;
                by=1;
                z=b;
            }
            ax++;
            ay++;
            bx++;
            by++;
            add(bx,by,z);
            add(bx,ay-1,-z);
            add(ax-1,by,-z);
            add(ax-1,ay-1,z);
        }else{
            int ax=1e9/1e9,ay=2e7/2e7-2+2,bx=1*2+0,by=-1+2;
            printf("%lld\n",sum(bx,by)-sum(bx,ay-1)-sum(ax-1,by)+sum(ax-1,ay-1));
        }
        t--;
    }
    return 0;
}

最终代码

代码如下咩：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1<<12;
long long tree[N][N][7];
int n,m;
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y,long long z){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            tree[i][j][1]+=z;
            tree[i][j][2]+=z*x;
            tree[i][j][3]+=z*y;
            tree[i][j][4]+=z*x*y;
        }
    }
}
long long sum(int x,int y){
    long long sum=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            sum+=(x+1)*(y+1)*tree[i][j][1]-(y+1)*tree[i][j][2]-(x+1)*tree[i][j][3]+tree[i][j][4];
        }
    }
    return sum;
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    n=114;
    m=514;
    n++;
    m++;
    int k,t=3;
    while(t){
        if(t==3){
            k=1;
        }else if(t==2){
            k=1;
        }else{
            k=2;
        }
        if(k==1){
            int ax,ay,bx,by,z;
            if(t==3){
                ax=1;
                ay=1;
                bx=1;
                by=1;
                z=a;
            }else{
                ax=2;
                ay=1;
                bx=2;
                by=1;
                z=b;
            }
            ax++;
            ay++;
            bx++;
            by++;
            add(bx,by,z);
            add(bx,ay-1,-z);
            add(ax-1,by,-z);
            add(ax-1,ay-1,z);
        }else{
            int ax=1e9/1e9,ay=2e7/2e7-2+2,bx=1*2+0,by=-1+2;
            printf("%lld\n",sum(bx,by)-sum(bx,ay-1)-sum(ax-1,by)+sum(ax-1,ay-1));
        }
        t--;
    }
    return 0;
}

正解的语法讲解：

1.

CPP
#include<iostream>
这个指头文件，是一条预处理指令，其中包含一下组件：
  • std::istream 类：指输入流。
  • std::ostream 类：指输出流
  • std::cin 对象：这是 std::istream 类中的其中一个对象，表示标准输入流，通常为键盘输入。
  • std::cout 对象：这是 std::ostream 类中的其中一个对象，表示标准输出流，通常为屏幕输出。

2.

CPP
using namespace std;
这个为标准命名空间，这段代码是要将 std 作为标准命名，std 为 C++ 标准库的命名空间。

3.

CPP
int main(){

    return 0;
}
这个是主函数，表示程序刚开始要运行的函数。
所以代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;//定义两个变量 a 和 b 
    cin>>a>>b;//输入并赋值 a 和 b 
    cout<<a+b;//输出 a + b 的和 
    return 0;
}

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...