B. Li Hua and Pattern
题意：给定一个 \(n\times n\) 的 01 矩阵，每次操作可以反转一位，你需要操作恰好 \(k\) 次，问是否能将其变为中心对称。
要变为中心对称，即为 \(\forall (i,j),a_{i,j}=a_{n-i+1,n-j+1}\)。所以，要满足条件至少需要操作不相等的对数 \(cnt\) 次。
剩下操作的显然需要凑出来：如果有中心块（\(n\) 为奇数），则可以重复操作中心块；否则需要选一个块操作两次，要求 \(cnt,k\) 的奇偶性相同。
By jiangly
void solve() {
int n, k;
std::cin >> n >> k;
int min = 0;
std::vector a(n, std::vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> a[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
min += a[i][j] != a[n - 1 - i][n - 1 - j];
}
}
min /= 2;
if (k >= min && (n % 2 == 1 || (k - min) % 2 == 0)) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
C. Li Hua and Chess
题意：交互题。在 \(n\times m\) 的棋盘上有一个棋子，每次你可以询问棋子到某位置的切比雪夫距离，在三次询问内确定棋子坐标。
首先可以询问一次左上角和一次右下角，设距离分别为 \(a,b\)。其中左上角的询问确定一个 _| 形，右下角的询问确定一个 Γ 形，两者相交，要么确定一条线，要么确定一个/两个点（一个点是因为，可能因棋盘大小限制，Γ 等形状退化成一条线段）。
对于确定一条线，要么为竖线要么为横线。不难发现，为竖线的充要条件为 \(a+b=m-1\)；为横线的充要条件为 \(a+b=n-1\)。判断出来后，确定具体坐标就是容易的：询问线的一端即可。
对于确定一个/两个点的情况，首先判断如果一个点则直接确定答案，否则询问与其中一个点的距离，如果为 0 则确定，否则为另一个点。
By jiangly
int query(int r, int c) {
std::cout << "? " << r << " " << c << std::endl;
int ans;
std::cin >> ans;
return ans;
}
void solve() {
int n, m;
std::cin >> n >> m;
int a = query(1, 1);
int b = query(n, m);
int x, y;
if (a + b == n - 1) {
x = 1 + a;
y = 1 + query(x, 1);
} else if (a + b == m - 1) {
y = 1 + a;
x = 1 + query(1, y);
} else {
if (1 + a <= n && m - b >= 1 && query(1 + a, m - b) == 0) {
x = 1 + a;
y = m - b;
} else {
x = n - b;
y = 1 + a;
}
}
std::cout << "! " << x << " " << y << std::endl;
}
实现上，单独写一个 query 函数可大幅简化代码。
D. Li Hua and Tree
题意：有一个 \(n\) 个节点，以 \(1\) 为根的有根树，点有点权。定义一个节点的重儿子为子树大小最大的儿子，如果多个相同则为编号最小的。支持两种操作：将节点 \(x\) 的重儿子翻上来；询问以 \(x\) 为根的子树的权值和。
维护每个点的子树大小、父节点，并将其儿子按照子树大小降序+编号升序扔到 set 里，则重儿子即为 set 的 begin。容易发现翻儿子时只需要改 \(O(1)\) 个节点的信息，复杂度 \(O(n\log n)\)。
By jiangly
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::vector<int> siz(n);
std::vector<i64> sum(n);
std::vector<std::vector<int>> adj(n);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<int> parent(n, -1);
std::vector<std::set<std::pair<int, int>>> s(n);
std::function<void(int)> dfs = [&](int x) {
siz[x] = 1;
sum[x] = a[x];
for (auto y : adj[x]) {
if (y == parent[x]) {
continue;
}
parent[y] = x;
dfs(y);
sum[x] += sum[y];
siz[x] += siz[y];
s[x].emplace(-siz[y], y);
}
};
dfs(0);
while (m--) {
int t, x;
std::cin >> t >> x;
x--;
if (t == 1) {
std::cout << sum[x] << "\n";
} else {
if (s[x].empty()) {
continue;
}
int y = s[x].begin()->second;
s[parent[x]].erase({-siz[x], x});
s[x].erase({-siz[y], y});
siz[x] -= siz[y];
siz[y] += siz[x];
sum[x] -= sum[y];
sum[y] += sum[x];
s[y].emplace(-siz[x], x);
s[parent[x]].emplace(-siz[y], y);
parent[y] = parent[x];
parent[x] = y;
}
}
return 0;
}