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$

分析:

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*************************************************************************
> 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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: