Educational Codeforces Round 143 (Rated for Div. 2)

题目连接

A. Two Towers

将b翻转接到a，再判断合不合法

B. Ideal Point

只考虑包含k的[l, r]，求出每个点被覆盖的次数，最后判断k是否最大且是否唯一大，考虑对l, r差分再求前缀和。

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(55, 0);
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		if (l <= k && k <= r) {
			a[l] += 1;
			a[r + 1] -= 1;
		}
	}
	for (int i = 1; i <= 50; i++) {
		a[i] += a[i - 1];
	}
	int cnt = 0;
	int mx = *max_element(a.begin(), a.end());
	for (int i = 1; i <= 50; i++) {
		if (a[i] == mx) {
			cnt++;
		}
	}
	if (a[k] == mx && cnt == 1) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
}

C. Tea Tasting

对于a[i], 它最多被后[i, n]个人品尝，假设他被后x个人品尝且产生了贡献，那么贡献为:前x-1个人喝的sum = b[i], b[i+1], b[i+2]...b[i+x-1], 第x个人为a[i]-sum,此后a[i]被喝完了，不会再产生贡献。

所以只需要二分找一下a[i]最多会产生多少次贡献，如何统计？前x-1个人喝下的茶是整数倍的b[i],第x个人喝下a[i]-sum; 单独记录第x个人的贡献，前x-1个人用差分数组维护一下。

void solve() {
	cin >> n;
 
	vector<ll> a(n + 1, 0), b(n + 1, 0), cnt(n + 2, 0);
	vector<ll> preb(n + 1, 0);
	vector<ll> ans(n + 1, 0);
	vector<P(ll)> add;
 
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) preb[i] = b[i] + preb[i - 1];
 
	for (int i = 1; i <= n; i++) {
		ll x = a[i];
		
		int l = i - 1, r = n;
 
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (a[i] >= (preb[p] - preb[i - 1])) l = mid;
			else r = mid - 1; 
		}
 
		cnt[i] += 1;
		cnt[l + 1] -= 1;
		if (l + 1 <= n && x < preb[l + 1]) {
			add.pb({l + 1, x - preb[l] + preb[i - 1]});
		}
	}
 
	for (int i = 1; i <= n; i++) {
		cnt[i] += cnt[i - 1];
	}
 
	for (int i = 1; i <= n; i++) {
		ans[i] += cnt[i] * b[i];
	}
	for (auto [i, w] : add) {
		ans[i] += w;
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " \n"[i == n];
	}
}

D. Triangle Coloring

首先考虑如何产生最大值

• 对于一个三元组，一定是选择最大的两条边；

考虑如何染色

• 题目保证了n/3为偶数，那么应该选择两组染成(红，红，蓝)和(红，蓝，蓝)；
• 这样每组都选择出两条最大的边；

考虑组合数学

一共有n/3组，其中有一半被染成了(红，红，蓝), 另一半被染成了(红，蓝，蓝)；

对每一个三元组（a, b, c）

• 如果(a=b=c)那么任取两个染成红色或蓝色，那么一共有三种情况。
• 如果(a=b<c)那么除了选c, 剩下a,b任取一个，一共两种情况。

综上$$ans = {{\frac {n}{3}} \choose {\frac{n}{6}}} * 3^{cnt1} * 2^{cnt2}$$

const ll mod = 998244353;
 
ll qmi(int a, int k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        k >>= 1;
    }
    return res;
}
 
 
ll C(int a, int b)
{
    if (b > a) return 0;
 
    ll res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = 1ll * res * j % mod;
        res = 1ll * res * qmi(i, mod - 2) % mod;
    }
    return res;
}
 
 
ll lucas(ll a, ll b)
{
    if (a < mod && b < mod) return C(a, b);
    return (ll) C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}
 
void solve() {
	int n;
	cin >> n;
	vector<int> a;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		a.pb(x);
		if (SZ(a) == 3) {
			sort(a.begin(), a.end());
			if (a[0] == a[1] && a[1] == a[2]) cnt1++;
			if (a[0] == a[1] && a[1] < a[2]) cnt2++;
			a.clear();
		}
	}
	ll ans = 1;
	ans = (C(n / 3, n / 6) * qmi(3, cnt1) % mod * qmi(2, cnt2) + mod) % mod;
	cout << ans << '\n';
}