codeforces 509 D. Restoring Numbers（数学+构造）
2024-09-01 05:48:59
题目链接：http://codeforces.com/problemset/problem/509/D
题意：题目给出公式w[i][j]= (a[i] + b[j])% k; 给出w,要求是否存在这样的数列，若存在则求出a,b 和k
题解：如果有符合条件的点的话那么a[i],b[j]可以任意转换比如说a[i],b[j]可以转化为a[i]-p,b[i]+p。所以只要存在
符合条件的解的a[i]可以为任意值。也就是说a[i]可以先赋值为0然后其他就都可以推出来了，当然开始推出后会发现
有负的，没事，还要模一个k，接下来就要验证是否存在k。
不妨设e[i][j]=abs(a[i]+b[j]-w[i][j])显然要使e[i][j]为0才能符合条件，所以要使e[i][j]%k=0。求一下所有e[i][j]
的gcd得出一个g。显然g就是k。如果g为0肯定存在而且k取最大值+1，否则，判断g是不是大于所有的w[i][j]，如果是
那么k存在为最大值+1，不然不存在。
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
ll a[200] , b[200] , w[200][200] , e[200][200];
ll gcd(ll x , ll y) {
return (y > 0) ? gcd(y , x % y) : x;
}
int main() {
int n , m;
cin >> n >> m;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
cin >> w[i][j];
}
}
a[0] = 0;
for(int j = 0 ; j < m ; j++) {
b[j] = w[0][j] - a[0];
}
for(int j = 1 ; j < n ; j++) {
a[j] = w[j][0] - b[0];
}
ll gg = a[0] + b[0] - w[0][0];
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
e[i][j] = abs(a[i] + b[j] - w[i][j]);
gg = gcd(gg , e[i][j]);
}
}
ll k = 0;
if(gg == 0) {
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
k = max(k , w[i][j] + 1);
}
}
cout << "YES" << endl;
cout << k << endl;
for(int i = 0 ; i < n ; i++) {
if(a[i] < 0) {
cout << w[i][0] + k - b[0] << ' ';
}
else {
cout << a[i] << ' ';
}
}
cout << endl;
for(int i = 0 ; i < m ; i++) {
cout << b[i] << ' ';
}
cout << endl;
}
else {
int flag = 0;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++) {
if(gg <= w[i][j]) {
flag = 1;
break;
}
}
}
if(flag) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
cout << gg << endl;
for(int i = 0 ; i < n ; i++) {
cout << w[i][0] + gg - b[0] << ' ';
}
cout << endl;
for(int i = 0 ; i < m ; i++) {
cout << b[i] << ' ';
}
cout << endl;
}
}
return 0;
}
最新文章
- python 的 集合，字典，元组，列表
- JS产生随机数的几个用法！
- 开发工具&环境
- Net accounts命令
- Java经典实例：比较浮点数
- logback 常用配置详解（二）
- Access 2003版数据库在Win7 64位系统下的不适应
- （转）iOS被开发者遗忘在角落的NSException-其实它很强大
- 沙盒单机网站代表-Steam【推荐】
- PBRT笔记(9)——贴图
- Java面向对象之多态的静态和动态实现
- TF之RNN：matplotlib动态演示之基于顺序的RNN回归案例实现高效学习逐步逼近余弦曲线—Jason niu
- JavaScript数据类型（第一天）
- 在WindowsPhone开发中使用MVVM设计模式
- 过滤器会拦截 前端页面加载 js文件的请求
- JDK（java se development kit）的构成
- jquery select radio
- Python Json序列化与反序列化
- C#.NET里面抽象类，接口，虚方法
- sort_contours_xld算子的几种排序方式研究