题解-CF429C Guess the Tree

题面

CF429C Guess the Tree

给一个长度为 \(n\) 的数组 \(a_i\)，问是否有一棵树，每个节点要么是叶子要么至少有两个儿子，而且 \(i\) 号点的子树大小是 \(a_i\)。

数据范围：\(1\le n\le 24\)。

题解

发现 \(n\) 很小，想到可以状压。

设叶子节点有 \(ln\) 个，所以中间节点有 \(mn=n-ln\) 个。

由于“每个节点要么是叶子要么至少有两个儿子”，所以 \(ln\ge\lceil\frac n2\rceil\)，\(mn\le n-\lceil\frac n2\rceil \le 11\)。

所以可以先特判 \(2mn\ge n\) 的情况答案为 NO。

然后剩下的可以 dp，设 \(f_{t,s,i}\)：

\(t\) 表示是一棵森林还是一个子树（为了对付“每个节点要么是叶子要么至少有两个儿子”，如果是子树 \(t=0\)，否则 \(t=1\)）。

\(s\) 表示包含的中间节点集合，\(s< 2^{mn}\le 2048\)。

\(i\) 表示包含的叶子节点个树，因为叶子节点都是一样的，所以这样可以优化状压。

值表示是否存在这样的森林，如果存在 \(=1\)，否则 \(=0\)。

考虑怎么转移：

一棵森林（子树）和另一棵森林（子树）合并成新的森林。
一棵森林上面加一个 \(a=\) 森林大小 \(+1\) 的节点成为一棵子树（怎么求一棵森林的大小？其实就是 \({\rm popcount}(s)+i\) 啦）。

然后就剩初始化的问题了，因为 \(i\) 这维就像一个背包，而且因为 \(s\) 这一维保证不会有重点，所以可以在 dp 中用无限背包的方式，这样就只需要初始化 \(f_{0,0,1}=1\) 了。

时间复杂度 \(\Theta(ln^2 3^{mn})\)，细节看代码。

代码

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair((a),(b))

#define x first

#define y second

#define bg begin()

#define ed end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

#define R(i,a,b) for(int i=(a),i##E=(b);i<i##E;i++)

#define L(i,a,b) for(int i=(b)-1,i##E=(a)-1;i>i##E;i--)

const int iinf=0x3f3f3f3f;

const ll linf=0x3f3f3f3f3f3f3f3f;

//Data

const int N=24,mN=11;

int n,sn,ln,mn,a[N],b[1<<mN];

int f[2][1<<mN][N+1]; // 森林还是子树，中间节点集，叶子节点数

bool get(int s,int i){ // 返回 f[1][s][i] 的值

    for(int su=s;su;su=s&(su-1))if(!(su&(s^su)))R(j,0,i+1)

        if((f[0][su][j]||f[1][su][j])&&(f[0][s^su][i-j]||f[1][s^su][i-j])) return true;

    R(j,0,i+1)if((f[0][0][j]||f[1][0][j])&&(f[0][s][i-j]||f[1][s][i-j])) return true; // 因为 su!=0，补上循环中缺少的 su=0

    return false;

}

//Main

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0),cout.tie(0);

    cin>>n; R(i,0,n) cin>>a[i]; sort(a,a+n,greater<int>());

    R(i,0,n)if(a[i]>1) mn++; ln=n-mn,sn=1<<mn,sort(a,a+mn);

    if(mn*2>=n) cout<<"NO\n",exit(0);

    R(i,1,sn) b[i]=b[i>>1]+(i&1);

    f[0][0][1]=true;

    R(s,0,sn)R(i,0,ln+1)if(get(s,i)){

        f[1][s][i]=true;

        R(t,0,mn)if(!(s&(1<<t))&&a[t]==b[s]+i+1) // 加新的 a= 森林大小+1 的节点形成子树

            f[0][s^(1<<t)][i]=true;

    }

    if(f[0][sn-1][ln]) cout<<"YES\n";

    else cout<<"NO\n";

    return 0;

}

祝大家学习愉快！

巴特西

题解-CF429C Guess the Tree

题面

题解

代码

最新文章

热门文章