One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

用 disjoint set 来确定 Gang ,在 union 的过程中更新数据,同时在 find 的过程中确定 Head 是谁。偷懒直接用一个数组储存了姓名信息……

注意一下,输入共有 N 组数据,但是,最多可以有 2*N 的人。一开始犯二了,没想到……测试点 3 就段错误了……

代码如下:

继续阅读

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

    
    
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

偷懒写了递归版……

代码如下:

继续阅读

拍集体照时队形很重要,这里对给定的N个人K排的队形设计排队规则如下:

  • 每排人数为N/K(向下取整),多出来的人全部站在最后一排;
  • 后排所有人的个子都不比前排任何人矮;
  • 每排中最高者站中间(中间位置为m/2+1,其中m为该排人数,除法向下取整);
  • 每排其他人以中间人为轴,按身高非增序,先右后左交替入队站在中间人的两侧(例如5人身高为190、188、186、175、170,则队形为175、188、190、186、170。这里假设你面对拍照者,所以你的左边是中间人的右边);
  • 若多人身高相同,则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人,请编写程序输出他们的队形。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N(<=10000,总人数)和K(<=10,总排数)。随后N行,每行给出一个人的名字(不包含空格、长度不超过8个英文字母)和身高([30, 300]区间内的整数)。

输出格式:

输出拍照的队形。即K排人名,其间以空格分隔,行末不得有多余空格。注意:假设你面对拍照者,后排的人输出在上方,前排输出在下方。

输入样例:

输出样例:

PAT-A-1109-Group Photo 的中文版。

代码如下:

继续阅读

本题的基本要求非常简单:给定N个实数,计算它们的平均值。但复杂的是有些输入数据可能是非法的。一个“合法”的输入是[-1000,1000]区间内的实数,并且最多精确到小数点后2位。当你计算平均值的时候,不能把那些非法的数据算在内。

输入格式:

输入第一行给出正整数N(<=100)。随后一行给出N个正整数,数字间以一个空格分隔。

输出格式:

对每个非法输入,在一行中输出“ERROR: X is not a legal number”,其中X是输入。最后在一行中输出结果:“The average of K numbers is Y”,其中K是合法输入的个数,Y是它们的平均值,精确到小数点后2位。如果平均值无法计算,则用“Undefined”替换Y。如果K为1,则输出“The average of 1 number is Y”。

输入样例1:

输出样例1:

输入样例2:

输出样例2:

PAT-A-1108. FINDING AVERAGE 的中文版

