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:

 

=====================================================

这道题也没什么技术含量,就是给你一个X列一个Y列,里面要凑出最大的积的和。有个限制条件,就是商品数量有限,所以可以从商品入手。将商品、优惠券全部排序后,从商品的一段开始匹配能产生最大积的优惠券,累计和,如果碰到乘出负数的就掉个头,从末端往回找。因为求快,所以代码写的多了点,估计还能精简…

里面可以看到,某个监测点耗时还挺长的…不过我的原则是够用就好。如果优惠券数量远多于商品的话,考虑只对商品排序,然后找优惠券就行了;反之亦然。

测试点

测试点 结果 用时(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)

http://www.patest.cn/contests/pat-a-practise/1100

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)

http://www.patest.cn/contests/pat-a-practise/1077

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?

 

这个题目就是到着找最长相同子串,没啥难度,用char数组操作很方便,直接给代码

 

PAT 1017. Queueing at Bank (25)

PATEST链接地址:http://www.patest.cn/contests/pat-a-practise/1017

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点之后完成

有两种思路,一种是像http://www.cnblogs.com/Rafy/archive/2012/03/20/2408419.html一样按照一秒一秒tick,还有一种是我的思路,把客户按照时间顺序排序,然后一个个“喂”给窗口。

窗口只需记录当前任务能完成的时间点T1。客户进入时间为T0。喂给窗口时就两个状况:

  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.读取输入,然后链表按其地址存放到map中(当然有猥琐的人可以存放到数组里用空间换时间);

2.按照链表的头指针顺着下去读取链表。建一个栈,当没有达到K个时,每个读取到的值压入栈里,然后集齐K个的时候输出。技巧是一行输出的东西可以分拆分成两块,即除第一行与最后一行特殊外,其他每两行都是:

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

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

也就是说得到当前节点后,只需要补齐上一行的”当前地址”和当前行前两项即可,等到下一个节点读入时再补上这一行的最后一个“下一地址”。

3.最后,末尾别忘了NULL指针“-1”

上面的算法复杂度是O(N)

 

但是请务必考虑下面几个特殊情况:

1. K=1, K=N

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

例如:

这时候的正确输出是:

 


 

代码

 


测试点

(这个结果还有优化的空间,不过既然已经<400ms了我就不管啦~)

测试点 结果 用时(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) ::哈希表二次探测法|质数判定

原题http://www.patest.cn/contests/pat-a-practise/1078

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),即序号递增的那种二次探测法。具体细节就不多说了,可以参考这里这里这里。数据结构荒废多年,自己竟然还要查资料,也是挺不好意思的。

 

我的代码(c++):

 

 


测试点 结果 用时(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)

http://www.patest.cn/contests/pat-a-practise/1065


 

原题如下

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|那么结果的符号与a相同,反之符号与b相同;
  • 数值计算,不管正负号,用绝对值大的那个做操作数1,绝对值小的做操作数2,如果a,b同号做操作数1+操作数2,异号做操作数1操作数2

 

我的代码(好久没写c++,各种复杂,见谅)

其中isBiggerAbs是判断a与b的绝对值大小的,isBigger是判断实际值大小的,swapss是交换元素。

另外0x30是字符’0’的ASCII码来着~输入的时候是按照字符流看待的,计算的时候转换成了数字,然后比较的时候为了和c比方便又转换回去了。

另外给的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.

Input

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.

Output

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

===============================================


又回来做PAT题目了,C++都忘得差不多干净了有没有!下次尝试下提交Python的答案吧~诶嘿嘿

这道题没什么难的,因为它时间要求不高。

我做了个链表把学生成绩的节点连起来,这样是因为学号有6位数(其实要是弄个1000000行的矩阵也没什么了不起的嘛哼!),反正之后就是链表查找的问题了,没啥可说。

 

 

1030. Travel Plan (30)

时间限制:400ms

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

=================================================
这题目嘛是单元最短路径算法的变种,主要变了俩地方:
1.最短路径可能不止1条
2.最后找出最短路中权重cost最小的一个
我不知道我的解法中数据结构是否有冗余的,不过反正是通过了(可能内存多占点吧)
主要就是用Dijkstra算法,但是
1.更新距离组的时候,如果碰到跟当前最好距离一样的,也应该加上
2.多算一个的最佳权重组
,更新条件是:A)发现了更好的距离的时候,直接更新权重组,因为距离是首先要考虑的
B)发现了和现在相同的距离的时候,如果cost比较小,更新一下

这样等Dijkstra算法结束后,我们已经能得到最短距离且权重cost最小的路径了。以前还想着再根据最短距离的各种回溯遍历一下求最小耗费,今天一想其实根本不需要!
算法中还有点不确定的地方,见下面的注释。
====================================================

#include
#include
#include
#include
using namespace std;

struct Node
{
vector best_from;
int best_dist;

int best_cost;
int best_cost_from;

vector linkedNodes;

Node()
{
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_from.clear();
ptrLinkedNode->best_from.push_back(last_found_best);

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

}
else if (distViaMe == ptrLinkedNode->best_dist)
{
ptrLinkedNode->best_from.push_back(last_found_best);
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)
{
route.push(currIndex);
currIndex = nodes[currIndex].best_cost_from;
}
printf("%d ", S);
while(!route.empty())
{
printf("%d ", route.top());
route.pop();
}
printf("%d %d", nodes[D].best_dist, nodes[D].best_cost);
return 0;
}

======================================================

1054. The Dominant Color (20)

时间限制:100ms

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:

==============================
这题目就是个投票选班长的题目,上个学期数据库老师课上讲过(可惜了,数据库后来没考好),瞬间犹如醍醐灌顶~

醍醐灌顶,出于《敦煌变文集·维摩诘经讲经文》:“令问维摩,闻名之如露入心,共语似醍醐灌顶。”佛教指灌输智慧,使人彻底觉悟。比喻听了高明的意见使人受到很大启发。

最笨的办法是每个人画正字,浪费空间,最后还要统计票数
最终的目的是要选出票数最多的一个人,那么可以这样做:

初始化:
班长候选人:叉叉叉
当前差额票数:1
然后拿一张选票,票面上的名字是Name
if Name == 当前的候选人:
差额票数++
else:
差额票数--
if 差额票数==0:
候选人 = Name
差额票数 = 1

这样的话,省时间也省空间:)
原理其实想通了很简单,因为我们只选一个人啊,只算净胜票数就行
净胜票数为0了,那就要被赶下台了!

从测试点的结果来看,的确有个测试点数据量挺大的…估计之前说的笨办法就要超时了..
=================================

#include

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