UOJ Logo gaolinxiang的博客

博客

陈太阳系列题解

2018-10-07 14:47:35 By gaolinxiang

因为两场比赛的 $\text{T1}$ 过水，所以不在此赘述。

全部赛区 Day 1

出题人：$\text{fizzydavid}$。

陈太阳与路径

给定一棵树，求每个点是几条简单路径的中点。树形态随机，$n \le 5 \times 10^5$。

分析

对于此题，只需对于每个点，求出距离它为 $k\ (0\le k \lt n)$ 的点分别有多少个就可以计算答案了。

有两个性质：

  • 随机树的期望平均深度为 $\Theta(\log n)$。
  • 随机树的期望最大深度为 $\Theta(\sqrt n)$。

我们令 $dp1[i][j]$ 表示以结点 $1$ 为根 $i$ 点的子树下距离 $i$ 点为 $j$ 的点的个数。转移十分显然，我们可以用一遍 $\text{DFS}$ 求出它。对于每个结点，$dp1[i][j]\ (j > dep[i])$ 是没有意义的，我们可以以此来压缩时间和空间。具体实现时可以使用 std::vector 以减少空间复杂度。

我们令 $dp2[i][j]$ 表示结点 $i$ 往上走 $j$ 步可能到达的点的数量。这样我们可以再用一遍 $\text{DFS}$ 使用 $dp1$ 求出它。但是发现这样的空间复杂度过大。其实对于此题只需记录一条根到结点的路径上的所有 $dp2$，并在 $\text{DP}$ 过程中计算答案即可。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 5e5 + 5, maxm = 1e6 + 5;
long long ans[maxn];
int n, d[maxn];
int tot, ter[maxm], nxt[maxm], lnk[maxn];
vector<int> dp1[maxn], dp2[maxn];

void addEdge(int u, int v) {
    ter[++tot] = v;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
}

void dfs1(int u, int p) {
    d[u] = 1;
    dp1[u].resize(d[u]);
    dp1[u][0] = 1;
    for (int i = lnk[u], v; i; i = nxt[i]) {
        v = ter[i];
        if (v == p) continue;
        dfs1(v, u);
        d[u] = max(d[u], d[v] + 1);
        dp1[u].resize(d[u]);
        for (int j = 0; j < d[v]; j++) {
            dp1[u][j + 1] += dp1[v][j];
            ans[u] -= 1ll * dp1[v][j] * (dp1[v][j] + 1) / 2;
        }
    }
    for (int i = 0; i < d[u]; i++) {
        ans[u] += 1ll * dp1[u][i] * (dp1[u][i] + 1) / 2;
    }
}

