时间限制

10
-10 1 2 3 4 -5 -23 3 7 -21

10 1 4

==============================================
这是一个经典问题，可以利用《编程珠玑》第8章<算法设计技术>里面的扫描算法
算法不写了，书上一模一样的原题，伪代码如下:

maxsofar = 0
maxendinghere = 0
for i = [0,n)
    /* invariant: maxendinghere and maxsofar
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxendinghere, maxsofar)

只不过这里输出的时候要输出首末位置的数字，所以加了一些变量。
什么时候会改变首末位置呢：
1. maxEndingHere == 0的时候，表示如果后面还会有更好的结果的话，肯定开始的位置是从这个点之后的一个数字开始的。此时要记录可能会产生gap，留给后续处理
2.当到达vStartIndex，别忘了记下<可能的>新的起点
3.当后面那一坨真的比原来的值还大时，如果存在gap，那要用新的起点替换掉旧的，然后吧gap开关关上，一个新的开始
4.当算出来总数maxEndingHere比maxSofar大时，别忘了记下当前位置的数值作为末尾数值
另外要注意，如果全是负值怎么处理，特别注意这样的输入，不能以maxSofar是否>0判断

3
-1 0 -1

代码中startIndex与endIndex是不必要存储的。
=============================================

#include 
#include  //max
using namespace std;
int main()
{
	int N;
	scanf("%d", &N);
	long maxSofar = 0;
	long maxEndingHere = 0;
	int startVal = 0;
	int startIndex = -1;  //
	int vStartIndex = 0;//
	int vStartVal = 0;
	int endIndex = -1;//
	int endVal = 0;
	bool hasGap = true;
	bool allNegative = true;
	//int *savedVals = new int[N];
	int totalStartVal;
	int totalEndVal;
	for(int i=0; i= 0 && allNegative)
			allNegative = false;
		if(i==0)
			totalStartVal = inputVal;
		else if(i == N-1)
			totalEndVal = inputVal;
		//savedVals[i] = inputVal;
		maxEndingHere = max( maxEndingHere + inputVal, (long)0);
		if(maxEndingHere == 0)
		{
			hasGap = true;
			vStartIndex = i+1;
		}
		if(i == vStartIndex)
			vStartVal = inputVal;
		if( maxEndingHere > maxSofar)
		{
			maxSofar = maxEndingHere;
			endIndex = i;
			endVal = inputVal;
			if(hasGap)
			{
				startIndex = vStartIndex;
				startVal = vStartVal;
				hasGap = false;
			}
		}
	}
	if(!allNegative)
		printf("%ld %d %d", maxSofar, startVal, endVal);
	else
		printf("%ld %d %d", maxSofar, totalStartVal, totalEndVal);
	return 0;
}

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 0 750 2/2
1 答案正确 0 790 1/1
2 答案正确 0 790 3/3
3 答案正确 0 790 4/4
4 答案正确 0 790 4/4
5 答案正确 0 790 3/3
6 答案正确 0 790 3/3
7 答案正确 0 750 5/5

1027. Colors in Mars (20)

15 43 71

#123456

===============================
没啥技术含量。
===============================

#include 
#include 
using namespace std;
string GetRGBVal(int val)
{
	char ret[3];
	ret[2] = '';
	int count = 1;
	while( count >= 0)
	{
		if(val == 0)
			ret[count] = '0';
		int temp = val % 13;
		if(temp >9)
		{
			temp -= 10;
			temp += 0x41;
		}
		else
			temp += 0x30;
		val /= 13;
		ret[count--] = (char)temp;
	}
	return string(ret);
}
int main()
{
	int rgb[3];
	cin >> rgb[0] >> rgb[1] >> rgb[2];
	cout << "#";
	for(int i=0; i<3; i++)
	{
		cout << GetRGBVal(rgb[i]);
	}
	return 0;
}

1039. Course List for Student (25)

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0

=================================
PAT上通过率0.09的题目看着挺可怕
主要是时间的问题我想，做那么多次查询~
第一想法是直接用STL的map给名字做索引
这样的话搜索效率是O(log2n)，因为map是用神马树实现的
不过…后来想想这个题目那么多跪了的，估计肯定不能用这个
只能拿空间换时间了~
权衡了一下，因为姓名是3个字母加1个数字，所以可以自己写个浪费空间的Hash函数，将名字的字母部分映射成数组的索引
哈希了一下嘛，时间复杂度就是O(1)了，邪恶一笑…
数组使用map>实现，显然前面那个int就是给字母最后的数字使用的，后面那个存的course的ID
这样可能稍微能节约点空间，不然26*26*26*10需要175760那么多地方…浪费地有点多
其他没有什么可以说的，里头有现成的sort，专门对付STL容器里头的排序，自己写个compare函数就行了，相当方便。
提交一次通过，虽然最长时间是180ms有点危险，不过不想再去折腾这个了。
==================================

#include 
#include 

==========================================
测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 0 1250 15/15
1 答案正确 0 1380 2/2
2 答案正确 0 1380 2/2
3 答案正确 0 1380 2/2
4 答案正确 0 1380 2/2
5 答案正确 180 21700 2/2

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.
Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

=================================
数据结构是个好东西。
输入的序列1,2,3，…，N其实是（废话本来就是）一个队列(下面记作seq)，然后在弄一个容易被填满的栈…
以下栈底、队首用#号标识
然后看测试的序列，比如5 6 4 3 7 2 1，
1.先看栈顶元素，如果栈顶元素就是输入的元素的话，那就弹栈，然后继续循环
2.如果不是，那么就要将队列的头一直取出，填到栈里面，
直到：(A)栈满了，那么失败了
(B)现在栈顶的元素就是我们的输入元素，那么继续读下一个测试的数字
测试序列5 6 4 3 7 2 1中，一开始的元素是5，于是不断的从1234567这个队列中取头部出来，压栈，然后
栈S : #1 2 3 4 5
seq: # 6 7
满足调节后，下一个循环查看的时候，发现栈顶的5刚好是我们的输入元素，于是序列指针移到6上面，并且弹出5，
经过差不多的过程，变成这样
栈S : #1 2 3 4 6
seq : #7
之后这样
栈S : #1 2 3 4
seq : #7
,
栈S : #1 2 3
seq : #7
,
栈S : #1 2
seq : #7
,
栈S : #1 2 7
seq : #
,
栈S : #1 2
seq : #
,
。。。直到尽头，然后成功了
=======================================================
具体实现可能跟刚才的说法略有不一致，但是原理是一样的。

#include 
#include 
#include 
using namespace std;
int main()
{
    int M, N, K;
    queue sequences;
    queue copy_of_seq; //为了防止重复生成浪费时间
    scanf("%d %d %d", &M, &N, &K);
    //生成seq队列
    for(int i=1; i s;
        bool failed = false;
        int input_val;
        for(int i=0; i= M) //要留一个给后面再读入的相等的元素
                {
                    failed = true;
                    break;
                }
            }
            if( failed )
            {
                printf("NOn");
            }
            else if( copy_of_seq.empty() )
            {
                failed = true;
                printf("NOn");
            }
            else
            {
                //成功了..
                //s.push( copy_of_seq.front() ); (反正还要pop，不搞了)
                copy_of_seq.pop();
            }
            //如果头部还是与数字不同，那就fail
        }
        if (!failed)
            printf("YESn");
    }
    return 0;
}

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 0 740 15/15
1 答案正确 0 750 3/3
2 答案正确 0 790 2/2
3 答案正确 0 790 2/2
4 答案正确 0 750 1/1
5 答案正确 0 780 2/2

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
Given two increasing sequences of integers, you are asked to find their median.
Input
Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.
Output
For each test case you should output the median of the two given sequences in a line.
Sample Input

4 11 12 13 14
5 9 10 15 16 17

Sample Output

13

====================================
这题其实没什么技术含量，因为输入序列都帮你排序好了，时间内存都没啥限制
要注意的一点就是，假定输入序列为A,B，当A或B某个已经被掏空时，需要另外处理，不然就会报段错误什么的…
在优化方面，其实可以先读第一个序列进队列，第二个序列读入时直接处理而不存储，能比原来节省一半空间。
由于题目比较松，没有做这方面处理。
====================================

#include 
#include 
using namespace std;
int main()
{
	///////////Init
	queue q_a ,q_b;
	long N1, N2; //两个序列的长度
	//不存储第二个序列，直接用来比较处理
	///////////
	//读第一个序列
	scanf("%ld", &N1);
	long temp;
	for(long i=0; i
另外测试结果比较恐怖，哈哈

测试点	结果	用时(ms)	内存(kB)	得分/满分

0	答案正确	0	660	4/4

1	答案正确	0	790	2/2

10	答案正确	320	17270	3/3

11	答案正确	320	17260	1/1

12	答案正确	320	17260	3/3

13	答案正确	0	740	1/1

2	答案正确	0	740	4/4

3	答案正确	0	750	1/1

4	答案正确	0	790	1/1

5	答案正确	0	750	1/1

6	答案正确	150	9000	1/1

7	答案正确	160	9000	1/1

8	答案正确	160	9010	1/1

9	答案正确	150	8870	1/1

		

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.
Input Specification:
Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.
Output Specification:
For each test case, print the total time on a single line.
Sample Input:

3 2 3 1

Sample Output:

41

==============================================
此题初看还以为是电梯算法，其实啥都不是。。。。
注意的是第一个输入的数字是后面的总的输入个数，不是别的其他什么…
答案也很短…好久没碰到这么简单的了
==============================================

#include 
using namespace std;
int main(int argc, char* argv[])
{
	int N;
	cin >> N;
	int floor_now = 0; //当前在0层
	int next_floor = 0;
	int total_time = 0;
	for(int i=0; i> next_floor;
		int time_per_floor = (next_floor - floor_now > 0) ? 6 : -4; //上楼还是下楼
		total_time = total_time + time_per_floor * (next_floor - floor_now) + 5;
		floor_now = next_floor;
	}
	cout << total_time;
	return 0;
}

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.
Input Specification:
Each input file contains one test case. Each case contains a positive integer N (<= 1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.
 
Output Specification:
For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line “There are N accounts and no account is modified” where N is the total number of accounts. However, if N is one, you must print “There is 1 account and no account is modified” instead.
Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa

Sample Input 2:

1
team110 abcdefg332

Sample Output 2:

There is 1 account and no account is modified

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333

Sample Output 3:

There are 2 accounts and no account is modified

======================================
这题没啥技术含量，直接发代码

#include 
#include 
using namespace std;
int main()
{
	int N;
	scanf("%d", &N);
	bool isModified = false;
	int modCount = 0;
	char name[11], pswd[11];
	char *ptrPswd;
	string strOut;
	for(int i=0; i