题目大意：原题链接
给定三个n*n的矩阵A,B,C,验证A*B=C是否成立.
所有解法中因为只测试一组数据,因此没有使用memset清零
Hint中给的傻乎乎的TLE版本：
#include<cstdio> #include<cstring> int n,A[510][510]; int B[510][510],C[510][510]; void Input(int m[510][510]) { for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) scanf("%d",&m[i][j]); } } int main() { scanf("%d",&n); bool sign=true; Input(A),Input(B),Input(C); for(int i=1;i<=n&&sign;i++){ for(int j=1;j<=n&&sign;j++){ int sum=0; for(int k=1;k<=n&&sign;k++) sum+=A[i][k]*B[k][j]; if(sum!=C[i][j]) sign=false; } } if(sign) printf("YES"); else printf("NO"); }
AC版本解法一：神奇的输入优化
之前就看到过几次一个神奇的输入模板,不知道这段代码是否就是那个(提交多次,觉得估计在提交人数多时容易超时)
#include<cstdio> using namespace std; int n,A[505][505]; int B[505][505],C[505][505]; int Read() { int d=0; char ch,t=0; while((ch=getchar())==' '||ch==' ') ; if(ch=='-') t=1; else d=ch-'0'; while((ch=getchar())>='0'&&ch<='9') d=d*10+ch-'0'; if(t) return -d; else return d; } int main() { scanf("%d",&n); bool sign=true; for(int i=0;i<n;i++){ for(int j=0;j<n;j++) A[i][j]=Read(); } for(int i=0;i<n;i++){ for(int j=0;j<n;j++) B[i][j]=Read(); } for(int i=0;i<n;i++){ for(int j=0;j<n;j++) C[i][j]=Read(); } for(int i=0;i<n&&sign;i++){ for(int j=0;j<n&&sign;j++){ int sum=0; for(int k=0;k<n;k++) sum+=A[i][k]*B[k][j]; if(sum!=C[i][j]){ sign=false; break; } } } if(sign) printf("YES"); else printf("NO"); }
AC版本解法二：稳稳的随机化算法
#include<ctime> #include<cstdio> #include<cstdlib> #define TLE 2000 int n,A[510][510]; int B[510][510],C[510][510]; void Input(int m[510][510]) { for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) scanf("%d",&m[i][j]); } } bool Judge() { int r,c;//随机行数,列数 int time=50*TLE;//注意取的次数需要适当 while(time--){ r=rand()%n+1,c=rand()%n+1; int sum=0; for(int k=1;k<=n;k++) sum+=A[r][k]*B[k][c]; if(sum!=C[r][c]) return 0; } return 1; } int main() { scanf("%d",&n); srand(time(NULL)); Input(A),Input(B),Input(C); if(Judge()) printf("YES"); else printf("NO"); }
AC版本解法三：流弊的状态压缩
思路；
/*
Problem B: Matrix Multiplication
The author gives an approximate algorithm rather than a precise one.
Randomize a n ×1 matrix X, test if the equation A × B × X = C × X holds true.
If it is not true we can safely say "NO" to this problem.
If it is true, the possibility that A × B ≠ X is extremely little.
*/
上面是北大网站上的提示，用行向量把C矩阵和A*B矩阵压缩了，看这一句：
Randomize a n ×1 matrix X，用一个随机的列向量。
具体怎实现呢？
用压缩矩阵再比较的方法：
我习惯左乘一个行向量，所以设一个行向量X，X是1*n的矩阵，若A*B等于C则必有X*A*B等于X*C，虽然多乘了一个向量，但是时间复杂度却降低到了O(n^2)了。
这样解的实质是把一个方阵压缩成了一个行向量，向量的每一个元素都是原矩阵该列的的和，也就是说用和来比较。这样大大节省了时间。但是带来一个问题：
如这两个矩阵：
x x x x x x x x x x x x x x x x x x x x
x x 1 x x x x 1 x x x x 0 x x x x 2 x x
x x x x x x x x x x x x x x x x x x x x
x x 1 x x x x 1 x x x x 2 x x x x 0 x x
…… ……
x x x x x x x x x x x x x x x x x x x x
用压缩再比较的方法不能得到正确结果。压缩再比较的关键在于怎么样在和中体现原来每个元素的个性。关键就是X行向量怎么设定。题目在比赛结束后提示是一个随机的向量X，就是把X的每个元素设为随机数。我觉得可以把X设为一个递增的向量：{1、2、…、n}，这样更能体现每个元素的个性，而随机有可能在关键点上出现错误。
#include<cstdio> int n,A[510][510]; int B[510][510],C[510][510]; int E[510],e[510],t[510]; void Input(int m[510][510]) { for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) scanf("%d",&m[i][j]); } } bool Judge(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) t[i]+=j*A[j][i]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i]+=t[j]*B[j][i]; for(int i=1;i<=n;i++) if(e[i]!=E[i]) return false; return true; } int main() { scanf("%d",&n); Input(A),Input(B),Input(C); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) E[i]+=j*C[j][i];//关键部分:j*C[j][i]就是给C矩阵左乘了一个递增的行向量X：{1,2,3,...,n} if(Judge(n)) printf("YES"); else printf("NO"); }