Educational Codeforces Round 77 (Rated for Div. 2) 题解

Educational Codeforces Round 77 (Rated for Div. 2)

Heating

贪心。

inline void solve() {
	ll a, b;
	rd(a), rd(b);
	ll c = b / a, d = b - a * c;
	ll ans = d * (c + 1) * (c + 1) + (a - d) * c * c;
	print(ans);
}

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

Obtain Two Zeroes

结论题。

inline void solve() {
	int a, b;
	rd(a), rd(b);
	prints((a + b) % 3 == 0 && (a + b) / 3 <= min(a, b) ? "YES" : "NO");
}

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

Infinite Fence

首先除以 $gcd$，不妨 $a \le b > 2$，然后可以发现由于 $a,b$ 互质，因此一定存在 $ka \equiv 1 \pmod b$ 的 $k$，即 $a$ 的逆元，因此贪心的判定即可。

inline void solve() {
	ll a, b, k;
	rd(a), rd(b), rd(k);
	if (a > b) swap(a, b);
	ll d = __gcd(a, b);
	a /= d, b /= d;
	prints(b > 2 && (b - 2) / a + 1 >= k ? "REBEL" : "OBEY");
}

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

A Game with Traps

二分 + 贪心。

const int N = 2e5 + 7;
int m, n, k, t, mx, a[N];
vector< pi > e[N];

inline int pd(int o) {
	vector< pi > p;
	for (int i = mx; i > a[o]; i--)
		for (ui j = 0; j < e[i].size(); j++)
			p.pb(e[i][j]);
	p.pb(mp(n + 1, n + 1));
	sort(p.begin(), p.end());
	int x = 0, w = 0, ans = 0;
	for (ui i = 0; i < p.size(); i++) {
		int l = p[i].fi, r = p[i].se;
		if (l > w) {
			ans += (w - x) * 3 + (l - w - 1);
			x = l - 1;
		}
		w = max(w, r);
	}
	return ans + 1;
}

int main() {
	rd(m), rd(n), rd(k), rd(t);
	for (int i = 1; i <= m; i++) rd(a[i]);
	sort(a + 1, a + m + 1);
	reverse(a + 1, a + m + 1);
	for (int i = 1; i <= k; i++) {
		int l, r, x;
		rd(l), rd(r), rd(x);
		e[x].pb(mp(l, r));
		mx = max(mx, x);
	}
	int l = 1, r = m + 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (pd(mid) <= t) l = mid + 1;
		else r = mid;
	}
	print(l - 1);
	return 0;
}

Tournament

贪心 + 堆。

const int N = 1 << 18 | 1;
int n, a[N], p;
ll ans;
pq< int > q;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rd(a[i]);
		if (!~a[i]) p = i;
	}
	for (int i = 1; i < p; i++) a[i] = 0;
	reverse(a + 1, a + p + 1);
	for (int i = n; i > 1; i--) {
		q.push(-a[i]);
		if ((i & -i) == i) ans += -q.top(), q.pop();
	}
	print(ans);
	return 0;
}

Colored Tree

首先设根为 $1$，设 $\text{dep}(x)$ 为 $x$ 的深度（$\text{dep}(1) = 0$），设 $\text{dis}(x,y), \text{lca}(x,y)$ 分别为 $x,y$ 的距离和最近公共祖先，显然有 $\text{dis}(x,y) = \text{dep}(x) + \text{dep}(y) - 2\text{dep}(\text{lca}(x,y))$。

再设 $v(x,c) = [l_x \le c \le r_x]$，$g(x) = r_x - l_x + 1$，$p = \prod_{i = 1} ^ n g(i)$。

对于两个点 $x,y$ 和一个颜色 $c$，其对答案的贡献为

$$\begin{aligned} ans &= [l_x \le c \le r_x][l_y \le c \le r_y]\text{dis}(x,y)\prod_{z \ne x,y}(r_z - l_z + 1) \\\\ &= pv(x,c)v(y,c)(\text{dep}(x) + \text{dep}(y) - 2\text{dep}(\text{lca}(x,y)))\frac{1}{g(x)g(y)} \end{aligned}$$

首先考虑

$$A = v(x,c)v(y,c)(\text{dep}(x) + \text{dep}(y))\frac{1}{g(x)g(y)}$$

注意到，对于一个点 $x$ 和一个颜色 $c$，其对 $A$ 贡献为

