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\)，发现满足条件当且仅当：
\[\max\{\mathrm{distance}(v',v_1),\mathrm{distance}(v',v_2)\} + l_e\le d
\]
其中 \(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;
}