# 秦简

0%

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

# 题目2 : Tree Restoration

## 描述

There is a tree of N nodes which are numbered from 1 to N. Unfortunately, its edges are missing so we don’t know how the nodes are connected. Instead we know:

1. Which nodes are leaves

2. The distance (number of edges) between any pair of leaves

3. The depth of every node (the root’s depth is 1)

4. For the nodes on the same level, their order from left to right

Can you restore the tree’s edges with these information? Note if node u is on the left of node v, u’s parent should not be on the right of v’s parent.

# 题目1 : Legendary Items

## 描述

Little Hi is playing a video game. Each time he accomplishes a quest in the game, Little Hi has a chance to get a legendary item.

At the beginning the probability is P%. Each time Little Hi accomplishes a quest without getting a legendary item, the probability will go up Q%. Since the probability is getting higher he will get a legendary item eventually.

After getting a legendary item the probability will be reset to ⌊P/(2I)⌋% (⌊x⌋ represents the largest integer no more than x) where I is the number of legendary items he already has. The probability will also go up Q% each time Little Hi accomplishes a quest until he gets another legendary item.

Now Little Hi wants to know the expected number of quests he has to accomplish to get N legendary items.

Assume P = 50, Q = 75 and N = 2, as the below figure shows the expected number of quests is 3.25

# 谁知道呢，会遇见段海新教授

### 笼中之鸟，若不为自由而振翅，又怎么知道有多大的空间呢？

【人物】段海新，没有什么能够阻挡你对自由的向往

『没有什么能够阻挡，你对自由的向往』。

——段海新教授在WhiteHat网络安全技术论坛上的演讲

（特别感谢，徒弟自带的幸运光环天赋）

2016年10月15日，于中国·江宁无线谷