P3208题解

· · 题解

题面

看完题目后，我们可以先发现：如果我们确定了原矩阵的第一行和第一列，那么结合给我们的 S 矩阵，我们可以推出原矩阵 A 的每一个元素。式子如下：

A_{i,j}=S_{i,j}-A_{i-1,j}-A_{i,j-1}-A_{i-1,j-1}

这很明显，因为题目定义对于每一个 i\in[2,n],j\in[2,m] 都有 S_{i,j}=A_{i-1,j-1}+A_{i-1,j}+A_{i,j-1}+A_{i,j}。

那么，我们假设我们已经枚举出了矩阵 A 的第一行和第一列，我们该如何求出矩阵的所有元素呢？

大家可以自己在纸上手推一下这个表格，大概就长这样。

经过整理，我们可以发现，A_{i,j} 是由一堆与 S 有关的值与 A_{1,1},A_{1,j},A_{i,1} 进行加加减减得来的。我们再进一步分析，不妨先设 B_{i,j} 表示前面那一堆与 S 有关的值，我们可以找到一点规律：

B_{i,j}=S_{i,j}-B_{i-1,j}-B_{i,j-1}-B_{i-1,j-1}

也不知道为什么我的同学管这玩意叫差分！

那么我们就可以先将 B 给预处理出来。

这样式子就处理了一半了，对于后面的与 A 有关的部分，我们发现，它可以写成这样：

(-1)^{i+1}\times A_{1,j}+(-1)^{j+1}\times A_{i,1}+(-1)^{i+j+1}\times A_{1,1}

证明如下：

对于 A_{1,j} 的部分：

对于 i=1 的情况，显然。

对于 i>1 的情况，不妨设对于 i-1 成立，那么在推 A_{i,j} 的式子中，只有 A_{i-1,j} 会含有 A_{1,j} 这一项。那么结合第一个式子，A_{i,j} 中 A_{1,j} 的系数应为 -1\times (-1)^{(i-1)+1}，即 (-1)^{i+1}。

那么对于所有 i\in[1,n] 就都成立了。

同理可以证明另外两个部分，只是对于 A_{1,1} 的部分需要升到二维。

那么，现在我们也证明了式子是正确的，就可以开始搜索了吗？

当然不够，我们还需要一些优化剪枝，而这个式子只是用来剪枝的。

我们一边枚举第一行的时候，我们就可以通过式子以及每一个元素的范围求出第一列每个元素 A_{1,j} 的范围了，当范围不合法时，就回溯。否则贪心的取范围的最小值最为最终的 A_{1,j}。

然后，我们就完美的完成了这一道简单的黑题。（话说我们的教练拿这玩意作为我们的 CSP-S 的复习题）

代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n,m,p,L[205],R[205],a[205][205],b[205][205],c[205][205];//a是给我们的，b是预处理出来的，c是答案，L、R用来存储范围
  void dfs(int j){
      if(j==m+1){//搜索完了
          for(int i=2;i<=n;i++){
              for(int j=2;j<=m;j++){
                  c[i][j]=a[i][j]-c[i-1][j]-c[i][j-1]-c[i-1][j-1];
              }
          }
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  printf("%d ",c[i][j]);
              }
              puts("");
          }//输出
          exit(0);//结束
      }
      int l[205],r[205];
      for(int i=2;i<=n;i++)l[i]=L[i],r[i]=R[i];//把范围先存下来
      for(int k=0;k<p;k++){//枚举值
          c[1][j]=k;//更新答案
          bool flag=1;
          if(j>1){
              for(int i=2;i<=n&&flag;i++){
                  c[i][j]=b[i][j]+((i&1)?1:-1)*c[1][j]+(((j+i)&1)?1:-1)*c[1][1];
                  if(j&1){
                      if(c[i][j]>=p)flag=0;
                      else if(c[i][j]<0)L[i]=max(L[i],-c[i][j]);
                      else R[i]=min(R[i],p-c[i][j]-1);
                  }
                  else{
                      if(c[i][j]<0)flag=0;
                      else if(c[i][j]>=p)L[i]=max(L[i],c[i][j]+1-p);
                      else R[i]=min(R[i],c[i][j]);
                  }//更新范围
                  if(L[i]>R[i])flag=0;//不合法
                  c[i][1]=L[i];//合法，贪心的选择
              }
          }
          if(flag)dfs(j+1);//是合法的，递归
          for(int i=2;i<=n;i++)L[i]=l[i],R[i]=r[i];//否则回溯
      }
  }
  signed main()
  {
      scanf("%d%d%d",&n,&m,&p);
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
      for(int i=2;i<=n;i++)L[i]=0,R[i]=p-1;//范围的处理
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)b[i][j]=a[i][j]-b[i-1][j]-b[i][j-1]-b[i-1][j-1];//预处理b
      dfs(1);//搜索
      return 0;
  }