这道题需要注意的是最多精确到 2 位,同时只有 0 个或 1 个合法数字时的输出。(似乎和测试点 3 有关

In case the average cannot be calculated, output “Undefined” instead of Y. In case K is only 1, output “The average of 1 number is Y” instead.

其他的就没有什么问题,就是发现自己的思路好不清晰,写第一遍时没有 AC ,然后偷懒直接 sscanf 反而过了……

本来打算写一个基于正则表达式的,但不知 regex.h 能不能用,回来有空尝试一下。

代码如下:

继续阅读

在不打扰居民的前提下,统计住房空置率的一种方法是根据每户用电量的连续变化规律进行判断。判断方法如下:

  • 在观察期内,若存在超过一半的日子用电量低于某给定的阈值e,则该住房为“可能空置”;
  • 若观察期超过某给定阈值D天,且满足上一个条件,则该住房为“空置”。

现给定某居民区的住户用电量数据,请你统计“可能空置”的比率和“空置”比率,即以上两种状态的住房占居民区住房总套数的百分比。

输入格式:

输入第一行给出正整数N(<=1000),为居民区住房总套数;正实数e,即低电量阈值;正整数D,即观察期阈值。随后N行,每行按以下格式给出一套住房的用电量数据:

K E1 E2 … EK

其中K为观察的天数,Ei为第i天的用电量。

输出格式:

在一行中输出“可能空置”的比率和“空置”比率的百分比值,其间以一个空格分隔,保留小数点后1位。

输入样例:

输出样例:

(样例解释:第2、3户为“可能空置”,第4户为“空置”,其他户不是空置。)

水题一道,“可能空置”与“空置”互斥,看题时没注意到……看数据才发现。

代码如下:

继续阅读

萌萌哒表情符号通常由“手”、“眼”、“口”三个主要部分组成。简单起见,我们假设一个表情符号是按下列格式输出的:

现给出可选用的符号集合,请你按用户的要求输出表情。

输入格式:

输入首先在前三行顺序对应给出手、眼、口的可选符号集。每个符号括在一对方括号[]内。题目保证每个集合都至少有一个符号,并不超过10个符号;每个符号包含1到4个非空字符。

之后一行给出一个正整数K,为用户请求的个数。随后K行,每行给出一个用户的符号选择,顺序为左手、左眼、口、右眼、右手——这里只给出符号在相应集合中的序号(从1开始),数字间以空格分隔。

输出格式:

对每个用户请求,在一行中输出生成的表情。若用户选择的序号不存在,则输出“Are you kidding me? @\/@”。

输入样例:

输出样例:

这道题,也有坑……

之后一行给出一个正整数K,为用户请求的个数。随后K行,每行给出一个用户的符号选择,顺序为左手、左眼、口、右眼、右手——这里只给出符号在相应集合中的序号(从1开始),数字间以空格分隔。

从 1 开始,但是测试数据被没有被限制在该范围内,所以应过滤输入,第 1 2 测试点就针对是这种情况吧。

代码如下:

继续阅读

复数可以写成(A + Bi)的常规形式,其中A是实部,B是虚部,i是虚数单位,满足i2 = -1;也可以写成极坐标下的指数形式(R*e(Pi)),其中R是复数模,P是辐角,i是虚数单位,其等价于三角形式(R(cos(P) + isin(P))。

现给定两个复数的R和P,要求输出两数乘积的常规形式。

输入格式:

输入在一行中依次给出两个复数的R1, P1, R2, P2,数字间以空格分隔。

输出格式:

在一行中按照“A+Bi”的格式输出两数乘积的常规形式,实部和虚部均保留2位小数。注意:如果B是负数,则应该写成“A-|B|i”的形式。

输入样例:

输出样例:

神坑 PAT,明明只是 Basic 级别中只有15分的题,通过率却只有 0.05,

我也贡献了十几次……过不了都怪我读题不认真T_T

没有比 Basic 级别的题目更言简意赅,简单明快的题目了,基本看一眼就可以写了,但是……但是……但是……谁知道会有这种坑。

坑主要就是在 -0.00 的问题之上了。

第一遍提交没过,考虑到实数的精度,于是使用了 float.h 中的 DBL_EPSILON 来提升精度。

……

……

……

……

……

然后我改了十几次,都没过……

后来随便输了一组数据……突然发现 -0.001 也会被过滤成 -0.00 ……当时就想打死自己……竟然会如此疏忽……

代码如下:

继续阅读

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:

Sample Output:

偷懒写了递归版……

感觉新增的 1108 – 1105 都有点水……

代码如下:

继续阅读

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate(房产)info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k Child1 … Childk M_estate Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0<=k<=5) is the number of children of this person; Childi‘s are the ID’s of his/her children;M_estate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M AVG_sets AVG_area

where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

Sample Input:

Sample Output:

用 disjoint set 来确定家庭……

child 和 parent 的 id 可能不在给出的人中,且没有资产

代码如下:

继续阅读

Given a set of N (> 1) positive integers, you are supposed to partition them into two disjoint sets A1 and A2 of n1 and n2numbers, respectively. Let S1 and S2 denote the sums of all the numbers in A1 and A2, respectively. You are supposed to make the partition so that |n1 – n2| is minimized first, and then |S1 – S2| is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 105), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 231.

Output Specification:

For each case, print in a line two numbers: |n1 – n2| and |S1 – S2|, separated by exactly one space.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

水题……排序后,后半部分减去前半部分的和……

代码如下:

继续阅读