Codeforces Round #677 (Div. 3) Editorial

A - Boring Apartments

直接找规律。\(ans = 10 * (dig-1) + \frac{len(len+1)}{2}\)

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		string x;
		cin >> x;
		int dig = x[0] - '0' - 1;
		int len = x.size();
		cout << dig * 10 + len * (len + 1) / 2 << endl;
	}

	return 0;
}

B - Yet Another Bookshelf

这道题也是找规律。答案是从左数第一个1开始到右数第一个数结束，之间存在的0的个数。注意：输出的下标从1开始。

#include <bits/stdc++.h>

using namespace std;

int main() {

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		while (a.back() == 0) a.pop_back();
		reverse(a.begin(), a.end());
		while (a.back() == 0) a.pop_back();
		cout << count(a.begin(), a.end(), 0) << endl;
	}
	
	return 0;
}

C - Dominant Piranha

这道题的答案不唯一，按照找出一个答案的思路出发，显然答案大概率产生在最大的元素上，我们发现，只要最大的元素与相邻的元素不相等，最大的元素就能继续成长，成为更大的元素（如果最大的元素有多个，此时，就超越那些原本一样最大的元素），然后，显然他就能成为dominant 元素。

#include <bits/stdc++.h>

using namespace std;

int main() {

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		int mx = 0;
		for (auto &it : a) {
			cin >> it;
			mx = max(mx, it);
		}
		int idx = -1;
		for (int i = 0; i < n; ++i) {
			if (a[i] != mx) continue;
			if (i > 0 && a[i - 1] != mx) idx = i + 1;
			if (i < n - 1 && a[i + 1] != mx) idx = i + 1;
		}
		cout << idx << endl;
	}
	
	return 0;
}

D - Districts Connection

题意：给出了n个地区，每一个地区有一个匪帮，id为\(a_i\)（两个地区有可能是同一个匪帮）。要求是找到一个连通图，使得两两地区的匪帮不是同一个匪帮。让你去判断存不存在这样的连通图，存在的话要输出图的边，有多个答案输出一个即可。

思路：写几个例子就能发现，只有当所有的地区都是一个匪帮时，才不存在连通图。其余情况都存在连通图。一个比较简单的构造方法就是先记录\(n=0\)的匪帮id：\(a_0\)，把其他地区匪帮id不为\(a_0\)的都挂在\(n=0\)这个地区上，这样剩下的不连通的区域就只剩下id同样是\(a_0\)的其他地区，只需要找到一个挂在\(n=0\)上的id不为\(a_0\)的地区，将剩余的挂载于其上即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<pair<int, int>> res;
		int idx = -1;
		for (int i = 1; i < n; ++i) {
			if (a[i] != a[0]) {
				idx = i;
				res.push_back({1, i + 1});
			}
		}
		if (idx == -1) {
			cout << "NO" << endl;
			continue;
		}
		for (int i = 1; i < n; ++i) {
			if (a[i] == a[0]) {
				res.push_back({idx + 1, i + 1});
			}
		}
		cout << "YES" << endl;
		for (auto [x, y] : res) cout << x << " " << y << endl;
	}
	
	return 0;
}

其他题目的官方题解（水平不足，没做）：
http://codeforces.com/blog/entry/83903