列表

详情


NC207389. TreeII

描述

系统中有一棵n个点的完全k叉树,现给出它的BFS层序遍历序列a_i(即从根节点开始,每一层从左向右遍历),请你还原这棵树,并返回加密后的答案。
答案加密方法:所有边两个端点异或的和,即,其中(u_i, v_i)为一条树上的边。

下面给出完全二叉树的定义:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k层所有的结点都连续集中在最左边。
请你根据这个定义进行适度推广,得到完全k叉树的含义。

输入描述

数据满足:

示例1

输入:

2,[1,2,3,4,5]

输出:

18

说明:

树边为(1, 2), (1, 3), (2, 4), (2, 5),加密过程为(1^2)+(1^3)+(2^4)+(2^5),答案为18。

样例1构成的完全二叉树为:

示例2

输入:

3,[1,2,3,4,5]

输出:

17

说明:

树边为(1, 2), (1, 3), (1, 4), (2, 5),加密过程为(1^2)+(1^3)+(1^4)+(2^5),答案为17。

样例2构成的完全三叉树为:

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C(clang11) 解法, 执行用时: 39ms, 内存消耗: 4068K, 提交时间: 2020-11-20 23:57:20

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 
 * @param k int整型 表示完全k叉树的叉数k
 * @param a int整型一维数组 表示这棵完全k叉树的Bfs遍历序列的结点编号
 * @param aLen int a数组长度
 * @return long长整型
 */
long long tree2(int k, int* a, int aLen ) {
    long long int y=0;
    for(long long int i=1;i<aLen;++i)
    {
        y+=a[i]^a[(i-1)/k];
    }
    return y;
}

Go(1.14.4) 解法, 执行用时: 34ms, 内存消耗: 9716K, 提交时间: 2020-11-20 21:27:05

package main

// github.com/EndlessCheng/codeforces-go
func tree2(k int, a []int) int64 {
	q := []int{a[0]}
	a = a[1:]
	ans := 0
	for len(a) > 0 {
		qq := q
		q = nil
		for _, v := range qq {
			for i := 0; i < k && len(a) > 0; i++ {
				q = append(q, a[0])
				ans += v ^ a[0]
				a = a[1:]
			}
		}
	}
	return int64(ans)
}

Python(2.7.3) 解法, 执行用时: 740ms, 内存消耗: 14196K, 提交时间: 2020-11-20 20:11:37

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 
# @param k int整型 表示完全k叉树的叉数k
# @param a int整型一维数组 表示这棵完全k叉树的Bfs遍历序列的结点编号
# @return long长整型
#
class Solution:

    def tree2(self, k, a):
        res = 0
        for i in xrange(1, len(a)):
            res += a[i] ^ a[(i - 1) / k]
        return res

C++(clang++11) 解法, 执行用时: 37ms, 内存消耗: 4076K, 提交时间: 2020-11-26 00:03:21

class Solution
{
	public:
		long long tree2(int k,vector<int> &a)
		{
			long long s=0;
			int n=a.size(),i;
			for(i=1;i<n;i=i+1)
			s+=a[i]^a[(i-1)/k];
			return s;
		}
};

上一题