米哈游后端笔试第一场（含1，2题代码）

太菜了只做出两题，有没有大佬出了第三题

第一题：求两点间最短曼哈顿距离，可以穿越边界

#include <bits/stdc++.h>

using i64 = long long;

i64 n, m;

i64 getDist(std::pair<i64, i64> a, std::pair<i64, i64> b) {
	return std::min(std::abs(a.first - b.first), n - std::abs(a.first - b.first))
		+ std::min(std::abs(a.second - b.second), m - std::abs(a.second - b.second));
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	std::cin >> n >> m;
	std::vector<std::pair<i64, i64>> v(3);
	for (i64 i = 0; i < 3; i++) {
		std::cin >> v[i].first >> v[i].second;
	}

	std::cout << getDist(v[0], v[1]) + getDist(v[1], v[2]) << "\n";

	return 0;
}

第二题，树形dp瞎搞，dp[u]表示以u为根节点，最大有多少个节点距离根节点1的距离不超过k的数量

#include <bits/stdc++.h>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, k;
	std::cin >> n >> k;
	std::vector adj(n, std::vector<int>());
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		std::cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	std::vector<i64> dp(n);
	std::vector<int> d(n); // depth

	auto dfs = [&](auto self, int x, int fa) -> void {
		for (int y : adj[x]) {
			if (y == fa) continue;
			d[y] = d[x] + 1;
			self(self, y, x);
		}
	};

	auto calc = [&](auto self, int x, int fa) -> void {
		if (d[x] > k) {
			return;
		}
		dp[x] = 1;

		bool isLeaf = true;
		for (int y : adj[x]) {
			if (y == fa) continue;
			self(self, y, x);
			isLeaf = false;
			dp[x] += dp[y];
		}

		if (isLeaf) {
			dp[x] = k - d[x] + 1;
		}
	};

	dfs(dfs, 0, -1);
	calc(calc, 0, -1);

	std::cout << dp[0] << "\n";

	return 0;
}

第三题，数学概率题，不会