拼字游戏

高斯消元 搜索

---

题面

有一个未知的$4×4$的拼盘$M$，它的每个元素都是正整数。给出$4$行元素的总和，$4$列元素的总和以及两条对角线元素总和。另外还给出了拼盘中任意$4$个位置的元素值,它们的位置在输入文件中给定。
编写一个程序求出拼盘中另外$12$个位置的正整数的值,要求这些元素的行之和,列
之和以及对角线之和与输入文件中给定的值相一致。
（输一种方案即可）

解析

$40pts$算法

经过手动推算,如果数字的位置得当（比如有很多数在中间四格或四角），我们发现弄出$8-9$个数就一定能解出整个矩阵。
于是我想到了暴枚$4$个数，摆在适当的位置，再去推。
但可能存在解到一半就（$1$表已知数，$0$表未知数）

$$\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}$$
那么在空白地方随便摆个$1$即可。
如果面向数据编程：

• 枚举范围为$1-300$，可获得$40pts$
• 枚举范围为$1-100$，可获得$50pts$
• 枚举范围为$1-80$，可获得$60pts$
  由于只输出一种方案，于是复杂度为$O(玄学)$

il void work()
{
  re int flag=1,tot=0,w=1,sum,ans=8;
  while(flag&&ans<16)
    {
      flag=0;
      fp(i,1,4)
    {
      tot=0;sum=0;w=1;
      fp(j,1,4) if(a[i][j]) ++tot,sum+=a[i][j];else w=j;
      if(tot==3) a[i][w]=h[i]-sum,flag=1,ans++;
      if(a[i][w]<=0&&tot==3) return;
      if(tot==4&&sum!=h[i]) return;
    }
      fp(i,1,4)
    {
      tot=0;sum=0;w=1;
      fp(j,1,4) if(a[j][i]) ++tot,sum+=a[j][i];else w=j;
      if(tot==3) a[w][i]=l[i]-sum,flag=1,ans++;
      if(a[w][i]<=0&&tot==3) return;
      if(tot==4&&sum!=l[i]) return;
    }
      if((a[1][1]>0)+(a[2][2]>0)+(a[3][3]>0)+(a[4][4]>0)==4&&a[1][1]+a[2][2]+a[3][3]+a[4][4]!=zs) return;
      if((a[1][1]>0)+(a[2][2]>0)+(a[3][3]>0)+(a[4][4]>0)==3)
    {
      sum=0;
      fp(i,1,4) sum+=a[i][i];
      fp(i,1,4) if(!a[i][i])
        {
          a[i][i]=zs-sum,flag=1,ans++;
          if(a[i][i]<=0&&tot==3) return;
        }
    }
      if((a[1][4]>0)+(a[2][3]>0)+(a[3][2]>0)+(a[4][1]>0)==4&&a[1][4]+a[2][3]+a[3][2]+a[4][1]!=zx) return;
      if((a[1][4]>0)+(a[2][3]>0)+(a[3][2]>0)+(a[4][1]>0)==3)
    {
      sum=0;
      fp(i,1,4) sum+=a[i][5-i];
      fp(i,1,4) if(!a[i][5-i])
        {
          a[i][5-i]=zx-sum,flag=1,ans++;
          if(a[i][5-i]<=0&&tot==3) return;
        }
    }
      if(flag==0&&ans<16)
    {
      re int tag=1;flag=1,ans++;
      fp(i,1,4)
          {
            fp(j,1,4) if(!a[i][j]) {a[i][j]=1,tag=0;break;}
            if(!tag) break;
          }
    }
    }
  if(ans==16)
      fp(i,1,4)
    {
      fp(j,1,4) printf("%d ",a[i][j]);
      puts("");
    }
      exit(0);
}
int main()
{
  freopen("scrab.in","r",stdin);
  freopen("scrab.out","w",stdout);
  fp(i,1,4) h[i]=gi();fp(i,1,4) l[i]=gi();zs=gi(),zx=gi();
  fp(i,1,4) a[gi()+1][gi()+1]=gi();
  if(!a[2][2]&&tot<4) x[++tot]=2,y[tot]=2,a[2][2]=1;
  if(!a[2][3]&&tot<4) x[++tot]=2,y[tot]=3,a[2][3]=1;
  if(!a[3][2]&&tot<4) x[++tot]=3,y[tot]=2,a[3][2]=1;
  if(!a[3][3]&&tot<4) x[++tot]=3,y[tot]=3,a[3][3]=1;
  if(!a[1][1]&&tot<4) x[++tot]=1,y[tot]=1,a[1][1]=1;
  if(!a[1][4]&&tot<4) x[++tot]=1,y[tot]=4,a[1][4]=1;
  if(!a[4][1]&&tot<4) x[++tot]=4,y[tot]=1,a[4][1]=1;
  if(!a[4][4]&&tot<4) x[++tot]=4,y[tot]=4,a[4][4]=1;
  re int flag=1;
  fp(i,1,4) fp(j,1,4) if(a[i][j]) vis[i][j]=1;
  fp(i,1,80)
    fp(j,1,80)
    fp(k,1,80)
    fp(o,1,80)
    {
      a[x[1]][y[1]]=i;
      a[x[2]][y[2]]=j;
      a[x[3]][y[3]]=k;
      a[x[4]][y[4]]=o;
      work();
      fp(i,1,4) fp(j,1,4) if(!vis[i][j]) a[i][j]=0;
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

$100pts$算法

从题意中我们可以看出，我们有$12$个未知数，而有$10$个方程。
于是就可以直接上$Gauss$消元了。
啥，有自由元？
$1-300$枚举即可。
复杂度还是很玄学。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int a[100][100],id[10][10],n,ans[100];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Gauss()
{
  fp(i,1,n)
    {
      re int now=i;
      fp(j,i+1,10)
    if(a[j][i]>a[now][i]) now=j;
      if(now^i) swap(a[i],a[now]);
      if(!a[i][i]) continue;
      fp(j,i+1,n)
    fq(k,n+1,i)
    a[j][k]-=a[i][k]*a[j][i]/a[i][i];
    }
}
il void Pre()
{
  n=16;
  fp(i,1,4) fp(j,1,4) id[i][j]=(i-1)*4+j;
  fp(i,1,10) a[i][n+1]=gi();
  fp(i,1,4) fp(j,(i-1)*4+1,(i-1)*4+4) a[i][j]=1;
  fp(i,5,8) for(re int j=i-4;j<=16;j+=4) a[i][j]=1;
  a[9][1]=a[9][6]=a[9][11]=a[9][16]=1;
  a[10][4]=a[10][7]=a[10][10]=a[10][13]=1;
  fp(i,1,4)
    {
      re int x=gi()+1,y=gi()+1,z=gi();
      ans[id[x][y]]=z;
      fp(j,1,10) if(a[j][id[x][y]]) a[j][n+1]-=z,a[j][id[x][y]]=0;
    }
  fp(i,1,10)
    {
      fp(j,1,17) printf("%d ",a[i][j]);
      puts("");
    }
}
il void out()
{
  fp(i,1,4)
    {
      fp(j,1,4) printf("%d ",ans[id[i][j]]);
      puts("");
    }
  exit(0);
}
il void dfs(re int x)
{
  printf("!!!%d\n",x);
  if(x>16) out();
  if(ans[x]) dfs(x+1);
  else
    if(a[x][x])
    {
      ans[x]=a[x][n+1];
      fq(i,n,x+1) if(a[x][i]) ans[x]-=ans[i]/a[x][i];
      ans[x]/=a[x][x];
      dfs(x+1);
    }
  else
    {
      fp(i,1,80)
    {
      ans[x]=i;
      dfs(x+1);
    }
    }
}
int main()
{
  Pre();
  Gauss();
  dfs(1);
  return 0;
}