Educational Codeforces Round 117 (Rated for Div. 2)A-E

Educational Codeforces Round 117 (Rated for Div. 2)A-E

A. Distance
思路：通过观察可以看出数据范围很小，暴力枚举每一种可能并判断是否合法。
代码：

#include 
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair ;
using vi = vector ;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int t, n, a[N];
int main() {
	cin >> t;
	while(t--) {
		int x, y;
		bool f = 0;
		scanf("%d%d", &x, &y);
		for(int i = 0; i <= x; i++) {
			for(int j = 0; j <= y; j++) {
				if(i + j == x - i + y - j && 2 * (i + j) == x + y) {
					f = 1; printf("%d %dn", i, j);
					break;
				}
			}
			if(f) break;
		}
		if(!f) puts("-1 -1");
	}
	return 0;
}

B. Special Permutation
思路：我们可以将a和b先剔除，然后将1-n剩余的数字从大到小排序，只有a在前n/2-1个数字中最小，b在后n/2-1个数数字中最大这种情况是合法的。
代码：

#include 
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair ;
using vi = vector ;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int t, n, d[110];
int main() {
	cin >> t;
	while(t--) {
		int a, b;
		scanf("%d%d%d", &n, &a, &b);
		vector  c;
		for(int i = n; i >= 1; i--) {
			if(i == a || i == b) continue;
			c.pb(i);
		}
		int now = 0;
		d[1] = a, d[n / 2 + 1] = b;
		for(int i = 1; i <= n; i++) {
			if(i == 1 || i == n / 2 + 1) continue;
			d[i] = c[now++];
		}
		bool f = 1;
		for(int i = 2; i <= n / 2; i++) {
			if(d[i] < d[1]) f = 0;
		}
		for(int i = n / 2 + 2; i <= n; i++) {
			if(d[i] > d[n / 2 + 1]) f = 0;
		}
		if(!f) puts("-1");
		else {
			for(int i = 1; i <= n; i++) printf("%d ", d[i]);
			puts("");
		}
		for(int i = 1; i <= n; i++) d[i] = 0;
	}
	return 0;
}

C. Chat Ban
思路：显然，这个序列具有单调性且是两个等差数列求和，可以二分在两边分类讨论，一定要注意二分边界！
代码：

#include 
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair ;
using vi = vector ;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int t, n, a[N];
int main() {
	cin >> t;
	while (t--) {
		ll k, x;
		scanf("%lld%lld", &k, &x);
		if(k + k * (k - 1) / 2 + (k - 1) * (k - 1) - (k - 1) * (k - 2) / 2 < x) printf("%lldn", 2 * k - 1);
		else {
			ll l = 1, r = 2 * k - 1;
			while(l < r) {
				ll mid = l + r >> 1;
				if(mid <= k) {
					if(mid + mid * (mid - 1) / 2 < x) l = mid + 1;
					else r = mid;
				}
				else {
					if(k + k * (k - 1) / 2 + (k - 1) * (mid - k) - (mid - k) * (mid - k - 1) / 2 < x) l = mid + 1;
					else r = mid; 
				}
			}
			printf("%lldn", l);
		}
	}
	return 0;
}

D. X-Magic Pair
思路：读完题后容易想到更相减损法的思想，但是这题一次次相减的话很容易超时，将他优化一下就可以了。
代码：

#include 
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair ;
using vi = vector ;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int t;
int main() {
	cin >> t;
	while(t--) {
		ll a, b, x;
		bool f = 0;
		scanf("%lld%lld%lld", &a, &b, &x);
		while(a != 0 && b != 0) {
			if(a < b) swap(a, b);
			if(a < x) break;
			if((a - x) % b == 0) {
				puts("YES"); f = 1; break;
			}
			else a = a % b;
		}
		if(!f) puts("NO");
	}
	return 0;
}

E. Messages
思路：读完题后会发现一个很特殊的数据范围， k i k_i ki​ <= 20，我们可以从这点入手，但是怎么求取期望数字呢？可以对每一个人的期望单独考虑，其实就是个高中组合数学的式子，每个人的总取法有C(t， k i k_i ki​)种，取到想读的那本书的取法有C(t - 1， k i k_i ki​ - 1)种(固定想读的那本书，在其余t - 1本书种取 k i k_i ki​ - 1本书)，所以每个人期望即为C(t - 1， k i k_i ki​ - 1) / C(t， k i k_i ki​) = k i k_i ki​ / t。
代码：

#include 
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair ;
using vi = vector ;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int m[N], k[N], n;
PII s[N];
int main() {
	vi res;
	cin >> n;
	int mx = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d%d", &m[i], &k[i]);
		mx = max(mx, m[i]);
	}
	double ans = 0;
	for(int t = 1; t <= 20; t++) {
		for(int i = 1; i <= n; i++) {
			s[m[i]].fi += (double)min(k[i], t) / t;
			s[m[i]].se = m[i];
		}
		sort(s + 1, s + 1 + mx, greater());
		double a = 0;
		for(int i = 1; i <= t; i++) {
			a += s[i].fi;
		}
		if(a > ans) {
			ans = a;
			res.clear();
			for(int i = 1; i <= t; i++) res.pb(s[i].se);
		}
		for(int i = 1; i <= mx; i++) s[i] = {0, 0};
	}
	cout << (int)res.size() << "n";
	for(int it : res) printf("%d ", it);
	return 0;
}

战况总结：

这一场用的是小号（虽然小号rating已经比大号高了，前期发挥还不错，但是在C题二分边界上还是想错了，调了20分钟，过完D后读E读了半天，最后也没做出来，今天又看了一下，发现昨天E其实只差一点就想出来了，还是蛮可惜的。。。