Visits: 238

Codeforces Round #635 (Div. 1)

Linova and Kingdom

设深度为 $d$，子树大小为 $s$，点 $i$ 对答案的贡献为 $d_i – s_i + 1$，从大到小贪心就好了。

const int N = 2e5 + 7;
int n, k, d[N], s[N];
vi e[N];
ll ans;
pq<pi> q;

void dfs(int x, int f) {
    s[x] = 1;
    for (int y : e[x])
        if (y != f) {
            d[y] = d[x] + 1;
            dfs(y, x);
            s[x] += s[y];
            q.push(mp(d[y] - s[y] + 1, y));
        }
}

int main() {
    rd(n, k);
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    dfs(1, 0);
    while (k--) {
        ans += q.top().fi;
        q.pop();
    }
    print(ans);
    return 0;
}

Xenia and Colorful Gems

乱搞，让三个数尽可能接近就行了。

const int N = 1e5 + 7;
int x, y, z;
ll a[N], b[N], c[N], ans;

inline void upd(ll x, ll y, ll z) {
    ans = min(ans, (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x));
}

inline void work(ll *a, int x, ll *b, int y, ll *c, int z) {
    for (int i = 1, j, k; i <= x; i++) {
        j = lower_bound(b + 1, b + y + 1, a[i]) - b;
        if (j <= y) {
            k = lower_bound(c + 1, c + z + 1, (a[i] + b[j]) >> 1) - c;
            if (k <= z) upd(a[i], b[j], c[k]);
            if (k > 1) upd(a[i], b[j], c[k-1]);
        }
        if (j > 1) {
            k = lower_bound(c + 1, c + z + 1, (a[i] + b[j-1]) >> 1) - c;
            if (k <= z) upd(a[i], b[j-1], c[k]);
            if (k > 1) upd(a[i], b[j-1], c[k-1]);
        }
    }
}

inline void solve() {
    rd(x, y, z), rda(a, x), rda(b, y), rda(c, z);
    sort(a + 1, a + x + 1);
    sort(b + 1, b + y + 1);
    sort(c + 1, c + z + 1);
    ans = 4e18;
    work(a, x, b, y, c, z);
    work(b, y, c, z, a, x);
    work(c, z, a, x, b, y);
    print(ans);
}

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

Kaavi and Magic Spell

正着比较难考虑，反着就容易了。

设 $f_{i,j}$ 表示考虑 $s^r$ 的前 $i$ 个字符，覆盖了要求目标字符串的前 $j$ 个字符和后 $i-j$ 个字符的方案数。

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

const int N = 3e3 + 7;
int n, m;
char s[N], t[N];
modint f[N][N], ans;

int main() {
    rds(s, n), rds(t, m);
    reverse(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) {
        if (n - i + 1 >= m) f[i-1][0] += 1;
        for (int j = 0; j < i; j++) {
            if (s[i] == t[j+1] || !t[j+1]) f[i][j+1] += f[i-1][j];
            if (s[i] == t[n-i+1+j] || !t[n-i+1+j]) f[i][j] += f[i-1][j];
        }
    }
    for (int j = 0; j <= n; j++) ans += f[n][j];
    print(ans);
    return 0;
}

Yui and Mahjong Set

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

Chiori and Doll Picking

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

Journey

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