Visits: 271

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;
}