Visits: 225

Codeforces Round #614 (Div. 1)

NEKO’s Maze Game

动态维护有多少对格子可以阻碍 $(1,1)$ 和 $(2,n)$ 相连，如果存在则意味着 No，否则为 Yes，模拟即可。

const int N = 1e5 + 7;
int n, q, a[2][N], ans;

inline int pd(int x, int y) {
    if (!a[x][y]) return 0;
    return a[x^1][y-1] + a[x^1][y] + a[x^1][y+1];
}

int main() {
    rd(n), rd(q);
    for (int i = 1; i <= q; i++) {
        int x, y;
        rd(x), rd(y);
        --x;
        ans -= pd(x, y);
        a[x][y] ^= 1;
        ans += pd(x, y);
        prints(ans ? "No" : "Yes");
    } 
    return 0;
}

Aroma’s Search

由于 $a > 1$，因此范围内的点只有 $\mathcal O(\log w)$ 个，那么枚举选的第一个点和之后的方向即可。

const int N = 107;
int n, ans;
ll ax, ay, bx, by, xs, ys, t, mx, my, x[N], y[N];

int main() {
    rd(x[0]), rd(y[0]), rd(ax), rd(ay), rd(bx), rd(by);
    rd(xs), rd(ys), rd(t), mx = xs + t, my = ys + t;
    while (x[n] <= mx && y[n] <= my)
        ++n, x[n] = x[n-1] * ax + bx, y[n] = y[n-1] * ay + by;
    for (int i = 0; i < n; i++)
        for (int j = -1; j <= 1; j += 2) {
            int cnt = 0, now = i;
            ll T = t;
            t -= abs(xs - x[i]) + abs(ys - y[i]);
            while (t >= 0) {
                ++cnt;
                now += j;
                if (now < 0 || now >= n) break;
                t -= abs(x[now-j] - x[now]) + abs(y[now-j] - y[now]);
            }
            ans = max(ans, cnt);
            t = T;
        }
    print(ans);
    return 0;
}

Xenon’s Attack on the Gangs

考虑 dp，设 $f_{i,j}$ 表示路径 $(i,j)$ 上的最大贡献，转移就是向两端各延伸一个点，类似于树上区间 dp，时间复杂度 $\mathcal O(n^2)$。

const int N = 3e3 + 7;
int n, fa[N], s[N], l[N], r[N], k, p[N];
vi e[N];
ll f[N][N], ans;

void dfs2(int x, int fa, int X, int Y) {
    for (auto y : e[x])
        if (y != fa) {
            f[y][X] = f[X][y] = max(f[X][x], f[Y][y]) + s[y] * (n - s[Y]);
            dfs2(y, x, X, Y);
        }
}

void dfs1(int x, int fa) {
    s[x] = 1, l[x] = ++k, p[k] = x;
    for (auto y : e[x])
        if (y != fa) {
            ::fa[y] = x;
            dfs1(y, x), s[x] += s[y];
            f[y][x] = f[x][y] = s[y] * (n - s[y]);
            dfs2(y, x, x, y);
        }
    r[x] = k;
    for (auto y : e[x])
        if (y != fa)
            for (auto z : e[x])
                if (z != fa && z != y)
                    for (int i = l[y]; i <= r[y]; i++)
                        for (int j = l[z]; j <= r[z]; j++)
                            f[p[i]][p[j]] = f[p[j]][p[i]] = max(f[p[i]][::fa[p[j]]], f[::fa[p[i]]][p[j]]) + s[p[i]] * s[p[j]];
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    dfs1(1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = max(ans, f[i][j]);
    print(ans);
    return 0;
}

Chaotic V.

本题其实很暴力。

主要思路就是，先将点数减小到 $n = 5 \times 10^3$。

假设答案为 $1$，然后每次往最大的子树走，如果答案能够更优则更新答案，否则输出答案即可。

考虑细节上的问题，第一点是，由于点数太大，图是无法显式建出来的。

如何隐式建图呢？

首先可以将 $1! \sim n!$ 的所有质因数以及幂次数都求出来，具体来说就是求出 $1 \sim n$ 的然后做一个前缀和即可。

然后对于每个 $i$ 建立一个指针 $p_i$ 指向 $i!$ 的最大质因数，特别地如果 $c_i$（即 $i$ 出现的次数）为零则最大质因数默认为 $1$。

那么每次往一棵子树走的时候，动态维护这个指针即可。

接下来考虑时间复杂度。

由于一个点的可重质因子个数是 $\mathcal O(\log n)$ 级别的，因此最多走 $\mathcal O(n \log n)$ 条边。

每走一条边需要均摊 $\mathcal O(n)$ 的时间维护。

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

const int N = 5e3 + 1;
int n, c[N], f[N][N], p[N], s[N];
ll ans, now;

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) rd(x), ++c[x];
    for (int i = 2; i < N; i++) {
        memcpy(f[i], f[i-1], sizeof(f[i]));
        for (int j = 2, k = i; j <= k; j++)
            while (k % j == 0) ++f[i][j], k /= j;
    }
    for (int i = 1; i < N; i++)
        if (!c[i]) p[i] = 1;
        else for (int j = 1; j <= i; j++)
            if (f[i][j]) p[i] = j, now += 1ll * f[i][j] * c[i];
    ans = now;
    while (*max_element(p + 1, p + N) > 1) {
        memset(s, 0, sizeof(s));
        for (int i = 0; i < N; i++) s[p[i]] += c[i];
        int o = max_element(s + 1, s + N) - s, w = s[o];
        if (w * 2 <= n || o == 1) break;
        ans = min(ans, now -= w * 2 - n);
        for (int i = 0; i < N; i++) {
            if (p[i] != o) p[i] = 1;
            if (p[i] == 1) continue;
            --f[i][p[i]];
            while (p[i] > 1 && !f[i][p[i]]) --p[i];
        }
    }
    print(ans);
    return 0;
}

Rin and The Unknown Flower

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

Nora’s Toy Boxes

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