void dfs2(int u, int p, int x) {
    for (int i = 1; i < d[u] && i < dp2[x].size(); i++) {
        ans[u] += 1ll * dp1[u][i] * dp2[x][i];
    }
    for (int i = lnk[u], v; i; i = nxt[i]) {
        v = ter[i];
        if (v == p) continue;
        dp2[x + 1].resize(d[v] + 1);
        dp2[x + 1][1] = 1;
        for (int j = 1; j < d[v]; j++) {
            dp2[x + 1][j + 1] = (j < dp2[x].size() ? dp2[x][j] : 0) + dp1[u][j] - dp1[v][j - 1];
        }
        dfs2(v, u, x + 1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    for (int i = 1; i <= n; i++) {
        printf("%lld%c", ans[i], " \n"[i == n]);
    }
    return 0;
}

陈太阳与开关

给定一棵 $n$ 个结点的树，求有多少个集合，使得在集合中的点连出的边的存在性取反后新生成的图联通。

分析

发现不联通的情况很少。考虑计算不联通的情况。

称集合中出现的点为白点，集合中未出现的点为黑点。

如果有相邻的两个点同色，不妨设他们是黑点。发现所有白点与这两个点联通（他们与这两个点中至少一个不相邻）。我们现在只需考虑是否有黑点与这两个点不联通。

发现一个黑点与这两个点不联通当且仅当所有白色的点围住了它，不然的话他一定可以与某个白色点联通。我们称这种点为孤立点。那么这种情况下联通的充要条件就是不存在孤立点。枚举孤立点后特判去重即可。

当没有相邻两个点同色时，直接模拟两种情况并用并查集优化。也可以采用 $\text{\_rqy}$ 神仙的做法：还是使用枚举孤立点的方法。发现只有一种反例：

          O----------O
         / \        / \
        /   \      /   \
       /     \    /     \
      +-------+  +-------+

特判掉即可。

当然，对于小规模的数据也需要特判，否则会被直接卡到 $50$ 分。

代码

$\%\%\%$ 神仙 $\text{\_rqy}\ !$

#include <cstdio>

const int maxn = 1e5 + 5, maxm = 2e5 + 5, mod = 1e9 + 7;
int T, n, m, a[maxn], u[maxn], v[maxn];
int tot, ter[maxm], nxt[maxm], lnk[maxn], deg[maxn];
int bin[maxn], vis[maxn];

void addEdge(int u, int v) {
    ter[++tot] = v;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
    deg[u]++;
}

bool check() {
    for (int i = 1; i < n; i++) {
        if (deg[u[i]] == 2 && deg[v[i]] == 2) {
            int a = 0, b = 0;
            for (int j = lnk[u[i]]; j; j = nxt[j]) {
                if (ter[j] != v[i]) {
                    a = ter[j];
                    break;
                }
            }
            for (int j = lnk[v[i]]; j; j = nxt[j]) {
                if (ter[j] != u[i]) {
                    b = ter[j];
                    break;
                }
            }
            if (deg[a] + deg[b] == n - 2 && deg[a] >= 2 && deg[b] >= 2) {
                return 1;
            }
        }
    }
    return 0;
}

int solve() {
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            ans += !vis[ter[lnk[i]]];
            vis[ter[lnk[i]]] = 1;
        } else {
            ans++;
        }
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    bin[0] = 1;
    for (int i = 1; i <= 1e5; i++) {
        bin[i] = bin[i - 1] + bin[i - 1];
        bin[i] < mod ? NULL : bin[i] -= mod;
    }
    while (T--) {
        scanf("%d", &n);
        tot = 0;
        for (int i = 1; i <= n; i++) {
            lnk[i] = deg[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u[i], &v[i]);
            addEdge(u[i], v[i]), addEdge(v[i], u[i]);
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 1) {
                cnt++;
            }
        }
        if (n == 1 || n == 2) {
            puts("2");
        } else if (cnt == n - 1) {
            printf("%d\n", (bin[n] - 2 + mod) % mod);
        } else if (cnt == n - 2) {
            printf("%d\n", (bin[n] - 6 + mod) % mod);
        } else if (check()) {
            printf("%d\n", (bin[n] - 14 + mod) % mod);
        } else {
            printf("%d\n", (bin[n] - 2 * solve() + mod) % mod);
        }
    }
    return 0;
}

青岛赛区 Day 2

出题人：$\text{apiadu}$。

陈太阳与直径

求 $n$ 个点的带标号树直径长度为 $0, 1, 2, \cdots, n-1$ 的个数 $\text{mod }m$ 的结果。$m$ 是素数，$n \le 500$。

分析

令 $f_{i, j}$ 表示 $i$ 个点的带标号树，深度 $\le j$ 的有多少个。转移方程如下：

$$f_{i, j} = i \times \sum_{k = 1}^{i - 1} {\binom{i - 2}{k - 1} \times f_{k, j - 1} \times \dfrac{f_{i - k, j}}{i - k}}$$

解释：将一棵结点数为 $k$ 的树接到一棵结点数为 $i - k$ 的树的根结点下面。要 $\div (i - k)$ 是因为那棵结点数为 $i - k$ 的树的根结点是确定的，乘的组合数是将除了两棵树的根结点以外的两棵树中的结点按照相对顺序排列的方案数。

