Codeforces1917F - Construct Tree

Codeforces1917F - Construct Tree

Problems

给一个长度为 \(n\) 的序列 \(l\) 和 \(d\)。

要求判断是否可以构造出一颗节点数为 \(n+1\) 的树，满足 \(l\) 的每一个元素唯一对应为一条边的长度，并使整棵树的直径长度恰好为 \(d\)。

Solution

不妨令 \(l_1 \le l_2 \le \cdots \le l_n\)。

考虑必须要找出 \(l\) 的子集使得其和为 \(d\)。同时考虑如何构造出一棵可行的树。

把选出的部分 \(l'\) 展成一条链，可以发现如果最后满足答案，充要条件使存在一个点，使得所有未被选中的边都可以直接连在这个点上，且直径仍然为最初 \(l'\) 展出的链。

设这个点为 \(v'\)，链的两端分别为 \(v_1,v_2\)，发现满足条件当且仅当：

其中 \(e\) 为任意一条没有选中的边。

发现实际上可以直接动态规划。固定分界点，记录以上的两个值，考虑怎么转移。

有点说不清楚，对着代码讲吧。（出题人的实现很牛，照搬过来的）

bitset < D > f[D >> 1];
void Push (int x){
    for (int i = d >> 1;i >= 0;-- i){
        if (i + x <= (d >> 1))
            f[i + x] |= f[i];
        f[i] |= f[i] << x;
    } // 正常转移
}
void WORK (){
    f[0][0] = 1;
    int id = 1;
    for (int i = 1;i <= (d >> 1);++ i){ // 钦定前面一维的长度不会超过 d/2
        while (id <= n && ! (l[id] ^ i))
            Push (l[id]), id ++;
        res = 0;
        for (int j = id;j <= n;++ j)
            res += l[j];
        if (res <= d - i && f[i][d - i - res]){
            // 这里实际上在考虑前一维为 i 的情况，所以可以不需要先转移后面。
            // 小于等于 i 的边此时一定可以挂在分界点上，或者参与转移。
            // 大于 i 的边此时不能挂在分界点上，
            // 而固定前一维为 i ，所以大于 i 的边此时一定会挂在后一维的链上。
            // 通过 d 算另一维的大小，再减去还没有考虑转移的（就是大于 i 的）边的长度和，判断是否存在即可
            puts ("Yes");
            return ;
        }
    }
    puts ("No");
}

需要用 \(\textrm{bitset}\) 。

时间复杂度 \(O(\frac{nd^2}{w})\)。\(w\) 为 \(\textrm{bitset}\) 的位数。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, D = 2005;
bitset < D > f[D >> 1];
int T, n, d, sum, res, l[N];
void Push (int x){
    for (int i = d >> 1;i >= 0;-- i){
        if (i + x <= (d >> 1))
            f[i + x] |= f[i];
        f[i] |= f[i] << x;
    }
}
void WORK (){
    scanf ("%d%d", &n, &d);
    sum = 0;
    for (int i = 1;i <= n;++ i){
        scanf ("%d", &l[i]);
        sum += l[i];
    }
    if (sum == d){
        puts ("Yes");
        return ;
    }
    sort (l + 1, l + n + 1);
    for (int i = 0;i <= (d >> 1);++ i)
        for (int j = 0;j <= d;++ j)
            f[i][j] = 0;
    f[0][0] = 1;
    int id = 1;
    for (int i = 1;i <= (d >> 1);++ i){
        while (id <= n && ! (l[id] ^ i))
            Push (l[id]), id ++;
        res = 0;
        for (int j = id;j <= n;++ j)
            res += l[j];
        if (res <= d - i && f[i][d - i - res]){
            puts ("Yes");
            return ;
        }
    }
    puts ("No");
}
int main (){
    scanf ("%d", &T);
    while (T --)
        WORK ();
    return 0;
}