杂题——Money Trees

参考了文章

前言

首先来先介绍一下三维前缀和和三维差分的做法**(即使学过也可以看看最下面的做法,有彩蛋做法)**

三维前缀和

首先就是经典的就是下面这个公式
$$
S(X, Y, Z) = a(X, Y, Z)+S(X, Y, Z - 1) + S(X, Y - 1, Z) + S(X - 1, Y, Z)-S(X, Y - 1, Z - 1) - S(X - 1, Y, Z - 1) - S(X - 1, Y - 1, Z) + S(X - 1, Y - 1, Z - 1)
$$
具体为什么我们可以通过可以拿一个魔方来理解.

1	`具体讲解持续更新中.......`

记忆方式

二进制001——111，奇数个（-1）则为正号。（总共2t个加数咯，算上本身嘛）

然后我们介绍一种比较小众的办法吧,我们从一维开始说:

S(X, Y, Z) = a(X, Y, Z) +	表示
001 符号：+	S(X, Y, Z - 1)
010 符号：+	S(X, Y - 1, Z)
011 符号：-	S(X, Y - 1, Z - 1)
100 符号：+	S(X - 1, Y, Z)
101 符号：-	S(X - 1, Y - 1, Z)
110 符号：-	S(X - 1, Y - 1, Z)
111 符号：+	S(X - 1, Y - 1, Z - 1)

一维前缀和

这个还是最标准的写法

1 2	`for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];`

二维前缀和

这里我们就不同于之前的写法,而是修改为了二次前缀和的模式,虽然麻烦了点,但是相差其实大同小异,影响不大.

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]+=a[i][j-1];
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]+=a[i-1][j];

三维前缀和

到了介绍三维前缀和的时候就开始展示这种求和方式的优势了**(贼好理解,理解成本很低)**

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        for(int k=1;k<=p;k++)
        a[i][j][k]+=a[i-1][j][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        for(int k=1;k<=p;k++)
        a[i][j][k]+=a[i][j-1][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        for(int k=1;k<=p;k++)
        a[i][j][k]+=a[i][j][k-1];

t维前缀和

对于t维前缀和其实就很容易可以扩展了,也就是说对于t维前缀和,时间复杂度就是O(n^t * t),但是题目也基本不可能再出维度大于3的题目了,可能性很低,要是真的出了也不至于说要像前面推导三维前缀和公式那样子了**(如果需要求子区间和其实还是要推公式)**

三维差分

理解层面同样从魔方出发……

1	`具体讲解持续更新中.......`

二进制	表示
000	——————————————B(X1, Y1, Z1) += C ——使该立方体全部加上常数C
001	B(X1, Y1, Z2 + 1) -=C
010	B(X1, Y2 + 1, Z1) -= C
011	B(X1, Y2 +1, Z2 + 1) += C
100	B(X2 +1, Y1, Z1) -= C
101	B(X2 + 1, Y1, Z2 + 1) += C
110	B(X2 + 1, Y2 + 1, Z1) += C
111	B(X2 + 1, Y2 + 1, Z2 + 1) -= C

三体攻击

三体人将对地球发起攻击。

为了抵御攻击，地球人派出了 A×B×C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。

其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i,j,k)）的生命值为 d(i,j,k)。

三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。

具体地，第 t 轮攻击用 7 个参数 lat,rat,lbt,rbt,lct,rct,ht描述；

所有满足 i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct] 的战舰 (i,j,k) 会受到 ht 的伤害。

如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入格式

第一行包括 4 个正整数 A,B,C,m；

第二行包含 A×B×C 个整数，其中第 ((i−1)×B+(j−1))×C+(k−1)+1个数为 d(i, j, k)；

第 3 到第 m+2 行中，第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。

输出格式

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。

保证一定存在这样的战舰。

数据范围

1≤A×B×C≤106

