首先我们要注意到一个性质: 由于根与右子树的根奇偶性相同, 那么根的奇偶性与 \(N\) 相同
然后我们发现对于一个完美树, 他的左右两个儿子都是完美树
也就是说, 一颗完美树是由两棵完美树拼成的
注意到另一个性质: 由于权值是一个排列, 假设根节点为 \(x\), 那么左子树的范围是 \([1, x - 1]\), 右子树为 \([x + 1, n]\)
由于根节点和 \(N\) 奇偶性相同, 那么左子树的大小与 \(N\) 的奇偶性相反, 所以右子树大小为偶数
如果子树区间为 \([l, r]\), 那么其实可以把它看成 \([1, r - l + 1]\), 所以只和子树大小有关, 和子树权值无关
手玩一波小数据:
当 \(N=1\) 时, 就是一个点
当 \(N=2\) 时, 二为根, 一为根的左子树
当 \(N=3/4\) 时为样例
当 \(N=5\) 时, 可以用两个 2 的子树拼成
然后我们发现, 能作为右子树的只有 \(2/4\), 前五个都不是满二叉树, 所以我们可以合并两颗树, 当且仅当两个二叉树高度相同
发现 2 的高度为 2, 没有与之相同树高的树, 所以能作为右子树的只有 \(4\)
所以我们就有: 用 \(4/5\) 可以凑出 \(9/10\),\(9/10\) 又可以拼出 \(19/20\)......
所以我们就可以用 \(4/5\) 一路递推下去, 发现每次都 * 了 \(2\), 所以复杂度为 \(O(logN)\)
- \(Code:\)
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int n, x = 4, y = 5;
- scanf("%d", &n);
- if(n == 1 || n == 2) return puts("1"), 0;
- while(y < n) {
- if(x & 1) x = 2 * y, y = x + 1;
- else x = 2 * y - 1, y = x + 1;
- }
- return printf("%d", (x == n || y == n)), 0;
- }
来源: http://www.bubuko.com/infodetail-3267241.html