PAT (Advanced Level)-1004. Counting Leaves (30)

PAT (Advanced Level)-1004. Counting Leaves (30)

1004. Counting Leaves (30)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.


Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.

Sample Input

2 1
01 1 02

Sample Output

0 1

解读

题目条件无非就是构建并存储树,但是如何处理题目中输入的父节点和子节点是一个算法中的关键。

采用map容器,把每一个节点和存储它的子节点容器进行关联,可以方便操作。

对于存储之后的统计每层级的叶子数,可以采用深度优先的算法,通过临时变量level,在迭代中不干扰其他支线的统计,保证同级的叶子最终均会统计入LeavesOfLevel数组中。

但是这样做会有一个麻烦,由于迭代的过程level在不同的环节是不同的值,无法直接知晓探索到最深时候level的值,所以我们通过辅助统计的变量LeavesCount记录每一级的叶子数,并在输出时候进行累加,直到LeavesCount与总叶子数Leaves相同,即可停止对LeavesOfLevel数组的输出。

完整代码

#include<iostream>
#include<vector>
#include<map>

using namespace std;

map<int, vector<int>> List;

void DFS(int, int, int[]);

int main()
{
	int N, M;
	int LeavesOfLevel[101] = { 0 };//统计每级上面的叶子节点

	//输入部分
	cin >> N >> M;	
	for (int i = 0; i < M; i++)
	{
		int ID, K, ID_Son;
		cin >> ID >> K;
		for (int j = 0; j < K; j++)
		{
			cin >> ID_Son;
			List[ID].push_back(ID_Son);
		}
	}

	int Leaves = N - M;//统计总叶子数
	//深度优先搜索
	DFS(1, 0, LeavesOfLevel);

	//输出部分
	int LeavesCount = LeavesOfLevel[0];//辅助记录
	cout << LeavesOfLevel[0];
	for (int i = 1; LeavesCount < Leaves; i++)
	{
		cout << " " << LeavesOfLevel[i];
		LeavesCount += LeavesOfLevel[i];
	}
	
	return 0;
}

//深度优先,统计每层级的叶子数
void DFS(int id, int level,int LeavesOfLevel[])
{
	if (List[id].empty())
	{
		LeavesOfLevel[level]++;
		return;
	}

	vector<int>::iterator item = List[id].begin();

	for (; item != List[id].end(); item++)
	{
		DFS(*item, level+1, LeavesOfLevel);
	}
}

PAT (Advanced Level)-1024. Palindromic Number (25)

PAT (Advanced Level)-1024. Palindromic Number (25)

1024. Palindromic Number (25)

时间限制
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.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 1010) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3

Sample Output 2:

1353
3

解读

这一天考查的很简单,就是如何判断回文数。但是按照题目的条件,即便使用long long类型都无法全部通过检查点。故而遇见此类大数问题可以使用string来避免上限的限制。 熟练掌握字符和数值的转换。可以提升写代码的速度。同样也可以用STL标准库函数来缩减代码量。

完整代码

#include<iostream>
#include<cstring>
#include<string>


using namespace std;

string add(string str1, string str2)
{
	if (str2.length() > str1.length())
	{
		string buf;
		for (int i = 0; i < (str2.length() - str1.length()); i++)
		{
			buf += "0";
		}
		buf += str1;
		str1 = buf;
	}
	else
	{
		string buf;
		for (int i = 0; i < (str1.length() - str2.length()); i++)
		{
			buf += "0";
		}
		buf += str2;
		str2 = buf;
	}

	string result;
	bool addition = false;
	for (int i = str1.length() - 1; i >= 0; i--)
	{
		int val = (str1[i] - '0') + (str2[i] - '0') + addition;
		if (val >= 10)
		{
			result += (val - 10 + '0');
			addition = true;
		}
		else
		{
			result += (val + '0');
			addition = false;
		}
	}
	if (addition)
	{
		result += '1';
	}

	string RealResult;
	for (int i = 0; i < result.length(); i++)
	{
		RealResult += result[result.length() - 1 - i];
	}

	return RealResult;
}

string inverted_sequence(string N)// 翻转数字
{
	string rN;

	for (int i = 0; i < N.length(); i++)
	{
		rN += N[N.length() - 1 - i];
	}
	
	return rN;
}