1≤×≤106,
1≤m≤106
0≤d(i, j, k), ht≤109
1≤lat≤rat≤A1
1≤lbt≤rbt≤B1
1≤lct≤rct≤C1
层、行、列的编号都从 1 开始。

输入样例：

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

输出样例：

样例解释

在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。

思路

其实将前面的三维差分和三维前缀和学会了,这道题目的难度也就基本大打折扣了.

这道题目就是要找最早的某一艘飞船会爆炸的攻击轮次,如此我们可以选择三维差分来看各个飞船的基本情况,然后二分寻找飞船是否存在爆炸情况,存在则可能轮次晚了,r = mid即可,没有爆炸就是轮次早了,l = mid + 1即可,这样就可以优化时间复杂度到最后的n^3logn(大概就是2x10^6xlog10^6=3.6x10^7)了

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e6 + 10;

int A, B, C, m;
int s[N], b[N], op[N / 2][8], tmp[N];

int get(int i, int j, int k) {
    return (i * B + j) * C + k;
}

void add(int x1, int y1, int z1, int x2, int y2, int z2, int c) {
    b[get(x1, y1, z1)] += c;
    b[get(x1, y1, z2 + 1)] -= c;
    b[get(x1, y2 + 1, z2)] -= c;
    b[get(x2 + 1, y1, z1)] -= c;
    b[get(x2 + 1, y2 + 1, z1)] += c;
    b[get(x2 + 1, y1, z2 + 1)] += c;
    b[get(x1, y2 + 1, z2 + 1)] += c;
    b[get(x2 + 1, y2 + 1, z2 + 1)] -= c;
}

void sub(int x1, int y1, int z1, int x2, int y2, int z2, int c)
{
    tmp[get(x1, y1, z1)] -= c;
    tmp[get(x1, y1, z2 + 1)] += c;
    tmp[get(x1, y2 + 1, z1)] += c;
    tmp[get(x2 + 1, y1, z1)] += c;
    tmp[get(x1, y2 + 1, z2 + 1)] -= c;
    tmp[get(x2 + 1, y1, z2 + 1)] -= c;
    tmp[get(x2 + 1, y2 + 1, z1)] -= c;
    tmp[get(x2 + 1, y2 + 1, z2 + 1)] += c;
}

bool check(int mid)
{
    memcpy(tmp, b, sizeof b);
    
    // 将前面的所有情况列出来
    fore (i, 0, mid - 1)
    {
        int x1 = op[i][0], x2 = op[i][1], y1 = op[i][2], y2 = op[i][3],
            z1 = op[i][4], z2 = op[i][5], c = op[i][6];
        sub(x1, y1, z1, x2, y2, z2, c);
    }
    me0(s);
    
    // 重新求前缀和看看是否存在负数情况
    fore (i, 1, A)
        fore (j, 1, B)
            fore (k, 1, C)
            {
                s[get(i, j, k)] = tmp[get(i, j, k)] + 
                    s[get(i - 1, j, k)] + s[get(i, j - 1, k)] - s[get(i - 1, j - 1, k)] + 
                    s[get(i, j, k - 1)] - s[get(i - 1, j, k - 1)] - s[get(i, j - 1, k - 1)] + 
                    s[get(i - 1, j - 1, k - 1)];
                if (s[get(i, j, k)] < 0) return true;
            }
    return false;
}

void solve() {
    cin >> A >> B >> C >> m;
    fore (i, 1, A) {
        fore (j, 1, B) {
            fore (k, 1, C) {
                cin >> s[get(i, j, k)];
                add(i, j, k, i, j, k, s[get(i, j, k)]);
            }
        }
    }
    
    fore (i, 0, m - 1) {
        fore (j, 0, 6) cin >> op[i][j];
    }
    
    int l = 1, r = m;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << r;
}
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

杂题——勇士传说上一篇

算法练习专栏——洛谷练习——复旦勰码基础赛 10 QFOI Round 2 下一篇