「csp校内训练 2019-11-06」解题报告

T1、华中

$Description$：

严先生是华中科技大学的大一新生。
体育选课了，严先生作为幸运 Ex 的联创人才，选上了「户外运动」这门课。

严先生第一次课的内容是“定向越野”。
具体来说是这样的:校园内共有 $n$ 个检查点，他们之间有 $n - 1$ 条路径相连。
换句话说，检查点之间构成了一棵树。

为了让事情更有趣一点，严先生将这些检查点划分为两种，权值分别为 $0$ 和 $1$；
但是学校有打卡规定，在一次越野之后，经过的所有检查点的权值异或和必须为 $0$。

严先生的越野方案是这样的：从某一个检查点开始，不经过重复的检查点，随机的选择一个与当前检查点有路径相连的检查点，直到走到无路可走，这算完成一次定向越野。
但是严先生是联创团队 lab 组的优秀人才，严先生可以随意钦点每一个检查点的权值。
也就是说，严先生会让每一个点轮流做一次根节点，你需要让根节点到每一个叶子节点的路径权值异或和都为 $0$ ，这就是一个合法的方案。
现在严先生想知道,总共有多少种合法的方案。输出结果对 $ 10^9 + 7 $ 取模。

$ 1 \leq n \leq 10^6 $。

$Solution$：

先考虑 $dp$，$f_u$ 表示 $u$ 为根的子树中的叶子节点到 $u$ 的异或和相等的方案数；
显然有 $f_u = 2 \prod f_v$，对于叶子有 $f_u = 1$。
直接 $dp$ 换根即可。

由上面不难看出，每个非叶结点会对答案有 $\times 2$ 的贡献；
设有 $k$ 个叶子，考虑根是否为叶子，$ans = (n - k) 2 ^ {n - k} + k \ 2 ^ {n - k + 1}$。

$Source$：

太占位置，不贴了。

T2、科技

题目链接

$Description$：

杨先生是另一名华中科技大学的大一新生。
与严先生一样，杨先生也是一名联创团队的优秀人才。作为 Web 组的新人，杨先生正在研究服务器的问题。

杨先生发现，团队内部总共有 $n$ 台服务器，通过 $n - 1$ 条数据链路进行连接。换句话说，服务器链接成了一个树的形状。每台服务器分配的任务不一样，因此第 $i$ 台服务器有一个权值 $v_i$，用于描述服务器的重要程度。

现在杨先生正在进行熬夜测试，他的任务是给每一个服务器确定一个负载值 $w_i$ ($w_i \leq 1$) 和一个颜色 (黑或者白)，使得对于每一个节点 $u$，它的子树内的和它同色的节点负载值之和（包括它本身）与它的权值相等。

杨先生想知道熬夜测试的出题人有没有在刁难他，因此你需要告诉杨先生是否存在这么一个方案。如果存在输出"ICHOOSEUNIQUE"，不存在输出"ICHOOSEBINGYAN"（均不含引号）。
当然啦，为了防止你骗分，杨先生对本题采用捆绑测试。

$n \leq 1000 , v_i \leq 5000$。

$Solution$：

考虑一棵 $u$ 为根的子树，当然希望子树里和 $u$ 异色的负载和最小；
$f_{u}$ 表示 $u$ 的子树中，与 $u$ 异色点负载和的最小值。
$dp$ 即可。
$g_{i, j}$ 表示 $u$ 的前 $i$ 个子树与 $u$ 同色点的负载和为 $j$ 的最小异色负载和。
转移讨论某个儿子与 $u$ 是否异色即可：
\[g_{i,j} = \min\begin{cases}\min \{g_{i, j - val_v} + f_v\}\\\\\min \{g_{i, j - f_v} + val_v\}\\\end{cases} \\\\f_{u} = \min_{j = 0}^{val_u} \{g_{k, j}\}\]

$Source$：

#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' || c > '9')
        f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }

const int N = 1e3 + 5, M = 5e3 + 5, inf = 0x3f3f3f3f;

struct edge {
    int next, to;
} e[N << 1];
int ecnt = 1, head[N];
int n, val[N];
int f[M];

void add_edge(const int u, const int v) {
    e[++ecnt] = (edge){head[u], v}, head[u] = ecnt;
}

int t[M], s[M];
void dfs(const int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
    }
    memset(s, inf, sizeof(s));
    s[0] = 0;
    for (int i = head[u]; i; i = e[i].next) {
        memset(t, inf, sizeof(t));
        int v = e[i].to;
        for (int j = val[u]; j >= 0; --j) {
            if (j >= val[v])
                chk_min(t[j], s[j - val[v]] + f[v]);
            if (j >= f[v])
                chk_min(t[j], s[j - f[v]] + val[v]);
        }
        std::swap(s, t);
    }
    for (int j = val[u]; j >= 0; --j)
        chk_min(f[u], s[j]);
}

int main() {
    //freopen("in", "r", stdin);
    freopen("sciandtech.in", "r", stdin);
    freopen("sciandtech.out", "w", stdout);
    n = in();
    for (int i = 2, fa; i <= n; ++i) {
        fa = in();
        add_edge(fa, i);
    }
    for (int i = 1; i <= n; ++i)
        val[i] = in();
    memset(f, inf, sizeof(f));
    dfs(1);
    puts((f[1] < inf) ? "ICHOOSEUNIQUE" : "ICHOOSEBINGYAN");
    return 0;
}

T3、大学

题目链接

$Description$：

鸡先生也是一名华中科技大学的大一新生。
和大家预想的不太一样的是，鸡先生并没有加入联创团队，也不喜欢唱跳和球。

鸡先生正在准备冰岩作坊游戏组的实习任务，他现在遇到了一个棘手的问题。
鸡先生要构造出一个地图种子，具体来说，这是一个长度为 $n$ 的 $01$ 串。然而鸡先生想要构造出更多的地图种子，因此鸡先生给出了 $m$ 个区间 $[L_i,R_i]$ ，鸡先生可以对区间内的数进行重排。
每个区间只能操作一次，并且区间操作需要按照顺序依次进行。
对 $m$ 个区间内的数全部重排之后，鸡先生想知道，这样可以得到多少个不同的 $01$ 串？

为了方便你处理，鸡先生向你保证，这些区间的 $L_i$ 是单调不降的，即保证了 $L_i\leq L_{i+1}$ 。
由于答案有点大，因此你需要对 $10^9+7$ （一个质数）取模。

$1\leq n,m \leq 2000$。

$Solution$：

$0,1$ 是对偶的，不妨只关注 $1$ 。

重新理解一下重排：
题目要求重排，不妨不去思考如何将区间内的 $0,1$ 进行分配，考虑每个位置放什么数。

不难想到一个 $dp$：
$f_{i,j}$ 表示前 $i$ 个位置，放了 $j$ 个 $1$ 的方案数，但此时能用的 $1$ 是 $r_i$ 之前的所有 $1$。
(其中 $r_i$ 表示覆盖到 $i$ 的最靠右的右端点)。
为了方便处理边界，假设每个未被覆盖的位置都是长度为 $1$ 的重排区间。

$Source$：

#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' || c > '9')
        f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }

const int N = 2005, mod = 1e9 + 7;

inline void add(int &_, int __) {
    _ += __;
    if (_ >= mod)
        _ -= mod;
}

int n, m, r[N];
int f[N][N], pre[N];
char s[N];

int main() {
    //freopen("in", "r", stdin);
    freopen("university.in", "r", stdin);
    freopen("university.out", "w", stdout);
    n = in(), m = in();
    scanf(" %s", s + 1);
    for (int i = 1; i <= n; ++i)
        r[i] = i, pre[i] = pre[i - 1] + (s[i] == '1');
    for (int i = 1; i <= m; ++i) {
        int x = in(), y = in();
        for (int j = x; j <= y; ++j)
            chk_max(r[j], y);
    }
    f[0][0] = 1;
    for (int i = 1, cur = 1; i <= n; ++i, cur ^= 1) {
        memset(f[cur], 0, sizeof(f[cur]));
        for (int j = 0; j <= i && j <= pre[r[i]]; ++j) {
            if (pre[r[i]] - j > r[i] - i)
                continue;
            f[cur][j] = f[cur ^ 1][j];
            if (j) {
                add(f[cur][j], f[cur ^ 1][j - 1]);
            }
        }
    }
    printf("%d\n", f[n & 1][pre[n]]);
    return 0;
}

先生