Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

比赛链接：

https://codeforces.com/contest/1649

A. Game

题目大意：

\(n\) 个连续的位置，0 表示海洋，1 表示陆地，只可以从一个陆地到另一个陆地上，从一个陆地到相邻的陆地不用花费，但是从第 \(i\) 个陆地到第 \(i + x\) 个陆地需要花费 \(x\)，且该移动只能进行一次。

思路：

因为跨陆地移动只能操作一次，所以我们应该从起点先通过临近移动，移动到能到的最远的陆地，然后移动到可以通过临近移动移动到第 \(n\) 个陆地的那个陆地。

代码：

#include 
using namespace std;
#define IOS() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define LL long long
LL T = 1, n;
void solve(){
	cin >> n;
	vector  a(n);
	int p = 0, q = n - 1;
	for (int i = 0; i < n; ++ i)
		cin >> a[i];
	while (a[p] == a[p + 1] && p < n) p++;
	while (a[q] == a[q - 1] && q > 0) q--;
	if (p < q) cout << q - p << "\n";
	else cout << "0\n";
}
int main(){
	IOS();
	cin >> T;
	while(T--)
		solve();
	return 0;
}

B. Game of Ball Passing

题目大意：

\(n\) 个人玩传球游戏，现在只知道每个人传了几次球，求出最少需要几个球才能完成这个游戏。

思路：

定义 \(s\) 为 \(n\) 个人传球次数的总和，\(m\) 为 \(n\) 中最多的传球次数。
容易知道当 \(m * 2 <= s\) 时，只需要一个球。有一个特殊情况，当所有人的传球次数都是 0 的时候，答案为 0。
当 \(m * 2 > s\) 时，传球次数就是 \(m * 2 - s\)。因为我们要将这种情况转化为上一种情况，也就是让 \(m * 2 <= s\)，所以容易知道传球次数就是 \(m * 2 - s\)。

代码：

#include 
using namespace std;
#define all(x) (x).begin(), (x).end()
#define IOS() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define LL long long
LL T = 1, n;
void solve(){
	cin >> n;
	vector  a(n);
	for (int i = 0; i < n; ++ i)
		cin >> a[i];
	LL s = accumulate(all(a), 0LL), m = *max_element(all(a));
	if (m == 0) cout << "0\n";
	else if (m * 2 <= s) cout << "1\n";
	else cout << 2 * m - s << "\n";
}
int main(){
	IOS();
	cin >> T;
	while(T--)
		solve();
	return 0;
}

C. Weird Sum

题目大意：

\(n * m\) 的网格，每一个格子有一个数字，同一个数字的格子可以组成一对，它们之间的距离以曼哈顿距离计算，求出网格中每一对的距离之和。

思路：

定义第 \(i\) 种数字总共有 \(len\) 个，分别为 (r_0, c_0),(r_1, c_1),...,(r_{len - 1}, c_{len - 1})。
要求的是 \(\sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} \lvert r_i - r_j \rvert + \lvert c_i - c_j \rvert\) = \(\sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} \lvert r_i - r_j \rvert + \sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} \lvert c_i - c_j \rvert\)。
两个的求法其实一样，我们以 \(r\) 为例，如果将 \(r\) 升序排好，那结果就变成 \(\sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} (r_j - r_i) = \sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} s_j - \sum_{i = 0}^{len - 1}\sum_{j = i + 1}^{len - 1} r_i = \sum_{j = 0}^{len - 1} j * r_j - \sum_{i = 0}^{len - 1}(len - 1 - i) * r_i = \sum_{i = 0}^{2 * i + 1 - len} * r_i\)
按照格子中的数将点分开，然后将它们横纵坐标分别存下来，分别排序，接着按照公式求解。

代码：

#include 
using namespace std;
#define all(x) (x).begin(), (x).end()
#define IOS() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define LL long long
#define pb push_back
const int N = 1e5 + 10;
LL n, m, ans, k;
vector  r[N], c[N];
int main(){
	IOS();
	cin >> n >> m;
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < m; ++ j){
			LL x;
			cin >> x;
			r[x].pb(i);
			c[x].pb(j);
			k = max(x, k);
		}
	for (int i = 1; i <= k; ++ i){
		sort(all(r[i]));
		LL l = 0;
		for (auto x : r[i]){
			ans += (2 * l + 1 - r[i].size()) * x;
			l++;
		}
	}
	for (int i = 1; i <= k; ++ i){
		sort(all(c[i]));
		LL l = 0;
		for (auto x : c[i]){
			ans += (2 * l + 1 - c[i].size()) * x;
			l++;
		}
	}
	cout << ans << "\n";
	return 0;
}