Codeforces Global Round 7 题解

Codeforces Global Round 7

Bad Ugly Numbers

特判掉 $n=1$ 的情况，然后 $8999\cdots 9$ 就符合要求。

inline void solve() {
	int n;
	rd(n);
	if (n == 1) return puts("-1"), void();
	putchar('8');
	while (--n) putchar('9');
	puts("");
}

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

Maximums

依照题意，我们可以得到一个递推式 $a_n = \max_{i=1}^{n-1} a_i + b_n$ ，时间复杂度 $\mathcal O(n)$ 。

const int N = 2e5 + 7;
int n;
ll a[N], x;

int main() {
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++)
		print(x + a[i], " \n"[i==n]), x = max(x, x + a[i]); 
	return 0;
}

Permutation Partitions

最大值肯定可以选择 $n,n-1,\cdots,n-k+1$ 这 $k$ 个数相加。

求方案数时，相邻两个区间的间隔一定在两个选择的数中间，因此将位置之差相乘即可。

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

const int N = 2e5 + 7;
int n, k;
ll a[N], ans;
modint Ans = 1;

int main() {
	rd(n), rd(k), rda(a, n);
	for (int i = 1; i <= k; i++) ans += n + 1 - i;
	print(ans, ' ');
	vi p;
	for (int i = 1; i <= n; i++)
		if (a[i] > n - k) p.pb(i);
	for (ui i = 1; i < p.size(); i++)
		Ans *= p[i] - p[i-1];
	print(Ans);
	return 0;
}

Prefix-Suffix Palindrome

显然可以先贪心地取互为反串的最长前后缀。

取完扔掉之后，相当于要在剩下的字符串的前缀或后缀找到一个最长的回文串。

manacher 即可，时间复杂度 $\mathcal O(n)$ 。

const int N = 1e6 + 7;
int n, m;
char s[N], t[N];

inline int work(char *s, int n) {
	string ss = "$#";
	vi p;
	for (int i = 1; i <= n; i++) ss += s[i], ss += "#";
	p.pb(1);
	int mx = 0, id = 0, ans = 1;
	for (int i = 1; i < (int)ss.length(); i++) {
		p.pb(mx > i ? min(p[2*id-i], mx - i) : 1);
		while (i + p[i] < (int)ss.length() && ss[i+p[i]] == ss[i-p[i]]) ++p[i];
		if (i == p[i]) ans = max(ans, p[i]);
		if (i + p[i] > mx) mx = i + p[i], id = i;
	}
	return ans - 1;
}

inline void solve() {
	rds(s, n);
	int p = 1;
	while (p <= n && s[p] == s[n+1-p]) ++p;
	if (p == n + 1) {
		for (int i = 1; i <= n; i++) putchar(s[i]);
		return puts(""), void();
	}
	m = 0;
	for (int i = p; i <= n + 1 - p; i++) t[++m] = s[i];
	int l = work(t, m);
	reverse(t + 1, t + m + 1);
	int r = work(t, m);
	reverse(t + 1, t + m + 1);
	if (l < r) reverse(t + 1, t + m + 1), swap(l, r);
	for (int i = 1; i < p; i++) putchar(s[i]);
	for (int i = 1; i <= l; i++) putchar(t[i]);
	for (int i = p - 1; i; i--) putchar(s[i]);
	puts("");
}

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

Bombs

首先有答案是递减的。

对于当前答案 $x$ ，我们如何判断它时候能被保留下来呢？

可以发现， $x$ 能留下当且仅当存在一个位置满足它右边 $\ge x$ 的数大于它右边的炸弹数。

于是线段树维护全局 $\max$ 和区间修改即可，时间复杂度 $\mathcal O(n \log n)$ 。

const int N = 3e5 + 7;
int n, a[N], b[N], p[N], ans;
struct T {
	int l, r, x, z;
} t[N<<2];

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return;
	build(ls, l, md), build(rs, md + 1, r);
	t[p].x = max(t[ls].x, t[rs].x);
}

void spd(int p) {
	if (t[p].z) {
		t[ls].x += t[p].z;
		t[ls].z += t[p].z;
		t[rs].x += t[p].z;
		t[rs].z += t[p].z;
		t[p].z = 0;
	}
}

void add(int p, int l, int r, int k) {
	if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void();
	spd(p);
	if (l <= md) add(ls, l, r, k);
	if (r > md) add(rs, l, r, k);
	t[p].x = max(t[ls].x, t[rs].x);
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), p[a[i]] = i; 
	for (int i = 1; i <= n; i++) rd(b[i]);
	build(1, 1, n), ans = n, print(n, ' ');
	add(1, 1, p[n], 1);
	for (int i = 1; i < n; i++) {
		add(1, 1, b[i], -1);
		while (t[1].x <= 0) add(1, 1, p[--ans], 1);
		print(ans, ' ');
	}
	return 0;
}

Wise Men

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

Spiderweb Trees