差分6/6---三体攻击--暴力枚举4/6

问题描述

　　三体人将对地球发起攻击。为了抵御攻击，地球人派出了 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。

输出格式

　　输出到标准输出。

　　输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

样例输入

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

样例说明

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

数据约定

　　对于 10% 的数据，B = C = 1；
　　对于 20% 的数据，C = 1；
　　对于 40% 的数据，A × B × C, m ≤ 10, 000；
　　对于 70% 的数据，A, B, C ≤ 200；
　　对于所有数据，A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。


　　资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 2000ms


　　请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

　　注意：
　　main函数需要返回0;
　　只使用ANSI C/ANSI C++ 标准;
　　不要调用依赖于编译环境或操作系统的特殊函数。
　　所有依赖的函数必须明确地在源文件中 #include
　　不能通过工程设置而省略常用头文件。

　　提交程序时，注意选择所期望的语言类型和编译器类型。

第一想法，模拟，暴力。

暴力枚举，解决一个问题即可，就是三维数组一维坐标表示化，我们默认下标从1开始，每个维度长度分别是a、b、c，d(i,j,k)对应的一维数组下标是(i-1)*b*c+(j-1)*c+(k-1)+1，剩下的就是简单暴力枚举即可--注：题目对此是有提示的，直接ctrl+c即可

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 

差分--差分没有看出来，只知道，差分求解某一区间上的数的操作很方便。

目前只会一维的差分，记得差分需要特殊处理区间端点。

要是差分的话，还是分为三维存储比较好，如何三维存储，避免超内存。

看看差分和前缀和---简单了解--就没用过

 想了想，不会，不会，只会暴力

差分(一维,二维,三维) 蓝桥杯三体攻击_小张张最美的博客-CSDN博客如果一维二维已经没问题的可直接跳转*三维查分一维差分首先给定一个原数组a：a[1], a[2], a[3], a[n];然后我们构造一个数组b ： b[1] ,b[2] , b[3], b[i];使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。考虑构造差分b数组最为直接的方法如下：a[0 ]= 0;b[1] = a[1] - a[0];b[2] = a[2] - a[1];b[3] =ahttps://blog.csdn.net/weixin_52879528/article/details/123227266差分的话，上面的链接足够了

初次看上面链接，再看的话，还有个不错的链接，如下

差分 --算法竞赛专题解析（32）https://www.icode9.com/content-1-857918.html

小结：模板题，直接暴力求解就好，差分实在麻烦，模拟、模拟、还是模拟，暴力求出几个解出来

经济划算

本题差分之后还要二分，最终复杂度是nlogm，不二分的话，还是n*m，和暴力一个效果，现在这就是个模板题了，看看就好，二分+三维差分模板，还不如写dp

#include

int A,B,C,n,m;//输入的A、B、C、n、m
const int Maxn = 1000005;
int s[Maxn];   //存储舰队生命值
int D[Maxn];   //三维差分数组（压维）；同时也用来计算每个点的攻击值
int x2[Maxn], y2[Maxn], z2[Maxn]; //存储区间修改的范围，即攻击的范围
int x1[Maxn], y1[Maxn], z1[Maxn]; 

int d[Maxn];                    //记录伤害，就是区间修改
int num(int x,int y,int z) {  
//题目提示压维，三维坐标(x,y,z)转为一维的((x-1)*B+(y-1))*C+(z-1)+1
    if (x>A || y>B || z>C) return 0;//超范围了
    return (x-1)*B*C+(y-1)*C+(z-1)+1;
}
bool check(int x){              //做x次区间修改。即检查经过x次攻击后是否有战舰爆炸
    for (int i=1; i<=n; i++)  D[i]=0;  //差分数组的初值，本题是0
    for (int i=1; i<=x; i++) {         //用三维差分数组记录区间修改：有8个区间端点
        D[num(x1[i],  y1[i],  z1[i])]   += d[i];
        D[num(x2[i]+1,y1[i],  z1[i])]   -= d[i];
        D[num(x1[i],  y1[i],  z2[i]+1)] -= d[i];
        D[num(x2[i]+1,y1[i],  z2[i]+1)] += d[i];
        D[num(x1[i],  y2[i]+1,z1[i])]   -= d[i];
        D[num(x2[i]+1,y2[i]+1,z1[i])]   += d[i];
        D[num(x1[i],  y2[i]+1,z2[i]+1)] += d[i];
        D[num(x2[i]+1,y2[i]+1,z2[i]+1)] -= d[i];
    }
    //x、y、z分别算前缀和
    for (int i=1; i<=A; i++)
        for (int j=1; j<=B; j++)
            for (int k=1; k>1;
        if (check(mid)) R = mid;
        else L = mid+1;
    }
	
    printf("%dn", R);  //打印临界值
    return 0;
}