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 <= 10⁵, and it is guaranteed that all the numbers will not exceed 2³⁰.
Output Specification:
For each test case, simply print in a line the maximum amount of money you can get back.
Sample Input:

4
1 2 4 -1
4
7 6 -2 -3

Sample Output:

43

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

#include <iostream>
using namespace std;
int compare(const void *a, const void *b)
{
	return (*(long*)a > *(long*)b) ? -1 : 1;
}
int main()
{
	int NC, NP;
	cin >> NC;
	long * coupons = new long[NC];
	for (int i = 0; i < NC; i++)
	{
		cin >> coupons[i];
	}
	cin >> NP;
	long * products = new long[NP];
	for (int i = 0; i < NP; i++)
	{
		cin >> products[i];
	}
	qsort(coupons, NC, sizeof(long), compare);
	qsort(products, NP, sizeof(long), compare);
	int nc_index = 0;
	long bonussum = 0;
	for (int i = 0; i < NP; i++)
	{
		if (nc_index >= NC)
			break;
		if (products[i] < 0)
			break;
		long bonus = coupons[nc_index] * products[i];
		if (bonus < 0)
			break;
		bonussum += bonus;
		nc_index++;
	}
	nc_index = NC - 1;
	for (int i = NP - 1; i >= 0; i--)
	{
		if (nc_index < 0)
			break;
		if (products[i] > 0)
			break;
		long bonus = coupons[nc_index] * products[i];
		if (bonus < 0)
			break;
		bonussum += bonus;
		nc_index--;
	}
	cout << bonussum;
	return 0;
}

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

测试点

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:

4
29
5
elo nov
tam

Sample Output:

hel mar
may
115
13

 
这题没什么技术含量，直接给代码（我写的肯定是史上最长哈哈哈）

#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		char* inStr = new char[8];
		scanf("%s", inStr);
		bool isInt = (inStr[0] >= '0' && inStr[0] <= '9');
		if (isInt)
		{
			int value = (int)strtol(inStr, NULL, 10);
			int high = value / 13;
			int low = value - 13 * high;
			switch (high)
			{
			case 0: break;
			case 1: printf("tam"); break;
			case 2: printf("hel"); break;
			case 3: printf("maa"); break;
			case 4: printf("huh"); break;
			case 5: printf("tou"); break;
			case 6: printf("kes"); break;
			case 7: printf("hei"); break;
			case 8: printf("elo"); break;
			case 9: printf("syy"); break;
			case 10:printf("lok"); break;
			case 11:printf("mer"); break;
			case 12:printf("jou"); break;
			default:
				break;
			}
			if (high > 0 && low > 0)
				printf(" ");
			switch (low)
			{
			case 0:
				if(high < 1)
					printf("tret");
				break;
			case 1: printf("jan"); break;
			case 2: printf("feb"); break;
			case 3: printf("mar"); break;
			case 4: printf("apr"); break;
			case 5: printf("may"); break;
			case 6: printf("jun"); break;
			case 7: printf("jly"); break;
			case 8: printf("aug"); break;
			case 9: printf("sep"); break;
			case 10:printf("oct"); break;
			case 11:printf("nov"); break;
			case 12:printf("dec"); break;
			default:
				break;
			}
		}
		else
		{
			bool nextFlag = true;
			int val = 0;
			if (strcmp(inStr, "tam") == 0)
				val = 1;
			else if (strcmp(inStr, "hel") == 0)
				val = 2;
			else if (strcmp(inStr, "maa") == 0)
				val = 3;
			else if (strcmp(inStr, "huh") == 0)
				val = 4;
			else if (strcmp(inStr, "tou") == 0)
				val = 5;
			else if (strcmp(inStr, "kes") == 0)
				val = 6;
			else if (strcmp(inStr, "hei") == 0)
				val = 7;
			else if (strcmp(inStr, "elo") == 0)
				val = 8;
			else if (strcmp(inStr, "syy") == 0)
				val = 9;
			else if (strcmp(inStr, "lok") == 0)
				val = 10;
			else if (strcmp(inStr, "mer") == 0)
				val = 11;
			else if (strcmp(inStr, "jou") == 0)
				val = 12;
			val *= 13;
			int chr = getchar();
			if (chr == ' ')
				scanf("%s", inStr);
			if (strcmp(inStr, "tret") == 0)
				val += 0;
			else if (strcmp(inStr, "jan") == 0)
				val += 1;
			else if (strcmp(inStr, "feb") == 0)
				val += 2;
			else if (strcmp(inStr, "mar") == 0)
				val += 3;
			else if (strcmp(inStr, "apr") == 0)
				val += 4;
			else if (strcmp(inStr, "may") == 0)
				val += 5;
			else if (strcmp(inStr, "jun") == 0)
				val += 6;
			else if (strcmp(inStr, "jly") == 0)
				val += 7;
			else if (strcmp(inStr, "aug") == 0)
				val += 8;
			else if (strcmp(inStr, "sep") == 0)
				val += 9;
			else if (strcmp(inStr, "oct") == 0)
				val += 10;
			else if (strcmp(inStr, "nov") == 0)
				val += 11;
			else if (strcmp(inStr, "dec") == 0)
				val += 12;
			printf("%d", val);
		}
		if (i < N - 1)
			printf("\n");
	}
	return 0;
}

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数组操作很方便，直接给代码

