比赛链接：

https://codeforces.com/contest/1725

A. Accumulation of Dominoes

题意：

\(n * m\) 的矩阵，从左上角开始，将 1 到 \(n * m\) 的数，放到矩阵中，先放第一行，从左到右，然后第二行，以此类推。问相邻且数字差为 1 的格子有多少个。

思路：

答案就是 \((m - 1) * n\)，特判一下只有一列的情况即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, m;
	cin >> n >> m;
	if (m == 1) cout << n - 1 << "\n";
	else cout << (m - 1) * n << "\n";
	return 0;
}

B. Basketball Together

题意：

\(n\) 个人，每个能有一个能力值，将他们分组后，每组中所有人的能力值会变成组中最大能力者的能力值，问怎样分组能让小组能力值之和严格大于 \(D\)。

思路：

将能力值排序，然后从大到小遍历，判断需要多少个人才能让这个小组能力值严格大于 \(D\)。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n, d;
	cin >> n >> d;
	vector <int> a(n);
	for (int i = 0; i < n; i ++ )
		cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = -1, j = n - 1; i < j; j -- ){
		int k = d / a[j] + 1;
		if (i + k - 1 < j){
			ans ++ ;
		}
		i += k - 1;
	}
	cout << ans << "\n";
	return 0;
}

G. Garage

题意：

如图，问下面那个正方形的面积第 \(n\) 小是多少。

思路：

打个暴力，枚举 \(a\) 和 \(b\) 找下面正方形的面积规律。
可以正方形的面积从小到大为

发现排除第一个，每三个都是两个奇数 + 一个 4 的倍数。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	LL n;
	cin >> n;
	if (n == 1) cout << "3\n";
	else{
		LL k = (n - 1 + 2) / 3;
		if (n % 3 == 0){
			cout << (k + 1) * 4 - 1 << "\n";
		}
		else if (n % 3 == 1){
			cout << (k + 1) * 4 << "\n";
		}
		else{
			cout << (k + 1) * 4 - 3 << "\n";
		}
	}
	return 0;
}

H. Hot Black Hot White

题意：

\(n\) 个数，将它们涂上黑和白两种颜色，要求涂上黑色的数的数量和涂上白色的数的数量相同。
定义 \(concat(a, b) = a * 10^{\lvert b \rvert}\)，例如 \(concat(10, 24) = 10 * 10^2 + 24 = 1024\)。
现在要确定一个 \(Z\) 及一种涂色方法，使得对于任意不同颜色的两个数，不存在 \(concat(a, b) * concat(b, a) + a * b \equiv Z\) mod 3。

思路：

因为 \(10 \equiv 1\) mod 3，所以 \(concat(a, b)\) mod 3 = \((a^{10^k} + b)\) mod 3 = \((a + b)\) mod 3。
那么 \(concat(a, b) * concat(b, a) + a * b\) mod 3 = \((a + b) * (b + a) + a * b\) mod 3 = \(a^2 + b^2\) mod 3。
对于原序列，只需要记录平方 % 3 就行。
所有数字 \(mod 3\) 之后只会是 0，1，2。
0^2 % 3 = 0
1^2 % 3 = 1
2^2 % 3 = 1
平方后 % 3 只有两种情况。
记录序列中 0 和 1 的个数，当 0 的数量小于 1 的时候，将序列长度一半的 1 涂成同一个颜色，任意两个不同颜色的数的组合只可能为 1 或 2 了，让 \(Z\) 等于 0。
否则让 \(Z\) 等于 2，因为凑不出 2 来。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n;
	cin >> n;
	vector <LL> a(n);
	int cnt0 = 0;
	for (int i = 0; i < n; i ++ ){
		cin >> a[i];
		a[i] = (a[i] * a[i]) % 3;
		if (a[i] == 0) cnt0 ++ ;
	}
	if (cnt0 <= n / 2){
		cout << "0\n";
		for (int i = 0, j = 0; i < n; i ++ ){
			if (a[i] == 1 && j < n / 2){
				cout << 0;
				j ++ ;
			}
			else cout << 1;
		}
		cout << "\n";
	}
	else{
		cout << "2\n";
		for (int i = 0, j = 0; i < n; i ++ ){
			if (a[i] == 0 && j < n / 2){
				cout << 0;
				j ++ ;
			}
			else cout << 1;
		}
		cout << "\n";
	}
	return 0;
}

M. Moving Both Hands

题意：

\(n\) 个节点，\(m\) 条边的有向带权图，有两个点，一个在 1，两个点可以沿着有向边移动，对于另一个点在 2 到 \(n\) 的所有情况，问最短路径分别是多少。

思路：

对于另一个节点的移动，其实可以看成 1 在反图上的移动。
先在正图上跑一遍 \(dijkstra\)，然后将能到达的点压入队列，再在反图上跑一遍即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector < vector < array<LL, 2> > > g(n + 1), G(n + 1);
	for (int i = 1; i <= m; i ++ ){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({w, v});
		G[v].push_back({w, u});
	}
	auto dijkstra = [&](int s){
		vector <LL> dis(n + 1, 1e18);
		vector <bool> vis(n + 1, false);
		dis[s] = 0;
		priority_queue < array<LL, 2>, vector < array<LL, 2> >, greater < array<LL, 2> > > q;
		q.push({0, s});
		while(q.size()){
			auto t = q.top();
			q.pop();
			int u = t[1];
			if (vis[u]) continue;
			vis[u] = true;
			for (auto [w, v] : g[u]){
				if (dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
					q.push({dis[v], v});
				}
			}
		}
		for (int i = 1; i <= n; i ++ ){
			if (dis[i] != 1e18){
				q.push({dis[i], i});
			}
			vis[i] = false;
		}
		while(q.size()){
			auto t = q.top();
			q.pop();
			int u = t[1];
			if (vis[u]) continue;
			vis[u] = true;
			for (auto [w, v] : G[u]){
				if (dis[v] > dis[u] + w){
					dis[v] = dis[u] + w;
					q.push({dis[v], v});
				}
			}
		}
		for (int i = 2; i <= n; i ++ ){
			if (dis[i] == 1e18) cout << "-1";
			else cout << dis[i];
			cout << " \n"[i == n];
		}
	};
	dijkstra(1);
	return 0;
}