EA 的练习赛 题解

EA 的练习赛

后缀树 suffix

$ans = 26 \times 25^{n-1}$，快速幂即可。

int main() {
	int n;
	rd(n);
	print(((modint)25 ^ (n - 1)) * 26);
	return 0;
}

纯粹容器 senpai

分四种情况讨论一下，有一种情况要期望 dp，复杂度 $\mathcal O(n^4)$。

const int N = 53;
int n, a[N], p[N];
modint f[N][N][N];

inline modint DP(int o, int l, int r) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= o - l; j++)
			for (int k = 0; k <= r - o; k++)
				f[i][j][k] = 0;
	f[0][o-l][r-o] = 1;
	modint ret = 0;
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j <= o - l; j++)
			for (int k = 0; k <= r - o; k++) {
				if (!f[i][j][k]) continue;
				if (!j || !k) ret += (i - 1) * f[i][j][k];
				else {
					int w = n - 1 - i - j - k;
					f[i+1][j-1][k] += f[i][j][k] * j / (j + k + w);
					f[i+1][j][k-1] += f[i][j][k] * k / (j + k + w);
					f[i+1][j][k] += f[i][j][k] * w / (j + k + w);
				}
			}
	return ret;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 1; i <= n; i++) {
		int l = i, r = i;
		while (l && a[l] <= a[i]) --l;
		while (r <= n && a[r] <= a[i]) ++r;
		if (!l && r > n) print(n - 1, ' ');
		else if (!l) print((modint)(n - r + i - 1) * (r - i) / (r - i + 1) + (r - i - 1), ' ');
		else if (r > n) print((modint)(n - i + l - 1) * (i - l) / (i - l + 1) + (i - l - 1), ' ');
		else print(DP(i, l, r), ' ');
	}
	return 0;
}

丝之割 silksong

$n^2$ 的 dp，注意到转移是一个一次函数，斜率优化 + 单调队列做到 $\mathcal O(n)$。

const int N = 3e5 + 7;
int n, m, c[N], t, l, r, qu[N];
pi p[N];
pair<ll, ll> q[N];
ll a[N], b[N], f[N];

inline ld calc(pair<ll, ll> a, pair<ll, ll> b) {
	return 1.0L * (b.se - a.se) / (a.fi - b.fi);
}

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 2; i <= n; i++) a[i] = min(a[i], a[i-1]);
	for (int i = 1; i <= n; i++) rd(b[i]);
	for (int i = n - 1; i; i--) b[i] = min(b[i], b[i+1]);
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), c[x] = max(c[x], y);
	for (int i = 2, j = 0; i <= n; i++)
		if (c[i] > j) j = c[i], p[++t] = mp(i, j);
	p[t+1].fi = n + 1;
	q[0] = mp(a[p[1].fi-1], 0), qu[0] = 0;
	for (int i = 1; i <= t; i++) {
		while (l < r && calc(q[l], q[l+1]) < b[p[i].se+1]) ++l;
		f[i] = q[l].fi * b[p[i].se+1] + q[l].se;
		pair<ll, ll> o = mp(a[p[i+1].fi-1], f[i]);
		while (l < r && calc(q[r-1], q[r]) > calc(q[r], o)) --r;
		if (o.fi != q[r].fi) q[++r] = o, qu[r] = i;
	}
	print(f[t]);
	return 0;
}

最优性剪枝 search

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

燔祭 sacrificial

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