ASH主题欢乐赛T4题解！
2024-09-25 21:59:09
发布于：广东
24阅读
0回复
0点赞
按照普通的解法直接暴力 肯定会寄掉
直接差分然后求前缀和的话 还不如暴力（
但是我们知道差分的优点在于可以用 的时间复杂度一次性加 次区间，然后根据题目，伤害是递增的
这时候肯定有聪明的小朋友知道怎么做了——加上二分！
二分，判断加到第 次时会不会有分身死亡就行了
这样时间复杂度就压到 了（）
注意使用快读快写
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
#define rep(i, j, k, n, m, l) for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) for(k = 1; k <= l; k++)
using namespace std;
int tmp[1000005][8];//记录下每个范围的攻击
int read(){
char c = getchar();
int x = 0, f = 1;
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)){
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x * f;
}
int i, j, k, n, m, l, t;
bool check(int idx, vector <vector <vector <int>>> a){
vector <vector <vector <int>>> dp(n + 2, vector <vector <int>>(m + 2, vector <int>(l + 2)));
for(int i = 1; i <= idx; i++){
int val = tmp[i][7];
dp[tmp[i][1]][tmp[i][3]][tmp[i][5]] += val;
dp[tmp[i][2] + 1][tmp[i][3]][tmp[i][5]] -= val;
dp[tmp[i][1]][tmp[i][4] + 1][tmp[i][5]] -= val;
dp[tmp[i][1]][tmp[i][3]][tmp[i][6] + 1] -= val;
dp[tmp[i][2] + 1][tmp[i][4] + 1][tmp[i][5]] += val;
dp[tmp[i][2] + 1][tmp[i][3]][tmp[i][6] + 1] += val;
dp[tmp[i][1]][tmp[i][4] + 1][tmp[i][6] + 1] += val;
dp[tmp[i][2] + 1][tmp[i][4] + 1][tmp[i][6] + 1] -= val;//差分（压缩）
}
rep(i, j, k, n, m, l) dp[i][j][k + 1] += dp[i][j][k];
rep(k, i, j, l, n, m) dp[i][j + 1][k] += dp[i][j][k];
rep(j, k, i, m, l, n) dp[i + 1][j][k] += dp[i][j][k];//累加（解压）
rep(i, j, k, n, m, l) if(a[i][j][k] < dp[i][j][k]) return 1;//判断
return 0;
}
signed main(){
freopen("sword.in", "r", stdin);
freopen("sword.out", "w", stdout);
n = read(), m = read(), l = read(), t = read();
vector <vector <vector <int>>> a(n + 1, vector <vector <int>>(m + 1, vector <int>(l + 1)));
rep(i, j, k, n, m, l) a[i][j][k] = read();
for(int i = 1; i <= t; i++){
for(int j = 1; j <= 7; j++){
tmp[i][j] = read();
}
}
int left = 1, right = t;
while(left <= right){
int mid = left + right >> 1;
if(check(mid, a)) right = mid - 1;
else left = mid + 1;
}
cout << min(left, t);
fclose(stdin), fclose(stdout);
return 0;
}
有帮助，赞一个