2016-12-04

UvaLive 7511 Multiplication Table【模拟】

题目链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5533

题意：

给定原矩阵，元素值为行列乘积。现已知另一个矩阵$R \times C$中的部分元素值，问你能否通过给出的元素判断出该矩阵是否为原矩阵的一部分。
数据范围：$1 \le R, C \le 1000, 所有元素值不超过1e9$

分析：

若给出的元素个数为$0$，即给出的矩阵全部为’?’，那么必定为”Yes“。
若给出的元素个数为$1$，需判断一下该位置是否可能存在，即枚举因数，然后判断一下是否超出边界。
若给出的元素个数大于等于$2$个，则利用元素值为行列乘积这一性质，找两个点来唯一确定出矩阵的一种合法情况，并判断该矩阵得到的元素值与题目给出的值是否全部相等。

代码：

/*************************************************************************
    > File Name: ecfinal_L.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/12/4 18:27:36
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
char s[10 + 5];
int mat[maxn][maxn];
int mx = 1e5 + 5;
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; ++tt){
		int r, c;
		scanf("%d%d", &r, &c);
		int ansr, ansc, ansr1, ansc1;
		ansr = ansc = -1;
		int cnt = 0;
		for(int i = 1; i <= r; ++i){
			for(int j = 1; j <= c; ++j){
				scanf("%s", s);
				if(s[0] == '?'){
					mat[i][j] = 0;
				}else{
					mat[i][j] = (int)atoi(s);
					if(ansr == -1) ansr = i;
					else ansr1 = i;
					if(ansc == -1) ansc = j;
					else ansc1 = j;
					cnt++;
				}
			}
		}
		int ansx, ansy;
		int dx, dy;
		int x, y;
		bool flag = false;
		if(!cnt) flag = true;
		else if(cnt == 1){
			for(x  = 1; x <= mx; ++x){
				if(mat[ansr][ansc] < x) break;
				if(mat[ansr][ansc] % x != 0) continue;
				dx = x - ansr, dy = mat[ansr][ansc] / x - ansc;
				if(dx >= 0 && dy >= 0){
					flag = true;
					break;
				}
				dx = mat[ansr][ansc] / x - ansr, dy = x - ansc; 
				if(dx >= 0 && dy >= 0){
					flag = true;
					break;
				}
			}
		}else{
			int a1 = mat[ansr][ansc], a2 = mat[ansr1][ansc1];
			for(x = 1; x <= mx; ++x){
				if(a1 < x) break;
				if(a1 % x != 0) continue;
				y = a1 / x;
				if(x < ansr || y < ansc) continue;
				ll tmp = x * 1ll * (ansc1 - ansc) + y * 1ll * (ansr1 - ansr) + (ansc1 - ansc) * 1ll * (ansr1 - ansr);
				if(tmp == (ll)(a2 - a1)) break;
				swap(x, y);
				tmp = x * 1ll * (ansc1 - ansc) + y * 1ll * (ansr1 - ansr) + (ansc1 - ansc) * 1ll * (ansr1 - ansr);
				if(tmp == (ll)(a2 - a1)) break;
				swap(x, y);
			}
			if(x * y == a1){
				flag = true;
				for(int i = 1; i <= r; ++i){
					for(int j = 1; j <= c; ++j){
						if(!mat[i][j]) continue;
						if((ll)mat[i][j] != (x - ansr + i) * 1ll * (y - ansc + j)){
							flag = false;
							break;
						}
					}
				}
			}
		}
		if(flag) printf("Case #%d: Yes\n", tt);
		else printf("Case #%d: No\n", tt);
	}
	return 0;
}