1
13
2016
1

POJ3318 Matrix Multiplication

http://poj.org/problem?id=3318

题意不能更简单粗暴

随便弄一个1*N的矩阵R,因为矩阵乘法满足结合律,所以A*(B*R)=(A*B)*R,B*R的复杂度是N^2,C*R的复杂度是N^2,A*(B*R)的复杂度也是n^2,最后验证O(n)所以随机一次需要的复杂度是O(n2),多随机几次就能过啦。

我才不会告诉你只要加读入优化暴力就能过以及正确性期望我不会证

 

#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
int a[501][501],b[501][501],c[501][501],r[501],p[501],P[501],s[501];
int n;
bool ans;
inline int read(){
    int p=1,x;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')p=-1;
    x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';
    x*=p;
    return x;
}
inline bool work(){
	for(int i=1;i<=n;i++)r[i]=i;
	for(int i=1;i<=n;i++){
		p[i]=0;
		for(int j=1;j<=n;j++)p[i]+=b[i][j]*r[j];
	}
	for(int i=1;i<=n;i++){
		P[i]=0;
		for(int j=1;j<=n;j++)P[i]+=a[i][j]*p[j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)P[i]-=c[i][j]*r[j];
		if(P[i]!=0)return true;
	}
	return false;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)a[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)b[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)c[i][j]=read();
	if(work())printf("NO");
	else printf("YES");
}

只验证一次都要跑110ms,63ms的都是怪物

Category: POJ | Tags: 矩阵乘法 shi | Read Count: 559
Avatar_small
qiancl 说:
2016年1月13日 11:19

这尼玛标签写"矩阵乘法"是用来坑人的吧-。-


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com