bool J_Palindromic(string Palindromic)//判断回文
{
	int L = Palindromic.length();
	int signBOOL=0;
	for (int i = L-1; i > ((L-1) / 2); i--)
	{
		if (Palindromic[i] != Palindromic[L - 1 - i])
			signBOOL = 1;
	}
	if (signBOOL == 1)
		return false;
	else
		return true;

}

int main()
{
	string N;
	int K;
	cin >> N >> K;

	if (J_Palindromic(N))//判断输入的数字是否为回文,是则输出。
	{
		cout << N << '\n' << 0;
	}
	else 
	{
		string rN;
		bool signBOOL;//回文标记。

		for (int i = 1; i <= K; i++)
		{
			rN = inverted_sequence(N);
			N = add(N, rN);
			if (signBOOL = J_Palindromic(N))
			{
				cout << N << '\n' << i;
				break;
			}
			if (i == K)
			{
				cout << N << '\n' << K;
			}
		}

	}


	return 0;
}

微软2017年预科生计划在线编程笔试 第2题 Tree Restoration

微软2017年预科生计划在线编程笔试 第2题 Tree Restoration

题目2 : Tree Restoration

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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.

tree-restoration.png

输入

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 };
	//answer
	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++):

思路应该是没有问题的,但是结果WA,本地测试了几组数据没有问题。
可能的原因是部分边缘数据在算法中出了问题。
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

微软2017年预科生计划在线编程笔试 第1题 Legendary Items

微软2017年预科生计划在线编程笔试 第1题 Legendary Items

题目1 : Legendary Items

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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
legendary.png

输入

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

解析

不得不承认,微软在样例中给的二叉树真的十分具有诱惑性,让人第一反应就是模仿这个样子去实现,去计算。为什么呢?
因为用二叉树表现这个概率计算过程,一看就明了,算法都很清晰,剩下的就是去码代码了。

但是,很显然,这样做和暴力解题是差不多的。
就是从N个传奇物品出发,思考所有的可能性,并计算每种可能性的概率。

最终通过数学期望的定义:
   EX=\sum{(X \cdot P(X))}EX=∑(XP(X))

计算想要的结果。

首先,我们要看到的是,这是一道典型的概率计算题目。 每次完成任务,结果无非就是“获得传奇物品”和“未获得物品”。未获得物品时候,我们继续完成任务,这次获得的概率将会变化(不断提高),也就是说,最终必然会获得一个传奇物品。

在思考这个问题的时候,首先要很清晰的认识到每次获得传奇物品这个事件,是相互独立的。获得第一个传奇物品和获得第ii个传奇物品是独立的,即便第ii次的概率是通过[P/2^i][P/2i]计算得到的,但实际上每次的P'P(区别于初始PP)都是固定的。

所以,在计算最终期望的过程中,我们就可以对每次获得传奇物品的任务期望分别计算,最后进行加和,即可得到最终的结果。

根据数学期望的性质:
   E(X+Y)=EX+EYE(X+Y)=EX+EY

所以 EN=E_{(1)}1+E_{(2)}1+E_{(3)}1+.....+E_{(N)}1EN=E(1)​1+E(2)​1+E(3)​1+.....+E(N)​1

而每次获得传奇物品的期望E_{(i)}1E(i)​1计算方法如下:

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


其实这个代码还可以继续优化,因为在P小于一定值的的时候,后续的传奇物品的期望都是相同的。比如在Q=75Q=75时,P<5P<5后,期望就相同了,不必重复计算。


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


解读

这个问题的考察点很明确:十进制数对任意进制转换的问题。
那么进制的转换的一个思路:(十进制数N,进制基数b)

我们通过辗转相除:对原始数据N每次除以进制基数b,所得余数(N%b)为转换后的最后一位数,再将商(N/b)除以进制基数,余数为倒数第二位,如此循环往复,直至最后商小于进制基数。

从上述算法中我们可以得到一个仅需要对每次的被除数进行修正,即N=N/b,每次将商付给被除数进行操作。
上述算法另外一个需要注意的便是,由于第一次运算得到的是最后一位数,所以输出的时候就需要反序来输出了。

完整代码

#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;
}