# 题目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.

## 输入

The first line contains three integers N, M and K. N is the number of nodes. M is the depth of the tree. K is the number of leaves.

The second line contains M integers A1, A2, … AM. Ai represents the number of nodes of depth i.

Then M lines follow. The ith of the M lines contains Ai numbers which are the nodes of depth i from left to right.

The (M+3)-th line contains K numbers L1, L2, … LK, indicating the leaves.

Then a K × K matrix D follows. Dij represents the distance between Li and Lj.

1 ≤ N ≤ 100

## 输出

For every node from 1 to N output its parent. Output 0 for the root’s parent.

8 3 5
1 3 4
1
2 3 4
5 6 7 8
3 5 6 7 8
0 3 3 3 3
3 0 2 4 4
3 2 0 4 4
3 4 4 0 2
3 4 4 2 0

0 1 1 1 2 2 4 4

# 解析

• 对于每层第一个节点，上一层的第一个非叶子节点必然是这个节点的父节点。
• 此时记录该节点的父节点，并把父节点的子节点记录为当前节点，并以此更新这个父节点与其他已知节点的距离。
• 然后看该层下一个节点。
• 下一个节点若与前一个节点距离为2，则两者父节点相同。
• 若大于2，则该节点的父节点是上一层的下一个非叶子节点。同时记录父、子节点，更新距离。
• 如此每层循环，每层结束进入上一层，直到第二层。（第一层根节点不必再判断了。

## AC代码（C++）：

#include<iostream>
using namespace std;

int main() {
int N, M, K;
//N is the number of nodes. M is the depth of the tree. K is the number of leaves.
cin >> N >> M >> K;

int depth[105] = { 0 };
//depth[] represents the number of nodes of depth[i].
for (int i = 0; i < M; i++) {
cin >> depth[i];
}

int tree[105][105] = { 0 };
//the nodes of depth[i] from left to right.
for (int i = 0; i < M; i++) {
for (int j = 0; j < depth[i]; j++) {
cin >> tree[i][j];
}
}

int leaves[105] = { 0 };
//leaves node
int is_leaves[105] = { 0 };
//Determine whether a node is a leaf node
for (int i = 0; i < K; i++) {
cin >> leaves[i];
is_leaves[leaves[i]] = 1;
}

int dis[105][105] = { 0 };
// the distance between Li and Lj.
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
cin >> dis[leaves[i]][leaves[j]];
}
}

int father[105] = { 0 };
int son[105] = { 0 };
//record a child node of a node

father[tree[0][0]] = 0;
for (int i = 0; i < depth[1]; i++) {
father[tree[1][i]] = tree[0][0];
}

for (int i = M - 1; i >= 2; i--) {
int up_point = 0;
////i-1层中第一个不是叶子节点的节点，必定是当前节点的父亲
while (is_leaves[tree[i - 1][up_point]] && up_point < depth[i - 1]) {
up_point++;
}
int point_a = tree[i][0];
father[point_a] = tree[i - 1][up_point];
son[tree[i - 1][up_point]] = point_a;
//更新距离
for (int k = 0; k < N; k++) {
if (dis[point_a][k] > 0) {
dis[father[point_a]][k] = dis[k][father[point_a]] = dis[point_a][k] - 1;
}
}

for (int k = 0; k < K; k++) {
dis[leaves[k]][father[point_a]] = dis[father[point_a]][leaves[k]] = dis[leaves[k]][point_a] - 1;
}

for (int j = 1; j < depth[i]; j++) {
int point_b = tree[i][j];
//如果和前一个节点u距离为2，说明父亲节点相同
if (dis[point_a][point_b] == 2) {
father[point_b] = father[point_a];
}
//否则，父亲节点是i-1层中下一个非叶子节点
else {
up_point++;
while (is_leaves[tree[i - 1][up_point]] && up_point < depth[i - 1]) {
up_point++;
}
father[point_b] = tree[i - 1][up_point];
son[tree[i - 1][up_point]] = point_b;
//更新距离
for (int kk = 0; kk < N; kk++) {
if (dis[point_b][kk] > 0) {
dis[father[point_b]][kk] = dis[kk][father[point_b]] = dis[point_b][kk] - 1;
}
}
}
point_a = point_b;
}
//更新i-1层相邻节点的距离
for (int kk = 0; kk < depth[i - 1] - 1; kk++) {
if (!is_leaves[tree[i - 1][kk]] && !is_leaves[tree[i - 1][kk + 1]]) {
dis[tree[i - 1][kk]][tree[i - 1][kk + 1]] = dis[tree[i - 1][kk + 1]][tree[i - 1][kk]] = dis[son[tree[i - 1][kk]]][son[tree[i - 1][kk + 1]]] - 2;
}
}
}
cout << father[1];
for (int i = 2; i <= N; i++) {
cout << " " << father[i];
}
return 0;
}


## WA代码（C++）：

100个节点的数据太多了。暂时无法测试。

#include<iostream>
using namespace std;

