Codeforces Round 864 (Div. 2)（A~D）

A. Li Hua and Maze

 给出两个不相邻的点，最少需要堵上几个方格，才能使得两个方格之间不能互相到达。

思路：显然，对于不邻任何边界的方格来说，最少需要的是4，即上下左右都堵上；邻一个边界就-1，两个方格取一下最小值即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int t, n, m, x1, y1, x2, y2;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> m;std::cin >> x1 >> y1 >> x2 >> y2;int ans1 = 4, ans2 = 4;if(x1 == 1 || x1 == n) ans1 --;if(y1 == 1 || y1 == m) ans1 --;if(x2 == 1 || x2 == n) ans2 --;if(y2 == 1 || y2 == m) ans2 --;std::cout << std::min(ans1, ans2) << '\n';}return 0;
}

B. Li Hua and Pattern

给出一个n*n的矩阵，操作k次，判断能否使得当前矩形和旋转180°后的图形完全相同。每次操作是将格子的颜色翻转。

思路：显然，将格子分为四部分，对角的两两都应该中心对称。对于两两方格的两个坐标有相加等于n+1的关系，判断一下即可。注意，对于奇数时的中心那一条，应该等于同一条线上的另一部分。对于操作次数k，如果小于不同的方格数，则一定不满足条件；若是大于k，n是偶数时，k-cnt必须是偶数。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e3 + 5;
int t, n, k;
int a[N][N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> k;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= n; j ++) {std::cin >> a[i][j];}}int m = (n + 1) / 2;int cnt = 0;for(int i = 1; i <= m; i ++) {for(int j = 1; j <= m; j ++) {if(a[i][j] != a[1 + n - i][1 + n - j])cnt ++;}}for(int i = m + 1; i <= n; i ++) {for(int j = 1; j <= n / 2; j ++) {if(a[i][j] != a[1 + n - i][1 + n - j])cnt ++;}}if(k < cnt || (k - cnt) % 2 && n % 2 == 0)std::cout << "NO" << '\n';elsestd::cout << "YES" << '\n';}return 0;
}

C. Li Hua and Chess

 在n*m的方格中猜一个确定位置。每次可以询问目标位置和询问位置的距离，注意，距离是指经过八个方向移动的最小距离，在三次询问之内找到答案。

思路：观察移动方式，我们可以发现对于一个位置来说，向外扩展x圈上的点到中心点的距离都是x。那么我们可以先询问(1, 1)点，然后再问(1 + len, 1 + len)点，当然，注意和边界的判断。那么答案位置必然在第二次询问的点的正上方或者正左方。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e3 + 5;
int t, n, m;int ask(int x, int y) {std::cout << "? " << x << ' ' << y << '\n';std::cout.flush();int dis;std::cin >> dis;return dis;
}void work() {int a = 1, b = 1;int len = ask(a, b);if(!len) {std::cout << "! " << a << ' ' << b << '\n';return;}a = std::min(a + len, n), b = std::min(b + len, m);len = ask(a, b);if(!len) {std::cout << "! " << a << ' ' << b << '\n';return;}if(len >= a && len < b) {std::cout << "! " << a << ' ' << b - len << '\n';return;}else if(len >= b && len < a) {std::cout << "! " << a - len << ' ' << b << '\n';return;}int aa = a, bb = b, ll = len;a -= len;len = ask(a, b);if(!len) {std::cout << "! " << a << ' ' << b << '\n';return;}std::cout << "! " << aa << ' ' << bb - ll << '\n';
}int main() {// std::ios::sync_with_stdio(false);// std::cin.tie(0);// std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n >> m;work();std::cout.flush();}return 0;
}

 D. Li Hua and Tree

给出一棵树，进行k次操作，操作1是计算x的子树权值的和，操作2是交换x和x的重子，即断开x和x的父节点之间的边，链接x的重子和x的父节点之间的边。定义重子是x中具有最大子树的子节点，若有多个点满足条件，则重子是索引最小的那个点。

思路：模拟整个过程即可，注意细节。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
#define int long long
const int N = 1e5 + 5;
int n, m;
std::vector<int> vec[N];
int a[N], w[N], fa[N], val[N];struct node{int w, id;bool operator<(const node &a) const{if (w != a.w) return w > a.w;return id < a.id;}
};
std::set<node> s[N];void DFS(int u, int f){val[u] = a[u];w[u] = 1;for(auto v : vec[u]){if (v == f) continue;fa[v] = u;DFS(v, u);val[u] += val[v];w[u] += w[v];s[u].insert({w[v], v});}
}signed main(){std::cin.tie(0);std::cout.tie(0);std::ios::sync_with_stdio(0);std::cin >> n >> m;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}for(int i = 1; i < n; i ++) {int u, v;std::cin >> u >> v;vec[u].push_back(v);vec[v].push_back(u);}DFS(1, -1);while(m --){int op, x;std::cin >> op >> x;if(op == 1) std::cout << val[x] << '\n';else {if (s[x].empty()) continue;int son = s[x].begin() -> id;s[fa[x]].erase({w[x], x});s[x].erase(s[x].begin());int big = w[son];int value = val[son];w[son] = w[x];w[x] -= big;val[son] = val[x];val[x] -= value;s[fa[x]].insert({w[son], son});s[son].insert({w[x], x});fa[son] = fa[x];fa[x] = son;}}return 0;
}