codeforses Round 885(div 2) A

发布时间 2023-07-17 08:59:46作者: liuwansi

翻译:

A. 维卡和她的朋友们

每个测试的时间限制为1秒
每个测试的内存限制为256兆字节
输入:标准输入
输出:标准输出

维卡和她的朋友们去了一家购物中心,可以将其表示为一个边长为n和m的矩形网格。每个房间都有坐标(a,b),其中1≤a≤n,1≤b≤m。因此,我们称坐标为(c,d)的大厅为它的邻居,如果|a−c|+|b−d|=1。

维卡厌倦了空洞的时尚谈话,决定悄悄溜走。但由于她还没有机会去过其中的一家店铺,她不想离开购物中心。过了一会儿,她的朋友们注意到维卡的失踪,并开始寻找她。

目前,维卡位于坐标为(x,y)的房间,她的k个朋友分别位于坐标为(x1,y1),(x2,y2),...,(xk,yk)的房间中。坐标可以重叠。请注意,所有女孩都必须移动到相邻的房间。

每一分钟,首先维卡移动到她选择的任意一侧的相邻房间,然后每个朋友(看到维卡的选择)也选择一个相邻的房间移动到。

如果在每一分钟结束时(即在所有女孩都移动到相邻房间后),至少有一个朋友与维卡在同一个房间,她就会被捉住,其他朋友也会被叫住。

告诉我们,维卡能否永远逃脱她烦人的朋友,还是她必须在某个时候继续听空洞的时尚谈话?

输入

每个测试由多个测试用例组成。第一行包含一个整数t(1≤t≤100)- 测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含三个整数n,m,k(1≤n,m,k≤100)- 购物中心的大小和维卡的朋友数量。

每个测试用例的第二行包含一对整数x和y(1≤x≤n,1≤y≤m)- 维卡所在房间的坐标。

每个测试用例的接下来的k行中,每行包含一对整数xi和yi(1≤xi≤n,1≤yi≤m)- 第i个朋友所在房间的坐标。

输出

对于每个测试用例,如果维卡能够永远逃脱她的朋友,请输出"YES",否则输出"NO"。

你可以以任何大小写形式输出每个字母。例如,字符串"yEs","yes","Yes"和"YES"都将被接受为肯定答案。

样例

input

6
2 2 1
1 1
1 2
2 2 2
1 1
2 2
2 2
1 2 1
1 1
1 2
5 5 4
3 3
1 1
1 5
5 1
5 5
2 2 2
1 1
2 1
1 2
3 4 1
1 2
3 3

output

YES
NO
YES
NO
YES
YES

正确的做题思路:

1.最简单的的情况


即当V和朋友紧挨着且V先走V必赢,当V和朋友紧挨着且朋友先走V必输,有点类似博弈论

2.控制变量


两点横方向上距离为1,纵方向上距离也为1,此时必输

两点横方向上距离为2,纵方向上距离也为1,此时必赢

两点横方向上距离为3,纵方向上距离也为1,此时必输

3.得出结论

横距离加总距离若为偶数必输,为奇数必赢

代码如下:

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>

using namespace std;
#define int long long
int n, m, t, k, ans;
int x, y;
int xx, yy;

signed main() {
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		cin >> x >> y;
		int flag = 1;
		for (int i = 0; i < k; i++) {
			cin >> xx >> yy;
			if ((abs(x - xx) + abs(y - yy)) % 2 == 0) {
				flag = 0;
			}
		}
		if (flag == 1)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
    return 0;
}

总结:这道题还是一道很典型的思维题,很符合cf(div 2)A题的难度,总的来说还是要掌握一个正确的思维方式,只要思路正确了就能很轻松的把题目做出来,做题前先手动模拟几个样例,由特殊的简单的样例来推导复杂的一般的样例,最终得到一个具有普适性的结论