int main() {
int N, M, K;
//N is the number of nodes. M is the depth of the tree. K is the number of leaves.
cin >> N >> M >> K;

int count_depth[105] = { 0 };
for (int i = 1; i <= M; i++) {
cin >> count_depth[i];
}

int tree[105][105] = { 0 };
int depth_of_node[105] = { 0 };
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= count_depth[i]; j++) {
cin >> tree[i][j];
depth_of_node[tree[i][j]] = i;
}
}

int is_leaf[105] = { 0 };
int num_leaf[105] = { 0 };
for (int i = 1; i <= K; i++) {
int TEMP;
cin >> TEMP;
num_leaf[i] = TEMP;
is_leaf[TEMP] = 1;
}

int dis[105][105] = { 0 };
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
cin >> dis[num_leaf[i]][num_leaf[j]];
}
}

int father_node[105] = { 0 };

int s_son_node[105] = { 0 };
for (int i = 1; i <= N; i++) {
if (is_leaf[i]) {
s_son_node[i] = i;
}
}

for (int i = M; i > 0; i--) {
int count_top = 1;
for (int j = 1; j <= count_depth[i]; j++) {
if (j == 1) {
for (; count_top <= count_depth[i - 1]; count_top++) {
if (is_leaf[tree[i - 1][count_top]] != 1) {
father_node[tree[i][j]] = tree[i - 1][count_top];
s_son_node[tree[i - 1][count_top]] = tree[i][j];
count_top++;
break;
}
}
continue;
}
if (dis[tree[i][j]][tree[i][j - 1]] == 2) {
father_node[tree[i][j]] = father_node[tree[i][j - 1]];
}
else {
for (; count_top <= count_depth[i - 1]; count_top++) {
if (is_leaf[tree[i - 1][count_top]] != 1) {
father_node[tree[i][j]] = tree[i - 1][count_top];
s_son_node[tree[i - 1][count_top]] = tree[i][j];
count_top++;
break;
}
}
continue;
}
}

//更新上一层节点间距离
for (int j = 1; j <= count_depth[i - 1]; )
{
for (int jj = j + 1; jj <= count_depth[i - 1]; jj++)
{
dis[tree[i - 1][j]][tree[i - 1][jj]] = dis[tree[i - 1][jj]][tree[i - 1][j]] = dis[s_son_node[tree[i - 1][j]]][s_son_node[tree[i - 1][jj]]] - (depth_of_node[s_son_node[tree[i - 1][j]]] - depth_of_node[tree[i - 1][j]]) - (depth_of_node[s_son_node[tree[i - 1][jj]]] - depth_of_node[tree[i - 1][jj]]);
}
j++;
}
}
//输出
for (int i = 1; i < N; i++)
{
cout << father_node[i] << " ";
}
cout << father_node[N];

return 0;
}


## 最终结果

1490Tree RestorationACG++5ms0MB

# 题目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

2*50%*25% + 3*50%*75%*100% + 3*50%*100%*25% + 4*50%*100%*75%*100% = 3.25


## 输入

The first line contains three integers P, Q and N.

1 \leq N \leq 10^6, 0 \leq P \leq 100, 1 \leq Q \leq 1001≤N≤106,0≤P≤100,1≤Q≤100

## 输出

Output the expected number of quests rounded to 2 decimal places.

50 75 2

3.25

# 解析

EX=\sum{(X \cdot P(X))}EX=∑(X⋅P(X))

E(X+Y)=EX+EYE(X+Y)=EX+EY

1.初始任务数（至少1次任务就能获得）numQuests=1numQuests=1
2.第一次任务对该次获得传奇物品增加的期望：incE=(1-P)incE=(1−P)
3.调整概率P=P+QP=P+Q
4.进行下一次任务对该次获得传奇物品增加的期望计算：incE=incE\cdot(1-P)incE=incE⋅(1−P)
5.任务期望：numQuests=numQuest+incEnumQuests=numQuest+incE
6.回到步骤3
7.直至P=P+Q>100P=P+Q>100终止此次获得传奇物品的期望计算numQuestsnumQuests

## AC代码（C++）：

#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
int P, Q, N;
cin >> P >> Q >> N;

double count_q=Q*1.00/100;
double count_p;
double result = 0.00;

for (int i = 1; i <= N; i++)
{
double next_result = 1;

count_p = P*1.00 / 100;
double E1 = 1.00;
while (1)
{
E1 = E1*(1.00 - count_p);
next_result += E1;
count_p += count_q;
if (count_p > 1.00)
break;
}

result += next_result;
P = P / 2;
}

cout << fixed << setprecision(2) << result;

return 0;
}


## 最终结果

1489Legendary ItemsACG++22ms0MB

## PAT (Advanced Level)-1019. General Palindromic Number (20)

PAT (Advanced Level)-1019. General Palindromic Number (20)