令 $f_{i, j}$ 表示 $i$ 个点的带标号树，深度 $= j$ 的有多少个。显然，$g_{i, j} = f_{i, j} - f_{i, j - 1}$。

考虑如何计算答案。当树的直径长度为 $2k+1$，则树的中心为一条边。他两边连接的两棵子树的深度为 $k$。于是答案为：

$$\sum_{j = 1}^{n - 1} {\binom{n - 1}{j - 1} \times g_{j, k} \times g_{n - j, k}}$$

当树的直径长度为 $2k$，则树的中心为一个点。于是深度 $k$ 出现了至少两次。此时答案为：

$$g_{n, k} - \sum_{j = 1} ^ {n - 1} \binom{n}{j} \times f_{j, k - 1} \times f_{n - j,k - 1}$$

即所有深度为 $k$ 的树减去深度 $k$ 只出现了一次的树。

注意在 $n$ 较小时进行特判。时间复杂度 $\Theta(n ^ 3)$。（好像可以 $\text{FFT}$ ？）

代码

第一份是 $90$ 分代码。它较为容易理解，但是常数较大。

#include <cstdio>

const int maxn = 505;
int n, mod, inv[maxn], a[maxn], c[maxn][maxn];
int f[maxn][maxn], g[maxn][maxn], d[maxn][maxn];

int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) {
        if (b & 1) {
            c = 1ll * a * c % mod;
        }
    }
    return c;
}

int main() {
    scanf("%d %d", &n, &mod);
    if (n == 1) {
        return puts("1"), 0;
    } else if (n == 2) {
        return puts("0 1"), 0;
    }
    for (int i = 0; i <= n; i++) {
        inv[i] = qpow(i, mod - 2);
    }
    for (int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            c[i][j] < mod ? NULL : c[i][j] -= mod;
        }
    }
    d[1][0] = 1;
    for (int i = 0; i <= n; i++) {
        f[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            for (int k = 0; k < i; k++) {
                f[i][j] = (f[i][j] + 1ll * f[k][j - 1] * f[i - k][j] % mod * inv[i - k] % mod * c[i - 2][k - 1]) % mod;
            }
            f[i][j] = 1ll * i * f[i][j] % mod;
            d[i][j] = f[i][j] - f[i][j - 1];
            d[i][j] < 0 ? d[i][j] += mod : NULL;
            for (int j = i; j <= n; j++) {
                f[i][j] = f[i][i - 1];
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (i & 1) {
            for (int j = 1; j < n; j++) {
                a[i] = (a[i] + 1ll * d[j][i / 2] * d[n - j][i / 2] % mod * c[n - 1][j - 1]) % mod;
            }
        } else {
            a[i] = d[n][i / 2];
            for (int j = 1; j < n; j++) {
                a[i] = (a[i] + mod - 1ll * d[j][i / 2 - 1] * f[n - j][i / 2 - 1] % mod * c[n][j] % mod) % mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], " \n"[i == n - 1]);
    }
    return 0;
}

第二份是 $\text{AC}$ 代码。加了一些小优化。

#include <cstdio>

const int maxn = 505;
int n, mod, inv[maxn], a[maxn], c[maxn][maxn];
int f[maxn][maxn], d[maxn][maxn];
long long g[maxn][maxn];

int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) {
        if (b & 1) {
            c = 1ll * a * c % mod;
        }
    }
    return c;
}

