Contestant. Rank 1888. Rating +1.查重后刚好加了一分（跟白打没区别
A. Li Hua and Maze
题意
给定一个 \(n \times m\) 的矩阵以及两个点 \((x_1, y_1), (x_2, y_2)\)。其中，两点满足 \(|x_1-x_2|+|y_1-y_2|\geq 2\)。在矩阵中插入若干个障碍，使得两点不连通。
输出需要插入的最少障碍数。
思路
很显然，我们把起点或者终点包起来即可。
不要写错就是 \(win\)。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, m, x1, y1, x2, y2;
cin >> n >> m >> x1 >> y1 >> x2 >> y2;
int ans = 4;
if(x1 == 1 || y1 == 1 || x2 == 1 || y2 == 1 || x1 == n || y1 == m || x2 == n || y2 == m) ans = 3;
if(((x1 == 1 || x1 == n) && (y1 == 1 || y1 == m)) || ((x2 == 1 || x2 == n) && (y2 == 1 || y2 == m))) ans = 2;
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}我为什么会写错啊啊啊啊啊啊（艹
B. Li Hua and Pattern
题意
给定一个 \(n \times n\) 的矩阵，以及矩阵中若干标记点的坐标。定义一次操作可以取消或加上标记，现在给定操作数 \(k\)，在操作数用完的条件下，输出是否可以让整个矩阵旋转 \(180°\) 后和旋转前一样。
思路
首先，\(180°\) 旋转后，如果 \(n\) 为奇数，那么中心点是不会变的，也就是说 \(k\) 多余时可以全都操作在中心点上。
其次，题面等价于“将原矩阵旋转 \(180°\) 后进行操作，使其和原矩阵一致”。
那么，我们旋转后统计不一样的格子的个数 \(cnt\)。
我们不难发现，\(cnt\) 一定是偶数，因为具有对称性。而恰恰因为这个，我们只需 \(\frac{cnt}{2}\) 次操作即可让矩阵满足条件。
那么，如果操作数不够，就直接输出 \(NO\)。
否则，\(n\) 为偶数的时候，我们就需要考虑剩余操作数的奇偶性。因为在同一个点上操作两次等价于没有操作，所以当剩余的数量为偶数时，输出 \(YES\)，否则是 \(NO\)。
\(n\) 是奇数的时候，就和思路的第一句话所说的那样，直接判 \(YES\) 即可。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, k;
cin >> n >> k;
vector<vector<int>> a(n, vector<int>(n)), b(n, vector<int>(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin >> a[i][j];
b[n - i - 1][n - j - 1] = a[i][j];
}
int dif = 0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(a[i][j] != b[i][j]) dif ++;
dif /= 2;
if(dif > k){
cout << "NO\n";
return;
}
k -= dif;
cout << (n % 2 == 1 || k % 2 == 0 ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}我怎么就没想到 \(n\) 的奇偶性呢
C. Li Hua and Chess
题意
这是一道互动题。
给定一个 \(n \times m\) 的矩阵，定义一个棋子一次可以从 \(8\) 个方向移动一格或 \(\sqrt 2\) 格。
现在，在最多询问 \(3\) 次的前提下，每次询问给出一个坐标，将会得到目标棋子走到这个坐标的最少次数。
判断目标棋子的位置，并输出坐标。
思路
首先，我们从 \((1, 1)\) 展开我们的询问。
我们会得到一个数 \(t\)，通过画图我们可以看到，同一次数对应的下标集合是 \(L\) 型的，而超出 \(\min(n, m)\) 后对应的集合是一个 长或宽为 \(1\) 的长方形。
对于后者，我们可以根据 \(n, m\) 的大小确定 \(t + 1\) 是所求点的横/纵坐标，那么我们只需将未知的坐标记为 \(1\)，继续询问，所得到的 \(p + 1\) 即为未知的那个坐标，最后输出即可。
对于前者，我们最多还需问两次（不问白不问，我们直接问 \(2\) 次吧）：
询问 \((t + 1, t + 1)\)，我们得到 \(p\)，那么 \((t + 1 - p, t + 1), (t + 1, t + 1 - p)\) 其中之一就是我们需要的答案
我们询问任意一个，如 \((t + 1 - p, t + 1)\)，如果得到 \(0\)，那么这个点就是我们要的，否则另外一个点就是我们要的。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, m;
cin >> n >> m;
cout << "? 1 1\n";
cout.flush();
int t;
cin >> t;
if(t >= min(n, m)){
if(n > m){
cout << "? " << t + 1 << ' ' << 1 << '\n';
cout.flush();
int p;
cin >> p;
cout << "! " << t + 1 << ' ' << p + 1 << '\n';
cout.flush();
}else{
cout << "? " << 1 << ' ' << t + 1 << '\n';
cout.flush();
int p;
cin >> p;
cout << "! " << p + 1 << ' ' << t + 1 << '\n';
cout.flush();
}
}else{
cout << "? " << t + 1 << ' ' << t + 1 << '\n';
cout.flush();
int p;
cin >> p;
cout << "? " << t + 1 - p << ' ' << t + 1 << '\n';
cout.flush();
int q;
cin >> q;
if(q == 0) cout << "! " << t + 1 - p << ' ' << t + 1 << '\n';
else cout << "! " << t + 1 << ' ' << t + 1 - p << '\n';
cout.flush();
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}是哪个大铸币想着用 \(3\) 个边角去算啊，我不说是谁（x