### 1019. General Palindromic Number (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N > 0 in base b >= 2, where it is written in standard notation with k+1 digits ai as the sum of (aibi) for i from 0 to k. Here, as usual, 0 <= ai < b for all i and ak is non-zero. Then N is palindromic if and only if ai = ak-i for all i. Zero is written 0 in any base and is also palindromic by definition.

Given any non-negative decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.

Input Specification:

Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 109 is the decimal number and 2 <= b <= 109 is the base. The numbers are separated by a space.

Output Specification:

For each test case, first print in one line “Yes” if N is a palindromic number in base b, or “No” if not. Then in the next line, print N as the number in base b in the form “ak ak-1 … a0”. Notice that there must be no extra space at the end of output.

Sample Input 1:
27 2
Sample Output 1:
Yes
1 1 0 1 1

Sample Input 2:
121 5
Sample Output 2:
No
4 4 1

### 完整代码

#include<iostream>

using namespace std;

void OUTPUT(int transArray[], int FLAG)
{
for (int i = FLAG - 1; i >= 0; i--)
{
if (i != 0)
{
cout << transArray[i] << " ";
}
else
cout << transArray[i];
}
if (FLAG == 0)
{
cout << transArray[0];
}
}

int main()
{
int N, b;
cin >> N >> b;

int transArray[500];            //数组设置大一些，避免N最大时候，转换2进制时候越界

int FLAG=0;         //标记转换后的数字有多少位
int FLAG_XX = 0;            //标记是否为回文数

if (N == 0)         //输入为0时的特殊处理
{
transArray[0] = N;
}
else            //其他正常输入
{
for (; N; FLAG++)
{
transArray[FLAG] = N%b;
N = N / b;
}

//判断回文，循环次数可以折半
for (int i = FLAG - 1; i >= (int)((FLAG - 1) / 2); i--)
{
if (transArray[i] != transArray[FLAG - 1 - i])
{
FLAG_XX = 1;
}
}
}

//输出
if (FLAG_XX == 0)
{
cout << "Yes" << endl;
OUTPUT(transArray, FLAG);
}
else if (FLAG_XX == 1)
{
cout << "No" << endl;
OUTPUT(transArray, FLAG);
}
return 0;
}

## PAT (Advanced Level)-1011. World Cup Betting (20)

PAT (Advanced Level)-1011. World Cup Betting (20)

### 1011. World Cup Betting (20)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results — namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.

For example, 3 games’ odds are given as the following:

W　T　L

1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1

To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.13.02.5*65%-1)*2 = 37.98 yuans (accurate up to 2 decimal places).

Input

Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.

Output

For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.

Sample Input

1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1

Sample Output

T T W 37.98

### 完整代码

#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
double odd[3][3];           //记录原始输入数据

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cin >> odd[i][j];

char result[3];         //存储输出WTL
int signNum[3] = { 0,0,0 };         //标记

for (int i = 0; i < 3; i++)
{
double temp = odd[i][0];            //大小比较中的临时量

for (int j = 1; j < 3; j++)
{
if (temp <= odd[i][j])
{
temp = odd[i][j];
signNum[i] = j;
}
}
if (signNum[i] == 0)
{
result[i] = 'W';
}
else if (signNum[i] == 1)
{
result[i] = 'T';
}
else if (signNum[i] == 2)
{
result[i] = 'L';
}
}

//计算
double res = (odd[0][signNum[0]] * odd[1][signNum[1]] * odd[2][signNum[2]] * 0.65 - 1.00) * 2.00;

for (int i = 0; i < 3; i++)
cout << result[i] << " ";
cout << fixed << setprecision(2) << res;//这一块我们回到1002题目中，如何限定小数精度并四舍五入。

return 0;
}

## PAT (Advanced Level)-1009. Product of Polynomials (25)

PAT (Advanced Level)-1009. Product of Polynomials (25)

### 1009. Product of Polynomials (25)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

### 完整代码

#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct Node
{
double sum;
int e;
}Node;
#define MAX 3000
int main()
{
int n1, n2;
cin >> n1;

std::vector<Node> a(n1);
for (int i = 0; i < n1; ++i)
{
cin >> a[i].e;
cin >> a[i].sum;
}

cin >> n2;
std::vector<Node> b(n2);
for (int i = 0; i < n2; ++i)
{
cin >> b[i].e;
cin >> b[i].sum;
}
//product
std::vector<double> p;
p.assign(MAX + 1, 0.0);
for (int i = 0; i < n1; ++i)
{
for (int j = 0; j < n2; ++j)
{
Node tmp;
tmp.e = a[i].e + b[j].e;
tmp.sum = a[i].sum*b[j].sum;
p[tmp.e] += tmp.sum;
}
}
//output
int cnt = 0;
for (int i = MAX; i >= 0; --i)
{
if (std::fabs(p[i]) > 1e-6)
cnt++;
}
printf("%d", cnt);
for (int i = MAX; i >= 0; --i)
{
if (std::fabs(p[i]) > 1e-6)
cout << fixed << setprecision(1) << " " << i << " " << p[i];
}
printf("\n");

return 0;
}