Codeforces Round #622 (Div. 2) 题解

Codeforces Round #622 (Div. 2)

Fast Food Restaurant

贪心。

inline void solve() {
	int a, b, c;
	rd(a), rd(b), rd(c);
	int ans = 0;
	if (a) ++ans, --a;
	if (b) ++ans, --b;
	if (c) ++ans, --c;
	vi p;
	p.pb(a), p.pb(b), p.pb(c);
	sort(p.begin(), p.end());
	a = p[2], b = p[1], c = p[0];
	if (a && b) ++ans, --a, --b;
	if (a && c) ++ans, --a, --c;
	if (b && c) ++ans, --b, --c;
	if (a && b && c) ++ans;
	print(ans);
}

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

Different Rules

屑贪心结论题。

inline void solve() {
	ll n, x, y;
	rd(n), rd(x), rd(y);
	print(min(n, max(1ll, x + y - n + 1)), ' '), print(min(n, x + y - 1));
}

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

Skyscrapers

st 表求区间最小值，每次从区间最小值的位置左右分治，取更优的决策向上传递。

const int N = 5e5 + 7;
int n, a[N], b[N], f[N][21], ans[N];

inline int ask(int l, int r) {
	int k = log2(r - l + 1);
	return a[f[l][k]] < a[f[r-(1<<k)+1][k]] ? f[l][k] : f[r-(1<<k)+1][k];
}

inline ll solve(int l, int r) {
	if (l > r) return 0;
	if (l == r) return a[l];
	int o = ask(l, r);
	ll L = 1ll * (o - l + 1) * a[o] + solve(o + 1, r);
	ll R = 1ll * (r - o + 1) * a[o] + solve(l, o - 1);
	b[o] = L < R;
	return max(L, R);
}

inline void work(int l, int r) {
	if (l > r) return;
	if (l == r) return ans[l] = a[l], void();
	int o = ask(l, r);
	if (b[o]) {
		for (int i = o; i <= r; i++) ans[i] = a[o];
		work(l, o - 1);
	} else {
		for (int i = l; i <= o; i++) ans[i] = a[o];
		work(o + 1, r);
	}
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), f[i][0] = i;
	int w = log2(n);
	for (int j = 1; j <= w; j++)
		for (int i = 1; i+(1<<(j-1)) <= n; i++)
			f[i][j] = a[f[i][j-1]] < a[f[i+(1<<(j-1))][j-1]] ? f[i][j-1] : f[i+(1<<(j-1))][j-1];
	solve(1, n);
	work(1, n);
	for (int i = 1; i <= n; i++) print(ans[i], " \n"[i==n]);
	return 0;
}

Happy New Year

垃圾离散化 + 状压 dp。

Concatenation with intersection

exkmp 求出 $a$ 的每个后缀和 $s$ 的 LCP，以及 $b$ 的每个后缀和 $s^r$ 的 LCP。

统计每个 $a_i$ 开头的方案数，two pointers 在 $b$ 上扫到对应的区间，树状数组维护即可。

设 $n,m$ 同阶，总时间复杂度 $\mathcal O(n \log n)$，$\log$ 在树状数组上而不在求 LCP 上，常数较小。

const int N = 1e6 + 7;
int n, m, p[N], q[N], d[N], z[N];
ll c[N], ans;
char a[N], b[N], s[N];

inline void Z(char *s, int n) {
	for (int i = 1; i <= n; i++) z[i] = 0;
	z[1] = n;
	for (int i = 2, l = 0, r = 0; i <= n; i++) {
		if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
		while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
		if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
	}
}

inline void exkmp(char *s, int n, char *t, int m, int *p) {
	Z(t, m);
	for (int i = 1; i <= n; i++) p[i] = 0;
	for (int i = 1, l = 0, r = 0; i <= n; i++) {
		if (i <= r) p[i] = min(z[i-l+1], r - i + 1);
		while (i + p[i] <= n && s[i+p[i]] == t[p[i]+1]) ++p[i];
		if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
	}
}

inline void add(int x, int k) {
	if (!x) return;
	while (x <= m) c[x] += k, d[x] += k > 0 ? 1 : -1, x += x & -x;
}

inline pair<ll, int> ask(int x) {
	ll k = 0;
	int p = 0;
	while (x) k += c[x], p += d[x], x -= x & -x;
	return mp(k, p);
}

int main() {
	rd(n), rd(m);
	rds(a, n), rds(b, n), rds(s, m);
	exkmp(a, n, s, m, p);
	reverse(b + 1, b + n + 1);
	reverse(s + 1, s + m + 1);
	exkmp(b, n, s, m, q);
	reverse(q + 1, q + n + 1);
	for (int i = 1, j = 0; i <= n; i++) {
		while (j + 1 <= n && j + 1 < i + m - 1) {
			if (q[++j] == m) --q[j];
			add(q[j], q[j]);
		}
		if (p[i] == m) --p[i];
		pair<ll, int> x = ask(m), y = ask(m - p[i] - 1);
		ans += x.fi - y.fi - 1ll * (x.se - y.se) * (m - p[i] - 1);
		add(q[i], -q[i]);
	}
	print(ans);
	return 0;
}