Codeforces Round 864 (Div. 2)
题目链接
A题
这个题是一个思维题稍微想一下应该就可以解决.
1.我们可以发现如果点(x,y)位于正方形的四个角上把这个点围起来需要两次操作
2.如果点(x,y)在正方形的4条边上,需要3个操作将其其围起来
3.如果点(x,y)在其他地方需要4个操作将其围起来
我们求出两个坐标的最小值打印出来就可以
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
int n, m;
int length(int x, int y) {
if ((x == 1 && y == 1) || (x == 1 && y == m) || (x == n && y == 1) || (x == n && y == m)) { //4个点
return 2;
} else if (x == 1 || y == 1 || x == n || y == m) { //除去4个点的4条边
return 3;
} else {
return 4;//其他情况
}
}
void solve() {
scanf("%lld %lld", &n, &m);
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << min(length(x1, y1), length(x2, y2)) << '\n'; //求出x1,y1和x2,y2的最小值
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
B题
1.先将这个图形变成翻转180度可以重合的图形,如果两个点(x1,y1)(x2,y2)关于点(x,y)对称的话,(x1+x2)/2=x,(y1+y2)/2=y.记录需要的次数cnt
2.如果k<cnt的话是不可能得到结果的打印NO
3.如果cnt>=k计算(cnt-k)%2==0的话,说明可以多操作偶数次打印yes
4,如果(cnt-k)%2==1的话,分情况讨论,如果n为奇数打印yes,因为最中心可以操作一次,如果n为偶数打印no
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
//#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 1004;
int n, k;
int a[N][N];
int number(double x, double y) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 0 && a[(int)round(2 * x - i)][(int)round(2 * y) - j] == 1) {//遍历点(i,j)找到旋转180度对应的点(2 * x - i,2 * y - j);
cnt++;//统计次数
a[(int)round(2 * x - i)][(int)round(2 * y) - j] = 0;//将对称点设置为0
}
}
}
return cnt;//返回cnt
}
void solve() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
int ans = 0;
double x, y;
x = (n + 1) * 1.0 / 2.0;//可以发现边长为n的正方形的对称点为点((n+1)/2.0,(n+1)/2.0)
y = (n + 1) * 1.0 / 2.0;
ans = number(x, y);//得到答案
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// printf("%d ", a[i][j]);
// }
// cout<<'\n';
// }
// cout<<ans<<'\n';
if (ans > k) {//如果答案大于k打印no
no;
} else {
if (n % 2 == 1) {//如果n为奇数无论什么情况都打印yes
yes;
} else {
if ((k - ans) % 2 == 0) {//否则如果(k-ans)%2==0的时候&&n%2==0的时候打印yes
yes;
} else {
no;//否则打印no
}
}
}
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}