Comet OJ – 模拟赛 #1 Day1 题解

Comet OJ - 模拟赛 #1 Day1

修行

结论：不论怎样操作，当前序列的每个数始终分别对应原序列某极小段的总和，靠前的数对应的段也靠前，且段与段两两不相交。

拥有这个结论，我们只要找到 $b$ 中每个数对应 $a$ 中的段，如果段只包含了自己并且位置相同，我们就不需要浪费操作在它身上，否则恰好需要一次操作合并出该数。

然后就是模拟了，可以 $\mathcal O(n)$ 实现，细节较多。

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

inline void solve() {
	rd(n);
	ll sa = 0, sb = 0;
	for (int i = 1; i <= n; i++) rd(a[i]), sa += a[i];
	for (int i = 1; i <= n; i++) rd(b[i]), sb += b[i];
	if (sa ^ sb) return print(-1), void();
	for (int i = 0, j = 1; j <= n; j++) {
		int k = 0;
		while (i + 1 <= n && k < b[j]) k += a[++i];
		if (k == b[j]) p[j] = i;
		else return print(-1), void();
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += b[i] && (a[i] != b[i] || i != p[i]);
	print(ans);
}

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

灾厄

显然的最小生成树，然后求树上路径长度，时间复杂度 $\mathcal O(n \log n + m + q \log n)$。

const int N = 3e5 + 7;
int n, m, q, fa[N], d[N], f[N][20], g[N][20];
vector< pi > e[N];

void dfs(int x) {
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i].fi, z = e[x][i].se;
		if (y == f[x][0]) continue;
		f[y][0] = x;
		g[y][0] = z;
		d[y] = d[x] + 1;
		for (int i = 0; f[y][i]; i++)
			f[y][i+1] = f[f[y][i]][i], g[y][i+1] = Add(g[y][i], g[f[y][i]][i]);
		dfs(y);
	}
}

inline int ask(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	int ans = 0;
	for (int i = 19; ~i; i--)
		if (d[f[y][i]] >= d[x]) ans = Add(ans, g[y][i]), y = f[y][i];
	if (x == y) return ans;
	for (int i = 19; ~i; i--)
		if (f[x][i] ^ f[y][i])
			ans = Add(ans, Add(g[x][i], g[y][i])),
			x = f[x][i], y = f[y][i];
	return Add(ans, Add(g[x][0], g[y][0]));
}

int get(int x) {
	return x == fa[x] ? x : (fa[x] = get(fa[x]));
}

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1, x, y, z = 2; i <= m; i++, z = Mul(z, 2)) {
		rd(x), rd(y);
		if (get(x) == get(y)) continue;
		fa[get(x)] = get(y), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	}
	d[1] = 1;
	dfs(1);
	rd(q);
	for (int i = 1, x, y; i <= q; i++)
		rd(x), rd(y), print(ask(x, y));
	return 0;
}

羁绊

设 $a_i$ 在序列中由大到小的排名为 $p_i$，则 $ans = \frac 13 \sum_{i=1}^n a_i (\frac 34)^{p_i}$。

带修的话，可以先离散化然后在值域上维护一棵支持单点修改的线段树即可，时间复杂度 $\mathcal O(n \log n + q \log n)$。

代码有点麻烦不写了。