【NOI2020 超现实树】


题意

对于所有的无标号且区分左右儿子的有根二叉树,定义一棵树

T1T_1

T1​ 可以由另一棵树

T2T_2

T2​ 生长得到,当且仅当可以通过进行若干次将

T2T_2

T2​ 的叶节点替换成某棵二叉树的操作得到。对于一个二叉树集合

T\mathscr{T}

T,定义

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 表示所有可以由

T\mathscr{T}

T 中的树生长得到的树构成的集合。定义

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 是完备的当且仅当只有有限棵二叉树不在

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 中。给一个二叉树集合

T\mathscr{T}

T,问

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 是否完备。

n,m2106\sum n,\sum m\le 2*10^6

∑n,∑m≤2∗106

分析

定义树枝为那些每个节点的左右子树的

sizesize

size 的

minmin

min 不超过

11

1 的二叉树。换句话说,就是那些由一条主链和另外若干个叶子构成的二叉树。

可以发现

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 是完备的,当且仅当只有有限个树枝不能被生长得到。因为一棵树一定可以由一棵与它深度相同的树枝生长得到,那么若某个深度的树枝均能够被生长得到,所有不小于这个深度的树也就都能被生长得到。

问题转化为是否所有树枝都能被生长得到。对于输入的那些不是树枝的树,生成的也肯定不是树枝,故可以忽略。

除了单独的根节点以外,可以把所有的树枝分成四类:
(1)根有左儿子,但没有右儿子。
(2)根有右儿子,但没有左儿子。
(3)根有左右儿子,且左子树大小为

11

1。
(4)根有左右儿子,且右子树大小为

11

1。
注意后两种可能包含重复的树。

每种树枝都有无限种,故

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 是完备的当且仅当四种树枝都是完备的。考虑如下判断

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 是否完备的递归算法:
1、若

T\mathscr{T}

T 中存在一个单独的点,那么

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 一定是完备的。
2、对于

T\mathscr{T}

T 中所有能被归到第一类的树枝,设它们左子树构成的集合为

T\mathscr{T’}

T′,递归判断

grow(T)\mathrm{grow}(\mathscr{T’})

grow(T′) 是否完备。对于后三类树枝也做同样的处理。
3、

grow(T)\mathrm{grow}(\mathscr{T})

grow(T) 完备当且仅当上一个步骤中每一次递归的集合都是完备的。

时间复杂度

O(n)O(\sum n)

O(∑n)。

代码

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const int N = 2000005;

int m;

struct Tree
{
int n, *lef, *rig, *size;

void init()
{
scanf("%d", &n);
lef = new int[n + 1]; rig = new int[n + 1]; size = new int[n + 1];
size[0] = 0;
for (int i = 1; i <= n; i++) scanf("%d%d", &lef[i], &rig[i]);
}

bool check(int x)
{
if (lef[x] && !check(lef[x])) return 0;
if (rig[x] && !check(rig[x])) return 0;
size[x] = size[lef[x]] + size[rig[x]] + 1;
if (!lef[x] || !rig[x]) return 1;
return min(size[lef[x]], size[rig[x]]) <= 1;
}

void clear()
{
delete[] lef;
delete[] rig;
delete[] size;
}
}t[N];

bool solve(vector<pi> & vec)
{
if (!vec.size()) return 0;
for (pi w : vec) if (t[w.first].size[w.second] == 1) return 1;
vector<pi> v1, v2, v3, v4;
for (pi w : vec)
{
int x = w.first, y = w.second;
if (!t[x].lef[y]) v1.push_back(make_pair(x, t[x].rig[y]));
if (!t[x].rig[y]) v2.push_back(make_pair(x, t[x].lef[y]));
if (t[x].size[t[x].lef[y]] == 1 && t[x].rig[y]) v3.push_back(make_pair(x, t[x].rig[y]));
if (t[x].size[t[x].rig[y]] == 1 && t[x].lef[y]) v4.push_back(make_pair(x, t[x].lef[y]));
}
vec.clear();
if (!solve(v1) || !solve(v2) || !solve(v3) || !solve(v4)) return 0;
return 1;
}

int main()
{
int T; scanf("%d", &T);
while (T--)
{
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
t[i].init();
if (!t[i].check(1)) t[i].clear(), i--, m--;
}
vector<pi> vec;
for (int i = 1; i <= m; i++) vec.push_back(make_pair(i, 1));
puts(solve(vec) ? "Almost Complete" : "No");
for (int i = 1; i <= m; i++) t[i].clear();
}
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【NOI2020 超现实树】

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【NOI2020 超现实树】
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