| 题目名称 | 2103. [HZOI 2015] CrazyBinary |
|---|---|
| 输入输出 | crazy_binary.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 stdafx.h
于2015-11-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：3， 通过率：33.33% | ||||
 stdafx.h |
100 | 0.352 s | 64.24 MiB | C++ |
 FoolMike |
20 | 0.249 s | 138.15 MiB | C++ |
 再见 |
0 | 0.031 s | 0.34 MiB | C++ |
| 关于 CrazyBinary 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
要是数据真错了 你就出个修正版 sorry
这是我高一出的题目... 等我高三结束再改数据.... stdafx.h
2017-03-11 18:57
6楼
| ||||
|
| ||||
|
回复 @FoolMike :
这个不是原题 注意题目描述 stdafx.h
2017-03-11 18:55
4楼
| ||||
|
回复 @FoolMike :
出这道题的学长已经退役了。  _Itachi
2017-02-19 14:08
3楼
| ||||
|
数据有误，请您手算一下第一组数据，正确的答案应该是4
方案如下： 将9号点的权值改为-1e9，将2号点的权值改为1e9，将7号点的权值改为1e9，将4号点的权值改为16 这个方案是合法的，修改次数为4，而数据中答案为6，请您修正！ | ||||
|
有人来做这道题来帮你验数据吗
 zys
2015-12-17 18:10
1楼
| ||||
2103. [HZOI 2015] CrazyBinary
★★★☆ 输入文件：crazy_binary.in
输出文件：crazy_binary.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
自从stdafx考试看错题后十分不服,发明了一种新型的二叉搜索树,满足:设key[p]表示结点p上的数值.对于其中的每个结点p,若其存在左孩子lch,则key[p]>key[lch],若其存在右孩子rch,则key[p]<key[rch],而且:这种关系只针对与一个节点和它的父节点,而和之前节点的值无关,如A点的值为5,A的左子节点B的值为4,B的右子节点的值可以为100.
现在给定一棵这样二叉树,可以任意修改结点的数值,修改一个结点的数值算作一次修改,且这个结点不能再被修改.若要将其变成这种特殊的二叉搜索树,且任意时刻结点的数值必须是整数(可以是负整数或0),求所要的最少修改次数,结点1一定是二叉树的根.
【输入格式】
第一行一个正整数n表示二叉树结点数。结点从1~n进行编号.
第二行n个正整数用空格分隔开,第i个数ai表示结点i的原始数值
此后n-1行每行两个非负整数fa,ch,第i+2行描述结点i+1的父亲编号fa,以及父子关系ch,(ch=0 表示i+1为左儿子,ch=1表示i+1为右儿子).
【输出格式】
仅一行包含一个整数,表示最少的修改次数.
【样例输入】
3
2 2 2
1 0
1 1
【样例输出】
2
【提示】
数据范围约定:
20 % ：n <= 10
40 % ：n <= 100
100 % ：n <= 2000
【来源】
by stdafx,改编自"改造二叉树"