蓝桥杯 2018省赛 C/C++ A T7
知识点
二分、查分
题目
标题：三体攻击
【题目描述】
三体人将对地球发起攻击。为了抵御攻击，地球人派出了 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
思路
首先想到的是暴力枚举法，时间复杂度为 $O(mAB*C)$，对于$10^6$量级的数据，会超时。
对于暴力枚举法有以下常见的三种优化方式：
- 减少枚举层数
- 减少枚举范围
- 尝试二分
在本道题目中，由于对飞船攻击范围可能是全范围的，所以减少枚举层数、减少枚举范围的方法无法使用。从飞船生命线性递减的性质中确定可以使用二分方法。
但如果简单的使用二分法，时间复杂度为$O(log_2(m)kABC)$，其中$k$为二分后区间攻击次数，这样的时间复杂度在某些情况下仍是性能较差的，那么就需要针对$ABC$进行优化。
将本道题目进行抽象为持续变更一个区间范围的值，求最后状态。针对这类问题，可以使用查分方法进行优化。
以下介绍差分算法：
- 如果数组A是B的前缀和，则B是A的差分
- 前缀和：数列前n项的和 适用于频繁求区间
- $O(N)$ 维护数组
- $O(1)$ 求区间和
- 差分：适用于频繁改变区间
- $O(1)$ 改变区间值
- $O(N)$ 求单点最终值
本道题目需要使用三维情况的差分算法
通过使用二分和差分算法，优化后时间复杂度为$O(log_2(m)(m+AB*C))$
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
int A, B, C, m, a, b, c;
#define getX(i, j, k) (((i)-1) * b + ((j)-1)) * c + (k)
void add(LL cc[], int i, int j, int k, int h)
{
if (i < a && j < b && k < c)
cc[getX(i, j, k)] += h;
}
void op(LL cc[], int *atk, int x)
{
int lat = atk[0], rat = atk[1], lbt = atk[2], rbt = atk[3], lct = atk[4], rct = atk[5], ht = x * atk[6];
add(cc, lat, lbt, lct, ht);
add(cc, lat, rbt + 1, lct, -ht);
add(cc, lat, lbt, rct + 1, -ht);
add(cc, lat, rbt + 1, rct + 1, ht);
add(cc, rat + 1, lbt, lct, -ht);
add(cc, rat + 1, rbt + 1, lct, ht);
add(cc, rat + 1, lbt, rct + 1, ht);
add(cc, rat + 1, rbt + 1, rct + 1, -ht);
}
bool check(LL sum[], LL d[])
{
for (int i = 2; i <= A; i++)
for (int j = 1; j <= B; j++)
for (int k = 1; k <= C; k++)
sum[getX(i, j, k)] += sum[getX(i - 1, j, k)];
for (int i = 1; i <= A; i++)
for (int j = 2; j <= B; j++)
for (int k = 1; k <= C; k++)
sum[getX(i, j, k)] += sum[getX(i, j - 1, k)];
for (int i = 1; i <= A; i++)
for (int j = 1; j <= B; j++)
for (int k = 2; k <= C; k++)
sum[getX(i, j, k)] += sum[getX(i, j, k - 1)];
for (int i = 1; i <= A; i++)
for (int j = 1; j <= B; j++)
for (int k = 1; k <= C; k++)
if (sum[getX(i, j, k)] > d[getX(i, j, k)])
return true;
return false;
}
int main()
{
scanf("%d %d %d %d", &A, &B, &C, &m);
a = A + 1;
b = B + 1;
c = C + 1;
LL *cc = new LL[a * b * c]; // 差分数组
LL *d = new LL[a * b * c]; // 原始血量
LL *sum = new LL[a * b * c]; // 差分数组前缀和
int(*atk)[7] = new int[m + 1][7]; //攻击数据
for (int i = 1; i <= A; i++)
for (int j = 1; j <= B; j++)
for (int k = 1; k <= C; k++)
scanf("%Ld", &d[getX(i, j, k)]);
for (int i = 1; i <= m; i++)
scanf("%d %d %d %d %d %d %d", &atk[i][0], &atk[i][1], &atk[i][2], &atk[i][3], &atk[i][4], &atk[i][5], &atk[i][6]);
int l = 1, r = m, last_mid = 0;
while (l < r)
{
int mid = (l + r) >> 1;
if (last_mid < mid)
for (int i = last_mid + 1; i <= mid; i++)
op(cc, atk[i], 1);
if (last_mid > mid)
for (int i = mid + 1; i <= last_mid; i++)
op(cc, atk[i], -1);
memcpy(sum, cc, sizeof(LL) * a * b * c);
if (check(sum, d))
r = mid;
else
l = mid + 1;
last_mid = mid;
}
cout << r << endl;
delete[] cc;
delete[] d;
delete[] sum;
delete[] atk;
return 0;
}
