拼字游戏

拼字游戏

题面

有一个未知的(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("!!!%dn",x);if(x>16) out();if(ans[x]) dfs(x+1);elseif(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;
}

转载于:.html