蓝桥杯2018年第九届真题-三体攻击 题解

解题思路:有手就行

注意事项：不要超时

参考代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i <  (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i >  (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e6+5;
struct node {
  int la, ra, lb, rb, lc, rc;
  LL  h;
  void get() {
    read(la); read(ra);read(lb); read(rb);read(lc); read(rc); read(h);
  }
}op[N];
LL a[N], b[N];
int A, B, C, m;
inline int get(int i, int j, int k) {
  return ((i-1) * B + j - 1) * C + k;
}
void ready(int n) {
  b[get(op[n].la, op[n].lb, op[n].lc)] += op[n].h;
  b[get(op[n].ra+1, op[n].lb, op[n].lc)] -= op[n].h;
  b[get(op[n].la, op[n].rb+1, op[n].lc)] -= op[n].h;
  b[get(op[n].la, op[n].lb, op[n].rc+1)] -= op[n].h;
  
  b[get(op[n].ra+1, op[n].rb+1, op[n].rc+1)] -= op[n].h;
  b[get(op[n].la, op[n].rb+1, op[n].rc+1)] += op[n].h;
  b[get(op[n].ra+1, op[n].lb, op[n].rc+1)] += op[n].h;
  b[get(op[n].ra+1, op[n].rb+1, op[n].lc)] += op[n].h;
}
bool judge(int m) {
  memset(b, 0, sizeof b);
  _rep(1, m, i) ready(i);
  _rep(1, A*B*C, l) {
    b[l] -= b[l-B*C-C];//b[get(i-1, j-1, k)];
    b[l] -= b[l-B*C-1];//b[get(i-1, j, k-1)];
    b[l] -= b[l-C-1]; //b[get(i, j-1, k-1)];
    
    b[l] += b[l-B*C];//b[get(i-1, j, k)];
    b[l] += b[l-C];//b[get(i, j-1, k)];
    b[l] += b[l-1];//b[get(i, j, k-1)];
    b[l] += b[l-B*C-C-1];//b[get(i-1, j-1, k-1)];
    if(b[l] > a[l]) return 1;
  }
  return 0;
}
int main() {
  read(A); read(B); read(C); read(m);
  _rep(1, A*B*C, i) read(a[i]);
  _rep(1, m, i) op[i].get();
  int l = 1, r = m, ans;
  judge(1);
  while(l <= r) {
    int mid = l + r >> 1;
    if(judge(mid)) {
      ans = mid; r = mid-1;
    } else l = mid + 1;
  }
  cout << ans;
}