Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) 题解

Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

Math Problem

贪心。

inline void solve() {
	int l = 1e9 + 1, r = 0, n;
	rd(n);
	for (int i = 1; i <= n; i++) {
		int x, y;
		rd(x), rd(y);
		r = max(r, x);
		l = min(l, y);
	}
	print(max(r - l, 0));
}

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

Box

贪心。

const int N = 1e5 + 7;
int n, a[N], b[N];

inline void solve() {
	rd(n);
	set< int > s;
	for (int i = 1; i <= n; i++) {
		rd(a[i]), s.insert(i);
	}
	for (int i = 1; i <= n; i++) {
		si it = s.upper_bound(a[i]);
		if (it != s.begin()) b[i] = *--it, s.erase(it);
		else return print(-1), void();
	}
	for (int i = 1; i <= n; i++) print(b[i], " \n"[i==n]);
}

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

Messy

构造。

const int N = 1e5 + 7;
int n, k;
char s[N], c[2] = {')', '('};
vector< pi > ans;

inline void solve() {
	ans.clear();
	rd(n), rd(k), rds(s, n);
	for (int i = 1; i <= n; i++)
		if (s[i] != c[i&1]) {
			int t = i;
			for (int j = i + 1; j <= n; j++)
				if (s[j] == c[i&1]) {
					t = j;
					break;
				}
			ans.pb(mp(i, t));
			reverse(s + i, s + t + 1);
		}
	if (2 * k != n) ans.pb(mp(2 * k, n - 1));
	print(ans.size());
	for (ui i = 0; i < ans.size(); i++)
		print(ans[i].fi, ' '), print(ans[i].se);
}

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

Optimal Subsequences

二分 + 树状数组，$\mathcal O(n \log^2 n)$。

const int N = 2e5 + 7;
int n, m, a[N], c[N], ans[N];
pq< pi > q;
pair< pi, int > p[N];

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

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

inline int qry(int x) {
	int l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (ask(mid) < x) l = mid + 1;
		else r = mid;
	}
	return a[l];
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rd(a[i]);
		q.push(mp(a[i], -i));
	}
	rd(m);
	for (int i = 1, x, y; i <= m; i++) {
		rd(x), rd(y), p[i] = mp(mp(x, y), i);
	}
	sort(p + 1, p + m + 1);
	int t = 0;
	for (int i = 1; i <= m; i++) {
		while (t < p[i].fi.fi) {
			int x = -q.top().se;
			q.pop();
			add(x);
			++t;
		}
		ans[p[i].se] = qry(p[i].fi.se);
	}
	for (int i = 1; i <= m; i++) print(ans[i]);
	return 0;
}

Arson In Berland Forest

（假的）贪心。

const int N = 1e6 + 7;
int n, m, p[N];
string s[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i], s[i].pb('.');
	for (int i = 0; i < m; i++) s[n].pb('.');
	int ans = 1e9;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= m; j++) {
			p[j] = s[i][j] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
			if (s[i][j] == '.' && j && s[i][j-1] == 'X') ans = min(ans, p[j-1]);
		}
	for (int i = 0; i < m; i++)
		for (int j = 0; j <= n; j++) {
			p[j] = s[j][i] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
			if (s[j][i] == '.' && j && s[j-1][i] == 'X') ans = min(ans, p[j-1]);
		}
	ans = (ans - 1) / 2;
	cout << ans << endl;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= m; j++) {
			p[j] = s[i][j] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
			if (p[j] <= ans) s[i][j] = '.';
		}
	for (int i = 0; i < n; i++)
		for (int j = m; j >= 0; j--) {
			p[j] = s[i][j] == 'X' ? j < m ? p[j+1] + 1 : 1 : 0;
			if (p[j] <= ans) s[i][j] = '.';
		}
	for (int i = 0; i < m; i++)
		for (int j = 0; j <= n; j++) {
			p[j] = s[j][i] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
			if (p[j] <= ans) s[j][i] = '.';
		}
	for (int i = 0; i < m; i++)
		for (int j = n; j >= 0; j--) {
			p[j] = s[j][i] == 'X' ? j < n ? p[j+1] + 1 : 1 : 0;
			if (p[j] <= ans) s[j][i] = '.';
		}
	for (int i = 0; i < n; i++) s[i].pop_back(), cout << s[i] << endl;
	return 0;
}

Wrong Answer on test 233

首先如果相邻两个正确选项一样，那么这个位置选什么都不会产生影响，因此直接将答案 $\times k$。

如果不一样，那么对于每一个位置的生成函数为 $F(x) = x^{-1} + (k - 2) + x$。

设相邻两个正确选项不一样的位置有 $c$ 个，那么答案就是 $F^c(x)$ 的正项系数和 $\times k^{n-c}$。

枚举 $(k-2)$ 项的次数，设剩下的次数为 $i$，此时正项系数和为 $\binom{c}{i}\sum_{2j > i} \binom{i}{j} = \binom{c}{i} \times \frac{2^i - [2|i]\binom{i}{\frac{i}{2}}}2$。

忽略模运算后时间复杂度为 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, k, a[N], c;
modint p[N], ans;

int main() {
	rd(n), rd(k);
	for (int i = 1; i <= n; i++) rd(a[i]);
	c = a[1] != a[n];
	for (int i = 1; i < n; i++) c += a[i] != a[i+1];
	p[0] = 1;
	for (int i = 1; i <= c; i++) p[i] = p[i-1] * i;
	for (int i = 0; i <= c; i++) ans += (p[c] / p[i] / p[c-i]) * (((modint)2 ^ i) - ((i & 1) ? 0 : p[i] / p[i>>1] / p[i>>1])) * ((modint)(k - 2) ^ (c - i)) / 2;
	ans *= (modint)k ^ (n - c);
	print(ans);
	return 0;
}