Educational Codeforces Round 80 (Rated for Div. 2) 题解

Educational Codeforces Round 80 (Rated for Div. 2)

Deadline

在 $\sqrt d$ 附近枚举。

inline void solve() {
	int n, d;
	rd(n), rd(d);
	int x = sqrt(d);
	for (int i = max(0, x - 10); i <= x + 10; i++) {
		if (i + d / (i + 1) + (d % (i + 1) != 0) <= n)
			return prints("YES"), void();
	}
	prints("NO");
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Yet Another Meme Problem

枚举 $b$ 的位数。

inline void solve() {
	ll a, b;
	rd(a), rd(b);
	ll ans = 0;
	for (ll k = 10; k <= b + 1; k *= 10) ans += a;
	print(ans);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Two Arrays

可以 dp 也可以推公式发现答案就是 $\binom{n+2m-1}{2m}$。

const int N = 1e3 + 7, M = 13;
int n, m;
modint f[M][N], ans;

int main() {
	rd(n), rd(m);
	f[0][1] = 1;
	for (int i = 0; i < m; i++)
		for (int j = 1; j <= n; j++)
			for (int k = j; k <= n; k++)
				f[i+1][k] += f[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			ans += f[m][i] * f[m][n-j+1];
	print(ans);
	return 0;
}

Minimax Problem

贪心 + 状压，复杂度 $\mathcal O(n2^m)$。

const int N = 3e5 + 7, M = 9;
int n, m, a[N][M], s[N], b[1<<M|1], S;
pq <pair <int, pi> > q;

int main() {
	rd(n), rd(m), S = (1 << m) - 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++)
			rd(a[i][j]), q.push(mp(a[i][j], mp(i, j)));
	while (q.size()) {
		int x = q.top().se.fi, y = q.top().se.se;
		q.pop();
		if (b[S^(s[x]|(1<<y))]) {
			print(x, ' '), print(b[S^(s[x]|(1<<y))]);
			return 0;
		}
		b[1<<y] = x;
		for (int k = s[x]; k; k = (k - 1) & s[x]) b[k|(1<<y)] = x;
		s[x] |= 1 << y;
		if (s[x] == S) {
			print(x, ' '), print(x);
			return 0;
		}
	}
	return 0;
}

Messenger Simulator

树状数组维护即可。

const int N = 3e5 + 7;
int n, m, p[N], c1[N], c2[N], v[N], ans[N];

inline void add(int *c, int n, int x, int o) {
	while (x <= n) c[x] += o, x += x & -x;
}

inline int ask(int *c, int x) {
	int o = 0;
	while (x) o += c[x], x -= x & -x;
	return o;
}

int main() {
	rd(n), rd(m);
	for (int i = 1, x; i <= m; i++) {
		rd(x);
		if (!v[x]) {
			v[x] = 1;
			ans[x] = x + ask(c1, n) - ask(c1, x);
			add(c1, n, x, 1);
			add(c2, m, p[x] = i, 1);
			continue;
		}
		ans[x] = max(ans[x], 1 + ask(c2, i - 1) - ask(c2, p[x]));
		add(c2, m, p[x], -1);
		add(c2, m, p[x] = i, 1);
	}
	for (int x = 1; x <= n; x++)
		if (!v[x]) ans[x] = x + ask(c1, n) - ask(c1, x);
		else ans[x] = max(ans[x], 1 + ask(c2, m) - ask(c2, p[x]));
	for (int x = 1; x <= n; x++)
		print(v[x] ? 1 : x, ' '), print(ans[x]);
	return 0;
}

Red-Blue Graph

题目太神仙了，先咕咕咕着。