Codeforces Round #631 (Div. 1) – Thanks, Denis aramis Shitov! 题解

Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov!

Dreamoon Likes Coloring

简单构造题。

首先判无解，无解的情况只有两种，要么所有数的和加起来 $<n$，要么第 $i$ 个数大于 $n-i+1$。

然后倒着构造，每次先尽量不重复的覆盖，若第 $i$ 个颜色的左端点 $< i$，则将左端点手动设置为 $i$ 即可。

时间复杂度 $\mathcal O(n)$。

#define Fail return print(-1), 0
const int N = 1e5 + 7;
int n, m, a[N], b[N];
ll s;

int main() {
	rd(n), rd(m), rda(a, m);
	for (int i = 1; i <= m; i++) s += a[i];
	if (s < n) Fail;
	for (int i = 1; i <= m; i++)
		if (a[i] > n - i + 1) Fail;
	for (int i = m, j = n + 1; i; i--) {
		b[i] = j -= a[i];
		if (b[i] < i) b[i] = j = i;
	}
	for (int i = 1; i <= m; i++) print(b[i], " \n"[i==m]);
	return 0;
}

Dreamoon Likes Sequences

简单计数题。

由于要求 $a$ 递增且前缀异或和也要递增，因此在二进制下，后一个数要比前一个数至少多一位。

因此将每一个位数的数的个数乘起来，注意由于可以不选这个位数，因此个数要 $+1$，然后由于最后至少要有一个数，所以最后再 $-1$。

时间复杂度 $\mathcal O(T \log n)$。

int n;

inline void solve() {
	rd(n), rd(P);
	if (P == 1) return print(0);
	modint ans = 1;
	int t = 1;
	while (t <= n) ans *= min(n, (t << 1) - 1) - t + 2, t <<= 1;
	print(ans - 1);
}

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

Drazil Likes Heap

贪心，从大到小依次考虑每个数，如果这个数可以删就删，不能跳过。

判断是否能删的方式为，删除这个数受到影响的最深的节点的深度是否 $> g$，如果 $> g$ 则说明可以删除。

但这题有个很大的坑点，给定的代码中要访问到编号为 $2^h \sim 2^{h+1}-1$ 的节点，然后又是多测，所以要清空两倍长度的数组。

然后就有大概一半人都因此 FST 了。。。

时间复杂度 $\mathcal O(n \log n)$。

const int N = 1 << 21 | 1;
int h, g, a[N], d[N], p[N], t;
pq<int> q;

inline int find(int p) {
	if (!a[ls] && !a[rs]) return p;
	if (a[ls] > a[rs]) return find(ls);
	return find(rs);
}

inline void work(int p) {
	if (!a[ls] && !a[rs]) return;
	if (a[ls] > a[rs]) return swap(a[p], a[ls]), ::p[a[p]] = p, work(ls);
	swap(a[p], a[rs]), ::p[a[p]] = p, work(rs);
}

inline int work() {
	while (d[find(p[q.top()])] == g) q.pop();
	int p = ::p[q.top()];
	q.pop();
	a[p] = 0, work(p);
	return p;
}

inline void solve() {
	rd(h), rd(g);
	for (int i = 1; i < (1 << (h + 1)); i++) a[i] = 0;
	rda(a, (1 << h) - 1), t = 0;
	d[1] = 1;
	for (int i = 2; i < (1 << h); i++) d[i] = d[i>>1] + 1;
	while (q.size()) q.pop();
	for (int i = 1; i < (1 << h); i++) q.push(a[i]), p[a[i]] = i;
	vi p;
	for (int i = 1; i <= (1 << h) - (1 << g); i++) p.pb(work());
	ll ans = 0;
	for (int i = 1; i < (1 << g); i++) ans += a[i];
	print(ans);
	for (int x : p) print(x, ' ');
	prints("");
}

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

Dreamoon Likes Strings

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

Dreamoon Loves AA

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