$$v(x,c)\text{dep}(x)(\sum_{v(y,c)}\frac{1}{g(x)g(y)} - \frac{1}{g^2(x)})$$

则

$$\begin{aligned} A &= \sum_{v(x,c)}\text{dep}(x)(\sum_{v(y,c)}\frac{1}{g(x)g(y)} - \frac{1}{g^2(x)}) \\\\ &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g(x)}\sum_{v(x,c)}\frac{1}{g(x)}-\sum_{v(x,c)}\frac{\text{dep}(x)}{g^2(x)} \end{aligned}$$

显然可以把 $c$ 从小到大扫一遍，同时维护

$$\begin{aligned} A_1 &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g(x)} \\\\ A_2 &= \sum_{v(x,c)}\frac{1}{g(x)} \\\\ A_3 &= \sum_{v(x,c)}\frac{\text{dep}(x)}{g^2(x)} \end{aligned}$$

接下来考虑

$$B = v(x,c)v(y,c)\text{dep}(\text{lca}(x,y))\frac{1}{g(x)g(y)}$$

设 $s(x)$ 表示 $x$ 对 $B$ 的贡献，$S(x)$ 表示 $x$ 的所有祖先的 $s$ 之和。

注意到当我们加入一个点 $x$ 时，如果将 $x$ 的所有祖先的 $s$ 全都加上 $g(x)$，那么对于一个 $y$，其对 $B$ 的贡献 $= \frac{S(y) - s(1)}{g(y)}$。

树剖 + 树状数组即可。

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

const int N = 1e5 + 7;
int n, C, l[N], r[N], d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
modint g[N], vg[N], p, vp, now, A1, A2, A3, ans, c1[N], c2[N];
vi e[N], L[N], R[N];

void dfs(int x) {
	s[x] = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == f[x]) continue;
		d[y] = d[x] + 1;
		f[y] = x;
		dfs(y);
		s[x] += s[y];
		if (s[y] > s[son[x]]) son[x] = y; 
	}
}

void dfs(int x, int p) {
	top[x] = p;
	dfn[x] = ++num;
	rnk[num] = x;
	if (!son[x]) return;
	dfs(son[x], p);
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == f[x] || y == son[x]) continue;
		dfs(y, y);
	}
}

inline void add(modint *c, int x, modint k) {
	while (x <= n + 1) c[x] += k, x += x & -x;
}

inline modint ask(modint *c, int x) {
	modint ret = 0;
	while (x) ret += c[x], x -= x & -x;
	return ret;
}

inline void Add(int x, modint k) {
	while (x) {
		add(c1, dfn[top[x]], k);
		add(c1, dfn[x] + 1, -k);
		add(c2, dfn[top[x]], k * dfn[top[x]]);
		add(c2, dfn[x] + 1, -k * (dfn[x] + 1));
		x = f[top[x]];
	}
}

inline modint Ask(int x) {
	modint ret = -(ask(c1, 1) * 2 - ask(c2, 1));
	while (x) {
		ret += ask(c1, dfn[x]) * (dfn[x] + 1) - ask(c2, dfn[x]);
		ret -= ask(c1, dfn[top[x]] - 1) * dfn[top[x]] - ask(c2, dfn[top[x]] - 1);
		x = f[top[x]];
	}
	return ret;
}

int main() {
	rd(n), p = 1;
	for (int i = 1; i <= n; i++) {
		rd(l[i]), rd(r[i]);
		g[i] = r[i] - l[i] + 1;
		vg[i] = g[i] ^ -1;
		p *= g[i];
		C = max(C, r[i]);
		L[l[i]].pb(i), R[r[i]].pb(i);
	}
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	vp = p ^ -1;
	dfs(1);
	dfs(1, 1);
	for (int c = 1; c <= C; c++) {
		for (ui i = 0; i < L[c].size(); i++) {
			int x = L[c][i];
			A1 += d[x] * vg[x];
			A2 += vg[x];
			A3 += d[x] * vg[x] * vg[x];
			now += Ask(x) * vg[x];
			Add(x, vg[x]);
		}
		ans += A1 * A2 - A3 - 2 * now;
		for (ui i = 0; i < R[c].size(); i++) {
			int x = R[c][i];
			A1 -= d[x] * vg[x];
			A2 -= vg[x];
			A3 -= d[x] * vg[x] * vg[x];
			Add(x, -vg[x]);
			now -= Ask(x) * vg[x];
		}
	}
	print(ans * p);
	return 0;
}