CWOI 3-28 测试题解与总结

240 pts, 100 + 100 + 40, rk 2

不会 T3 自闭了

难度大概是三道 PJ T3 + PJ T2 + PJ T3？

我菜死了

A. 积木

有 n 个可以调换三个元素顺序的三元组，第 i 个为 (a_i, b_i, c_i)。现拿出若干个三元组并按照一定顺序，满足：a_{i + 1} \leq a_i, b_{i + 1} \leq b_i，试求最大化后的 \sum c_i。

n \leq 15

一种方案之后的扩展只和最上面有关。

则我们记 f(S, i, 0/1/2) 表示用了集合 S 中的积木，最上面的积木编号是 i，放置顺序是 i 的 0/1/2 阶置换。

dp 明显，枚举状态，枚举下一个积木。

注意判断可行时，不仅是考虑置换，还要考虑对换。

时间复杂度 O(2^nn^2)

#include <bits/stdc++.h>
#define in(S, i) (S & (1 << (i - 1)))
using namespace std;

typedef long long ll;

const int MAXN = 15 + 10, MAXSTATUS = (1 << 15) + 10;
int n, arr[MAXN][3];
ll f[MAXSTATUS][MAXN][3], ans;

void chkmax(ll& a, ll b) { if (a < b) a = b; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) for (int _ = 0; _ < 3; ++_) scanf("%d", &arr[i][_]);
    int MAXS = (1 << n) - 1;
    for (int i = 1; i <= n; ++i) {
        for (int _ = 0; _ < 3; ++_) {
            f[1 << (i - 1)][i][_] = arr[i][(_ + 2) % 3];
        }
    }
    for (int S = 0; S <= MAXS; ++S) {
        for (int i = 1; i <= n; ++i) {
            if (!in(S, i)) continue;
            for (int j = 1; j <= n; ++j) {
                if (in(S, j)) continue;
                for (int _ = 0; _ < 3; ++_) {
                    for (int __ = 0; __ < 3; ++__) {
                        if ((arr[i][_ % 3] >= arr[j][__ % 3] && arr[i][(_ + 1) % 3] >= arr[j][(__ + 1) % 3]) || (arr[i][_ % 3] >= arr[j][(__ + 1) % 3] && arr[i][(_ + 1) % 3] >= arr[j][__ % 3])) {
                            chkmax(f[S | (1 << (j - 1))][j][__], f[S][i][_] + arr[j][(__ + 2) % 3]);
                        }
                    }
                }
            }
        }
    }
    for (int S = 0; S <= MAXS; ++S) {
        for (int i = 1; i <= n; ++i) {
            for (int _ = 0; _ < 3; ++_) chkmax(ans, f[S][i][_]);
        }
    }
    printf("%lld", ans);
    return 0;
}

B. 快速荷叶叶变换

求

整除分块。

时间复杂度 O(\sqrt n)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int P = 1e9 + 7;
ll n, m, sum, ans;

void add(ll& a, ll b) { a = (a + b) % P; }

int main() {
    scanf("%lld %lld", &n, &m);
    for (ll l = 1; l <= m; ) {
        ll r = min(m / (m / l), m);
        ll val = m / l;
        add(sum, (1ll * (r - l + 1) * m - 1ll * val * (l + r) * (r - l + 1) / 2) % P);
        l = r + 1;
    }
    for (ll l = 1; l <= n; ) {
        ll r = min(n / (n / l), n);
        ll val = n / l;
        ans = (ans + 1ll * (1ll * (r - l + 1) * n - 1ll * val * (l + r) * (r - l + 1) / 2) % P * sum % P) % P;
        l = r + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

C. 树上摩托

给出一棵树，求断边方案数，使得断边后各连通块大小相同。

n \leq 10^6

显然各连通块仍是树。

显然各新树大小为 n 的因数。

且当固定大小之后，断边的方式是唯一确定的。

考虑一种合法的方案，最终是 \dfrac{n}{k} 个大小为 k 的子树。则原树就是在这些子树中连上若干条边形成的树。则我们看是否有 \dfrac{n}{k} 个节点的子树大小为 k 的倍数即可。

时间复杂度 O(d(n)n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int n, sz[MAXN];
vector<int> e[MAXN];

void dfs(int u, int fa) {
    sz[u] = 1;
    for (auto v : e[u]) if (v != fa) {
        dfs(v, u), sz[u] += sz[v];
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs(1, 0);
    int ans = 0;
    for (int k = 1; k <= n; ++k) {
        if (n % k == 0) {
            int cnt = 0;
            for (int i = 1; i <= n; ++i) {
                if (sz[i] % k == 0) cnt ++;
            }
            if (cnt == n / k) ans ++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

总结

好

• AB 切出来了
• C 暴力写出来了