Codeforces Round #675 (Div. 2)
A. Fence
题意：
给定 三条边的长度 让你求能组成四边的第四条边长度 其中三边不共线
问题分析：
四边形的一个性质：三边之和大于第四边 注意开 long long
AC代码：
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std
;
#define ll long long
#define mem(a,b) memset((a),(b),sizeof(a));
#define lowbit(a) ((a)&-(a))
const ll inf
=0x3f3f3f3f;
const int N
=1e6+10;
long long a
[N
];
int main(){
#ifdef io
freopen("in.txt","r",stdin);
#endif
cin
.tie(0);
ll t
;
cin
>>t
;
while(t
--){
ll x
,y
,z
;
cin
>>x
>>y
>>z
;
cout
<<(ll
)(x
+y
+z
-1)<<endl
;
}
return 0;
}
B. Nice Matrix
题意：
给你一个N*M的数字矩阵 要求每行每列都构成回文串 可以变换任意位置的数值（变化值为1） 求最小的变换次数
问题分析：
先看一个点 会发现 同行有一个必须和他相等 这个点的 同列也必须和他相等 相对的 同列的呢一行的 回文位置也必须和这个点相等
这样我们就可以知道 最优的处理办法就是 将这第个四个点变成 他们中数字数字出现 次数最多的呢个数字
因为 行列可能存在奇数的情况所以 这样就不是四个点了，相当于是2个点 同理 不相等 就需要变化 所以要特判 行列的 奇数情况
看图
奇数情况：这是都是奇数 可能会出现 3*8或者8*3这种类似的情况
偶数情况：
关于位置信息 我二维数组存的矩阵是从a[1][1]开始的 偶数情况的四个点 a[i][j]=a[i][m-j+1]=a[n-i+1][j]=a[n-i+1][m-j+1] 奇数的时候就是奇数的行或者列不变，然后另一个行、列扫一遍 一些细节啥的 看代码注释：
AC代码：
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std
;
#define ll long long
#define mem(a,b) memset((a),(b),sizeof(a));
#define lowbit(a) ((a)&-(a))
const ll inf
=0x3f3f3f3f;
const int N
=1e3+10;
long long a
[N
][N
];
ll flag
[10];
int main(){
#ifdef io
freopen("in.txt","r",stdin);
#endif
cin
.tie(0);
int t
;
cin
>>t
;
while(t
--){
ll sum
=0;
ll n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
cin
>>a
[i
][j
];
}
}
ll xx
=0;
for(int i
=1;i
<=n
/2;i
++){
for(int j
=1;j
<=m
/2;j
++){
flag
[1]=a
[i
][j
];
flag
[2]=a
[i
][m
-j
+1];
flag
[3]=a
[n
-i
+1][j
];
flag
[4]=a
[n
-i
+1][m
-j
+1];
ll ans
=5000000000;
for(int k
=1;k
<5;k
++){
ll ss
=0;
for(int l
=1;l
<5;l
++){
ss
+=abs(flag
[k
]-flag
[l
]);
}
if(ss
<ans
){
ans
=ss
;
xx
=flag
[k
];
}
}
sum
+=ans
;
}
}
if(m
%2){
ll w
=m
/2+1;
for(int i
=1;i
<=n
/2;i
++){
if(a
[i
][w
]!=a
[n
-i
+1][w
]){
sum
+=abs(a
[i
][w
]-a
[n
-i
+1][w
]);
}
}
}
if(n
%2){
ll w
=n
/2+1;
for(int i
=1;i
<=m
/2;i
++){
if(a
[w
][i
]!=a
[w
][m
-i
+1]){
sum
+=abs(a
[w
][i
]-a
[w
][m
-i
+1]);
}
}
}
cout
<<sum
<<endl
;
}
return 0;
}