#include <iostream>
#include <string.h>
using namespace std;
bool tryMoveForward(int N, char** sentences, int* posPtr, bool &contFlag)
{
	//尝试当前位置的字符是否相同
	char chr = sentences[0][posPtr[0]];
	bool flag = true;
	int i = 0;
	while(i < N)
	{
		if (sentences[i][posPtr[i]] != chr)
		{
			flag = false;
			break;
		}
		i++;
	}
	if (flag)
	{
		//Move forward
		for (i = 0; i < N; i++)
		{
			posPtr[i] --;
			if (posPtr[i] <0)
				contFlag = false;
		}
	}
	return flag;
}
int main()
{
	int N;
	cin >> N;
	char **sentences = new char*[N]; //存储句子
	int* posPtr = new int[N];	//当前位置指针
	//int maxSuffixStartPos = 0; //最长子串起始位置(距离最后一个字符)
	cin.ignore(1);
	for (int i = 0; i < N; i++)
	{
		sentences[i] = new char[257];
		//cin >> sentences[i];
		cin.getline(sentences[i], 257);
		posPtr[i] = strlen(sentences[i]) - 1;
	}
	bool contFlag = true;
	while (contFlag)
	{
		bool movFlag = tryMoveForward(N, sentences, posPtr, contFlag);
		contFlag &= movFlag;
	}
	//读取最长字串
	int longSufPos = posPtr[0];
	if (longSufPos == strlen(sentences[0]) - 1)
		cout << "nai";
	else
	{
		char* result = sentences[0] + longSufPos + 1;
		cout << result;
	}
	return 0;
}

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；

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
struct Customer
{
	int comeInTime; //到达时间（秒）
	int processingTime; //处理时间（秒）
};
int* nextAvailableTime; //窗口的下个可用时间点，用秒记录
Customer* customers;
int N, K, N_valid;
int compareCustomers(const void* c1, const void* c2)
{
	//时辰早的排在前面
	Customer* C1 = (Customer*)c1;
	Customer* C2 = (Customer*)c2;
	return C1->comeInTime - C2->comeInTime;
}
int getNextAvailable(Customer c)
{
	//找到下个可用窗口，返回等待时间
	int minTime = 100000; //这个值不能是17:00:00(61200),至少得是86400，因为有可能17点之前来的顾客会等到17点之后...;
	int minIndex = -1;
	for (int i = 0; i < K; i++)
	{
		if (nextAvailableTime[i] < minTime)
		{
			minTime = nextAvailableTime[i];
			minIndex = i;
		}
	}
	if (nextAvailableTime[minIndex] < c.comeInTime)
	{
		//之前就已经空窗；
		nextAvailableTime[minIndex] = c.comeInTime + c.processingTime;
		return 0;
	}
	else
	{
		int waitTime = nextAvailableTime[minIndex] - c.comeInTime;
		nextAvailableTime[minIndex] += c.processingTime;
		return waitTime;
	}
}
int main()
{
	scanf("%d %d", &N, &K);
	customers = new Customer[N];
	nextAvailableTime = new int[K];
	for (int i = 0; i < K; i++)
		nextAvailableTime[i] = 8 * 3600; // 8:00:00
	N_valid = N;
	for (int i = 0; i < N_valid; i++)
	{
		int hh, mm, ss, procTime;
		scanf("%d:%d:%d %d", &hh, &mm, &ss, &procTime);
		if (hh >= 17 && mm >= 0 && ss > 0)
		{
			N_valid--;
			i--;
			continue;
		}
		else
		{
			customers[i].comeInTime = hh * 3600 + mm * 60 + ss;
			if (procTime > 60)
				procTime = 60;
			customers[i].processingTime = procTime * 60;
		}
	}
	//对有效顾客排序
	qsort(customers, N_valid, sizeof(Customer), compareCustomers);
	int waitTimeSum = 0; //(秒)
	for (int i = 0; i < N_valid; i++)
	{
		waitTimeSum += getNextAvailable(customers[i]);
	}
	float waitTimeAvg = waitTimeSum / 60.0 / (float)N_valid;
	printf("%.1f", waitTimeAvg);
	return 0;
}