Deduplication on a Linked List

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Deepest Root

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N (≤10​^4​​) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

PAT里链表题有各式各样的骚操作。这些非常规操作易学易用，但是习惯了这些后，反而对题目真正想考察的知识生疏了。今天就碰到一道这样的题，想用正经的算法写却写不出来。希望大家以我为戒，不要过多的学习这些「奇技淫巧」

Linked List Sorting这道题很常规，是个很一般的链表排序题。链表不能随机访问，因此算法上的选择限制很大，只有冒泡、插入、选择排序可以选。我选了冒泡练手，没想到没做出来。

Recover the Smallest Number

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification

Each input file contains one test case. Each case gives a positive integer N (≤10​^4​​) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Maximum Subsequence Sum

Given a sequence of K integers { N​1​​, N​2​​, …, N​K​​ }. A continuous subsequence is defined to be { N​i​​, N​i+1​​, …, N​j​​ } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Head of a gang

Head of a Gang

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 threthold 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.

Public Bike Management

1018 Public Bike Management

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

刷PAT的过程中遇到了两类排队问题,这里总结一下

• 所有人在同一时刻到达,如1014 Waiting in Line
• 每个人到达的时刻不同,如1017 Queueing at Bank

解决这类问题一个比较好的思路是递推. 对同一时刻到达的问题,可以每个窗口设置front和rear两个变量,分别表示队首和队尾离队时间.front值最小的队列就是应该插入的队列.入队元素的离队时间可以由rear+=current.duration递推给出.队首元素离队后,原来第二个元素成为新的队首元素.更新front+=header.duration.

Waiting in Line

1014 Waiting in Line

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
• Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
• Customer​i​​ will take T​i​​ minutes to have his/her transaction processed.
• The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

Emergency

1003 Emergency

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.