int main() {
    scanf("%d %d", &n, &mod);
    long long inf = 5000000000000000000ll / mod * mod;
    if (n == 1) {
        return puts("1"), 0;
    } else if (n == 2) {
        return puts("0 1"), 0;
    }
    for (int i = 1; i <= n; i++) {
        inv[i] = qpow(i, mod - 2);
    }
    for (int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            c[i][j] < mod ? NULL : c[i][j] -= mod;
        }
    }
    d[1][0] = 1;
    for (int i = 0; i <= n; i++) {
        f[1][i] = g[1][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            for (int k = 0; k < i; k++) {
                g[i][j] += 1ll * f[k][j - 1] * g[i - k][j] % mod * c[i - 2][k - 1];
                if (g[i][j] >= inf) g[i][j] -= inf;
            }
            g[i][j] %= mod;
            f[i][j] = 1ll * i * g[i][j] % mod;
            d[i][j] = f[i][j] - f[i][j - 1];
            d[i][j] < 0 ? d[i][j] += mod : NULL;
            for (int j = i; j <= n; j++) {
                f[i][j] = f[i][i - 1];
                g[i][j] = g[i][i - 1];
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (i & 1) {
            for (int j = 1; j < n; j++) {
                a[i] = (a[i] + 1ll * d[j][i / 2] * d[n - j][i / 2] % mod * c[n - 1][j - 1]) % mod;
            }
        } else {
            a[i] = d[n][i / 2];
            for (int j = 1; j < n; j++) {
                a[i] = (a[i] + mod - 1ll * d[j][i / 2 - 1] * f[n - j][i / 2 - 1] % mod * c[n][j] % mod) % mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], " \n"[i == n - 1]);
    }
    return 0;
}

陈太阳与酒店

原来的题意太长了，请自行看题。

题意可以转化为：给定一个点带权的二分图，左侧有 $n$ 个点，权值为 $a_1, a_2, a_3, \cdots, a_n$，右侧有 $m$ 个点，权值为 $b_1, b_2, b_3, \cdots, b_m$。左侧第 $i$ 个点向右侧第 $j$ 个点连边当且仅当 $l_i \le j \le r_i$。求它的一个独立集，使得不在独立集中的点权值的平均值最大。题意的转化过程请读者自行思考。

分析

首先想到 $01$ 分数规划（二分答案）。二分 $x$，使每个点的权值 $- x$。我们要求新图中的最小独立集。为了方便起见，我们把每个点的权值取反，这样只需计算最大独立集。

考虑 $\text{DP}$。令 $dp_i$ 表示考虑到右侧第 $i$ 个点的最大权值和。我们发现对于左边的点 $k$，如果右侧的点中区间 $[l_k, r_k]$ 都没被选，则它就可以被选。预处理出 $f_{x, y}$ 表示如果右侧的点中区间 $[x, y]$ 都没被选那么左边的点中能选到的最大权值和为多少。这样 $dp_{i} = b_i + \max_{j = 0}^{i - 1} {dp_j + f_{j + 1, i - 1}}$。于是我们就得到了一个 $\Theta(n^2)$ 的算法。

考虑使用线段树优化这个算法。当 $\text{DP}$ 完右侧第 $i$ 个点时，我们把所有 $r_j = i$ 的左侧第 $j$ 个点添加到线段树中。因为 $dp_0, dp_1, dp_2, \cdots, dp_{l_j - 1}$ 转移到 $dp_{i + 1}, dp_{i + 2}, \cdots, dp_{m}$ 都要加上左侧第 $j$ 个点的权值，所以我们给线段树的 $[0, l_j)$ 加上 $a_j$。$dp_i$ 的值可通过查询线段树上 $[0, i - 1]$ 的获取。于是我们就得到了一个 $\Theta(n\log_2n)$ 的做法。

代码

首次尝试了用整形变量实现 $01$ 分数规划。这样可以有效避免精度问题并提高运算效率。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define lson (root << 1)
#define rson (lson | 1)
#define mid ((l + r) >> 1)
const int maxn = 30005;
const int maxm = 66666;
const long long mult = 1000000;
int n, m, a[maxn], b[maxn], l[maxn], r[maxn];
vector<int> v[maxn];
long long A[maxn], B[maxn];
long long mx[maxm], tag[maxm];

void update(int root) {
    mx[root] = max(mx[lson], mx[rson]);
}

void build(int root, int l, int r) {
    tag[root] = 0;
    if (l == r) {
        mx[root] = 0;
        return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    update(root);
}

void pushDown(int root) {
    if (tag[root]) {
        mx[lson] += tag[root];
        tag[lson] += tag[root];
        mx[rson] += tag[root];
        tag[rson] += tag[root];
        tag[root] = 0;
    }
}

void modify(int root, int l, int r, int lx, int rx, long long d) {
    if (l == lx && rx == r) {
        mx[root] += d;
        tag[root] += d;
        return;
    }
    pushDown(root);
    if (rx <= mid) {
        modify(lson, l, mid, lx, rx, d);
    } else if (lx > mid) {
        modify(rson, mid + 1, r, lx, rx, d);
    } else {
        modify(lson, l, mid, lx, mid, d);
        modify(rson, mid + 1, r, mid + 1, rx, d);
    }
    update(root);
}

long long query(int root, int l, int r, int lx, int rx) {
    if (l == lx && rx == r) {
        return mx[root];
    }
    pushDown(root);
    if (rx <= mid) {
        return query(lson, l, mid, lx, rx);
    } else if (lx > mid) {
        return query(rson, mid + 1, r, lx, rx);
    } else {
        return max(query(lson, l, mid, lx, mid), query(rson, mid + 1, r, mid + 1, rx));
    }
}

long long solve(long long x) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += 1ll * mult * a[i] - x;
        A[i] = max(0ll, x - 1ll * mult * a[i]);
    }
    for (int i = 1; i <= m; i++) {
        sum += 1ll * mult * b[i] - x;
        B[i] = max(0ll, x - 1ll * mult * b[i]);
    }
    build(1, 0, m);

    for (int i = 1; i <= m; i++) {
        long long x = query(1, 0, m, 0, i - 1) + B[i];
        modify(1, 0, m, i, i, x);
        for (int j = 0; j < v[i].size(); j++) {
            modify(1, 0, m, 0, l[v[i][j]] - 1, A[v[i][j]]);
        }
    }
    return sum + query(1, 0, m, 0, m);
}

