PAT1037 Magic Coupon (25)

The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!

For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:

Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.

Output Specification:

For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:

Sample Output:






测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 256 10/10
1 答案正确 1 256 3/3
2 答案正确 1 352 3/3
3 答案正确 1 348 3/3
4 答案正确 53 2560 3/3
5 答案正确 1 356 3/3


PAT 1100. Mars Numbers (20)

People on Mars count their numbers with base 13:

  • Zero on Earth is called “tret” on Mars.
  • The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
  • For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.

For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (< 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:

For each number, print in a line the corresponding number in the other language.

Sample Input:

Sample Output:




PAT 1077. Kuchiguse (20)

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:


  • Itai nyan~ (It hurts, nyan~)
  • Ninjin wa iyada nyan~ (I hate carrots, nyan~)


Now given a few lines spoken by the same character, can you find her Kuchiguse?




PAT 1017. Queueing at Bank (25)


Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.


  • 8点之前到的顾客要等8点开门
  • 17点之后到的顾客就不能进入了(不算入平均时间),但是17点之前到的,可以拖到17点之后完成



  1. 如果窗口现在有工作,那等待的时间就是T1-T0;
  2. 如果窗口现在空置(T1<T0),那么等待时间为0;




测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 256 12/12
1 答案正确 1 256 3/3
2 答案正确 1 256 3/3
3 答案正确 1 368 3/3
4 答案正确 1 360 2/2
5 答案正确 5 364 2/2

1074. Reversing Linked List (25) 链表反转~最后一个测试点,小心特殊情况!


Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

Sample Output:






[上一地址 ] [上个值 ] [当前地址]

[当前地址] [当前值] [下一地址]






1. K=1, K=N

2. 给的头指针不是整条链的头指针,而是中间某个节点的。这个问题是最后一个测试点测试的东西。我一开始也试了好多无果,还好搜到了这篇文章末尾的评论部分才得到启发!另外测试点6不会考虑给的测试例有多个next指针式NULL指针(-1)的情况,有些博客中这种说法是错误的。









测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 360 12/12
1 答案正确 1 232 3/3
2 答案正确 1 360 2/2
3 答案正确 1 232 2/2
4 答案正确 1 232 2/2
5 答案正确 326 8424 3/3
6 答案正确 1 360 1/1

1078. Hashing (25) ::哈希表二次探测法|质数判定


The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be “H(key) = key % TSize” where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (<=104) and N (<=MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

Sample Input:

Sample Output:




  1. 质数的查找。质数查找采用比较取巧的笨办法,1000以下用质数表,1000以上的用土办法(除以 2~根号X一个个试);
  2. 哈希表冲突的解决,题目中明确写了使用Quadratic probing(positive increments only),即序号递增的那种二次探测法。具体细节就不多说了,可以参考这里这里这里。数据结构荒废多年,自己竟然还要查资料,也是挺不好意思的。





测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 360 12/12
1 答案正确 1 360 3/3
2 答案正确 1 232 5/5
3 答案正确 20 360 5/5


1065. A+B and C (64bit) (20)



Given three integers A, B and C in [-263, 263], you are supposed to tell whether A+B > C.

Input Specification:

The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).

Sample Input:

Sample Output:





  • 最终结果符号的判定:如果|a|>=|b|那么结果的符号与a相同,反之符号与b相同;
  • 数值计算,不管正负号,用绝对值大的那个做操作数1,绝对值小的做操作数2,如果a,b同号做操作数1+操作数2,异号做操作数1操作数2





另外给的Sample Input里面那个一长串的就是上限和下限了,加上符号20位足够放。




时间 结果 得分 题目 语言 用时(ms) 内存(kB) 用户
2月22日 20:46 答案正确 20 1065 C++ (g++ 4.7.2) 1 360


测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 360 12/12
1 答案正确 1 360 4/4
2 答案正确 1 360 4/4


PAT 1012. The Best Rank (25)

To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C – C Programming Language, M – Mathematics (Calculus or Linear Algebra), and E – English. At the mean time, we encourage students by emphasizing on their best ranks — that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.

For example, The grades of C, M, E and A – Average of 4 students are given as the following:

Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.


Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (<=2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C, M and E. Then there are M lines, each containing a student ID.


For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.

The priorities of the ranking methods are ordered as A > C > M > E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.

If a student is not on the grading list, simply output “N/A”.

Sample Input

Sample Output







1030. Travel Plan (30)


A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input

Sample Output



using namespace std;

struct Node
vector best_from;
int best_dist;

int best_cost;
int best_cost_from;

vector linkedNodes;

best_dist = 65535;
best_cost = 65535;
best_cost_from = -1;

int main()
int N, M, S, D;
scanf("%d %d %d %d", &N, &M, &S, &D);
int **distances = new int*[N];
int **costs = new int*[N];
Node *nodes = new Node[N];
set working;

for(int i=0; i::iterator it = ptrCurrNode->linkedNodes.begin();
for(; it!=ptrCurrNode->linkedNodes.end(); it++)
int linkedId = *it;
if( working.find(linkedId) == working.end())
Node *ptrLinkedNode = &nodes[linkedId];
int distViaMe = ptrCurrNode->best_dist + distances[last_found_best][linkedId];
int costViaMe = ptrCurrNode->best_cost + costs[last_found_best][linkedId];
if(distViaMe < ptrLinkedNode->best_dist)
ptrLinkedNode->best_dist = distViaMe;

ptrLinkedNode->best_cost = costViaMe;
ptrLinkedNode->best_cost_from = last_found_best;

else if (distViaMe == ptrLinkedNode->best_dist)
if(costViaMe < ptrLinkedNode->best_cost)
ptrLinkedNode->best_cost = costViaMe;
ptrLinkedNode->best_cost_from = last_found_best;
int minDist = 65535;
set::iterator set_it = working.begin();
for(; set_it != working.end(); set_it++)
int id = *set_it;
if( nodes[id].best_dist < minDist) { minDist = nodes[id].best_dist; last_found_best = id; } } set_it = working.find(last_found_best); working.erase(set_it); } //第三步 stack route;
int currIndex = D;
while(currIndex != S)
currIndex = nodes[currIndex].best_cost_from;
printf("%d ", S);
printf("%d ",;
printf("%d %d", nodes[D].best_dist, nodes[D].best_cost);
return 0;


1054. The Dominant Color (20)


Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (<=800) and N (<=600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0, 224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print the dominant color in a line.

Sample Input:

Sample Output:




if Name == 当前的候选人:
if 差额票数==0:
候选人 = Name
差额票数 = 1




int main()
int M, N;
scanf("%d %d", &M, &N);
int resolution = M * N;
int currBest = -1;
int currCount = 1;
for(int i=0; i