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

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

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

解读

这道题目其实就是考察比较大小,找出最大值并记录的问题。
题目中有3×3的数据,我们在每一行找到最大的,并记录所在位置(标识WTL)和数值(运算)。 故而,在下面的代码中,我使用了signNum数组来记录三行中最大值在其所在行中的位置。

完整代码

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