int main() {
    scanf("%d %d %*d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &l[i], &r[i]);
        v[r[i]].push_back(i);
    }
    long long L = 0, R = 100000 * mult, M;
    while (L < R) {
        M = (L + R + 1) >> 1;
        if (solve(M) >= 0) {
            L = M;
        } else {
            R = M - 1;
        }
    }
    printf("%lld.%06lld\n", L / mult, L % mult);
    return 0;
}

评论

wujinzhao
您太强了
  • 2018-10-07 20:36:08
apiadu
您太强了
  • 2018-10-08 09:10:53
zhengruioi
您太强了
  • 2018-10-08 21:54:37
siyuan
您太强了
  • 2018-10-09 20:41:19
l___z___t
您太强了
  • 2018-10-10 07:27:43
hepan
您太强了
  • 2018-10-10 12:28:00
Sanada_Masayuki
您太强了
  • 2018-10-11 11:41:22
gaolinxiang
—————————— 复读终止线 ——————————
  • 2018-10-11 11:59:47
teddyxu
您实在是太强了
  • 2018-10-11 20:37:15
larryzhong
您确实是太强了
  • 2018-10-12 23:40:53
wph
您是真的强，感谢您的题解
  • 2018-10-16 08:07:01
liukaiyuan
您是真的强，感谢您的题解
  • 2018-10-19 20:10:28
tyf
您是真的强，感谢您的题解
  • 2018-10-22 08:09:27
gyfer
您是真的强，感谢您的题解
  • 2018-10-22 23:55:16
wangzhilue
您是真的强，感谢您的题解
  • 2018-10-25 22:22:34
hepan
您是真的强，感谢您的题解
  • 2018-10-26 14:30:15

中文 English

Server time: 2024-04-26 00:03:33   |   浙ICP备17047493号