2018省赛A组第7题“三体攻击” ，题目链接：
http://oj.ecustacm.cn/problem.php?id=1364
https://www.dotcpp.com/oj/problem2275.html

（比较深入地搞过算法竞赛的队员一看就知道，这是一个三维差分的模板题。）

1. 一维差分+二分法

2. 二维差分、三维差分

下面的C++代码清晰地重现了上面的解释。如有疑问，请看注释。

//cpp文件取名为 good.cpp
#include<bits/stdc++.h>
using namespace std;
int A,B,C,n,m;
int d[1000005]; //存储舰队生命值
int D[1000005]; //三维差分数组（压维）；同时也用来计算每个点的攻击值
int lat[1000005],rat[1000005]; //存储攻击
int lbt[1000005],rbt[1000005];
int lct[1000005],rct[1000005];
int ht[1000005];
int num(int i,int j,int k) { //小技巧：压维，把三维坐标[i][j][k]转为一维的((i-1)*B+(j-1))*C+(k-1)+1
    if (i>A || j>B || k>C) return 0;
    return ((i-1)*B+(j-1))*C+(k-1)+1;
}
bool check(int x) { //检查经过x次攻击后是否有战舰爆炸
    for (int i=1; i<=n; i++) D[i]=0;
    for (int i=1; i<=x; i++) { //三维差分数组：三维有8个区间端点
        D[num(lat[i], lbt[i], lct[i])] += ht[i];
        D[num(rat[i]+1,lbt[i], lct[i])] -= ht[i];
        D[num(lat[i], rbt[i]+1,lct[i])] -= ht[i];
        D[num(lat[i], lbt[i], rct[i]+1)] -= ht[i];
        D[num(rat[i]+1,rbt[i]+1,lct[i])] += ht[i];
        D[num(lat[i], rbt[i]+1,rct[i]+1)] += ht[i];
        D[num(rat[i]+1,lbt[i], rct[i]+1)] += ht[i];
        D[num(rat[i]+1,rbt[i]+1,rct[i]+1)] -= ht[i];
    }
    for (int i=1; i<=A; i++)
        for (int j=1; j<=B; j++)
            for (int k=1; k<C; k++)
                D[num(i,j,k+1)] += D[num(i,j,k)]; //用差分数组计算出每个点的攻击值

    for (int i=1; i<=A; i++)
        for (int k=1; k<=C; k++)
            for (int j=1; j<B; j++)
                D[num(i,j+1,k)] += D[num(i,j,k)];

    for (int j=1; j<=B; j++)
        for (int k=1; k<=C; k++)
            for (int i=1; i<A; i++)
                D[num(i+1,j,k)] += D[num(i,j,k)];

    for (int i=1; i<=n; i++)
        if (D[i]>d[i])
            return true; //攻击值大于生命值
    return false;
}
int main() {
    scanf("%d%d%d%d", &A, &B, &C, &m);
    n=A*B*C;
    for (int i=1; i<=n; i++) scanf("%d", &d[i]);
    for (int i=1; i<=m; i++) scanf("%d%d%d%d%d%d%d",&lat[i],&rat[i],&lbt[i],&rbt[i],&lct[i],&rct[i],&ht[i]);

    int L=1,R=m; //经典的二分写法
    while (L<R) { //对m进行二分，找到临界值
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d\n", R); //打印临界值
    return 0;
}

正好用这个题目练练对敲和测试。
参考博文：Python在竞赛中的应用-测试数据的构造与对拍https://blog.csdn.net/weixin_43914593/article/details/111385152

1. 用python写个暴力法的对敲代码

暴力代码很容易写。下面的代码取名为baoli.py。

A,B,C,m = map(int,input().split())

ship=[]
for i in range(A):
    sublist=[]
    for j in range(B):
        sublist.append([0]*C)
    ship.append(sublist)
    
life=list(map(int,input().split()))
v=0
for i in range(A):
    for j in range(B):
        for k in range(C):
            ship[i][j][k]=life[v] #战舰生命值
            v += 1
num = m
for attacknum in range(1,m+1):
    la, ra, lb, rb, lc, rc, ht = map(int,input().split())
    for i in range(la-1,ra):
        for j in range(lb-1,rb):
            for k in range(lc-1,rc):
                ship[i][j][k] -= ht
                if ship[i][j][k]<0:
                    print(attacknum)
                    exit()

2. 用python产生测试数据

写一个py文件，按题目要求的格式产生测试数据。文件名取为test.py。

#test.py
from random import *
N = 1e4                       #自定义一个合适的值
HT = 1e9                      

A = randint(1,N)
B = randint(1,N//A)
C = randint(1,N//A//B)
m = randint(1,N)
print( A,B,C,m) #第一行

for i in range(A*B*C-1): #第二行
  print (randint(HT//1000,HT),end=' ') #生命值设大一些
print (randint(HT//1000,HT))

for i in range(m): #后面m行，每行7个
    lat = randint(1,A)
    rat = randint(lat,A) #注意：rat比lat大
    lbt = randint(1,B)
    rbt = randint(lbt,B)
    lct = randint(1,C)
    rct = randint(lct,C)
    ht = randint(1,HT/100000) #攻击值设小一些
    print (lat,rat,lbt,rbt,lct,rct,ht)

@echo off
set path=C:\MinGW\bin
g++ -o good.exe good.cpp
:loop
set path=C:\Users\hp\AppData\Local\Programs\Python\Python39
python test.py >data.in
good.exe <data.in >good.out
python baoli.py <data.in >py.out
set path=C:\Windows\System32
fc py.out good.out
good.exe <data.in
if errorlevel == 1 pause
goto loop