P8666 [蓝桥杯 2018 省 A] 三体攻击

GUO120822 · 2024-01-10 21:37:09 · 题解

在 12 月 30 日更新。

先看下题目。

• 题目大意

这题其实就是一个修改问题，每次修改一个部分，看第几次有一个战舰累计受到的总伤害超过其防御力，就输出这个攻击的轮数。

• 思路

我们读完题，会发现这道题其实具有单调性。为什么呢？因为操作轮数越多，有某一个船爆炸的概率就越大。所以可以二分答案。

l=1;
r=m;
while (l<=r)
{
    mid=l+r>>1;
    if (check(mid)) r=mid-1;
    else l=mid+1;
}

那么怎么检查呢？这就用到了三维差分。

三维差分怎么做？我们先来看看一维和二维的我们是怎么做的。

一维：

a[s]+=h;
a[t+1]-=h;

二维（奇减偶加）：

b[sx][sy]+=h;
b[sx][ty+1]-=h;
b[tx+1][sy]-=h;
b[tx+1][ty+1]+=h;

由此，我们根据容斥原理，发现三维的是奇加偶减，可得三维差分公式：

c[calc(sx,sy,sz)]+=h;
c[calc(tx+1,sy,sz)]-=h;
c[calc(sx,ty+1,sz)]-=h;
c[calc(sx,sy,tz+1)]-=h;
c[calc(sx,ty+1,tz+1)]+=h;
c[calc(tx+1,sy,tz+1)]+=h;
c[calc(tx+1,ty+1,sz)]+=h;
c[calc(tx+1,ty+1,tz+1)]-=h;

在做完差分后，再求前缀和（容斥原理，奇加偶减）。

c[calc(i,j,k)]+=
c[calc(i-1,j,k)]
+c[calc(i,j-1,k)]
+c[calc(i,j,k-1)]
-c[calc(i-1,j-1,k)]
-c[calc(i-1,j,k-1)]
-c[calc(i,j-1,k-1)]
+c[calc(i-1,j-1,k-1)];

计算函数指的是把三维压成一维，映射它在一维数组中的位置。

int calc(int a,int b,int c)
{
    return max(0ll,((a-1)*B+(b-1))*C+(c-1)+1);
                |
          防越界
}

最后，展示。

注意 HACK 数据。

• 代码

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  const int N=1e6+10;
  int A,B,C,m,i,j,k,a[N],c[N];
  int sx[N],sy[N],sz[N],tx[N],ty[N],tz[N],h[N];
  int l,r,mid;
  int calc(int a,int b,int c)
  {
  return max(0ll,((a-1)*B+(b-1))*C+(c-1)+1);
  }
  void cf(int sx,int sy,int sz,int tx,int ty,int tz,int h)
  {
  c[calc(sx,sy,sz)]+=h;
  c[calc(tx+1,sy,sz)]-=h;
  c[calc(sx,ty+1,sz)]-=h;
  c[calc(sx,sy,tz+1)]-=h;
  c[calc(sx,ty+1,tz+1)]+=h;
  c[calc(tx+1,sy,tz+1)]+=h;
  c[calc(tx+1,ty+1,sz)]+=h;
  c[calc(tx+1,ty+1,tz+1)]-=h;
  }
  bool check(int mid)
  {
  memset(c,0,sizeof(c));
  int i,j,k;
  for (i=1;i<=mid;i++) cf(sx[i],sy[i],sz[i],tx[i],ty[i],tz[i],h[i]);
  for (i=1;i<=A;i++)
  {
      for (j=1;j<=B;j++)
      {
          for (k=1;k<=C;k++)
          {
              c[calc(i,j,k)]+=
              c[calc(i-1,j,k)]
              +c[calc(i,j-1,k)]
              +c[calc(i,j,k-1)]
              -c[calc(i-1,j-1,k)]
              -c[calc(i-1,j,k-1)]
              -c[calc(i,j-1,k-1)]
              +c[calc(i-1,j-1,k-1)];
              if (c[calc(i,j,k)]>a[calc(i,j,k)]) return true; 
          }
      }
  }
  return false;
  }
  signed main()
  {
  scanf("%lld%lld%lld%lld",&A,&B,&C,&m);
  for (i=1;i<=A;i++)
  {
      for (j=1;j<=B;j++)
      {
          for (k=1;k<=C;k++) scanf("%lld",&a[calc(i,j,k)]);
      }
  }
  for (i=1;i<=m;i++) scanf("%lld%lld%lld%lld%lld%lld%lld",&sx[i],&tx[i],&sy[i],&ty[i],&sz[i],&tz[i],&h[i]);
  l=1;
  r=m;
  while (l<=r)
  {
      mid=l+r>>1;
      if (check(mid)) r=mid-1;
      else l=mid+1;
  }
  printf("%lld",l);
  return 0;
  }