https://zybuluo.com/ysner/note/1136291
题面
有一个未知的(4×4)的拼盘(M)，它的每个元素都是正整数。给出(4)行元素的总和，(4)列元素的总和以及两条对角线元素总和。另外还给出了拼盘中任意(4)个位置的元素值,它们的位置在输入文件中给定。
编写一个程序求出拼盘中另外(12)个位置的正整数的值,要求这些元素的行之和,列
之和以及对角线之和与输入文件中给定的值相一致。
（输一种方案即可）
解析
(40pts)算法
经过手动推算,如果数字的位置得当（比如有很多数在中间四格或四角），我们发现弄出(8-9)个数就一定能解出整个矩阵。
于是我想到了暴枚(4)个数，摆在适当的位置，再去推。
但可能存在解到一半就（(1)表已知数，(0)表未知数）
egin{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
",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;
}