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

		

Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification:
Each input file contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification:
For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.
Sample Input:

1234567899

Sample Output:

Yes
2469135798

====================================
恩恩，having fun….
这道题的险恶用心在于..
int最大值 2147483647
longlong 最大值 9223372036854775807
都不满足20位的标准…因此需要自己手工做乘法计算~
其实乘法也是很好算的嘛~喵
还好时间给的充裕…
====================================

#include 
using namespace std;
char digs_in[20];
int digs_out[30];
short old_nums[10];
short new_nums[10];
int main()
{
	cin >> digs_in;
	//find ''
	int pos = 0;
	while(true)
	{
		if(digs_in[pos++] == '')
			break;
	}
	pos--;
	//手工做*2...
	int r = 0;
	int d = 0;
	int count = 0;
	while (pos--)
	{
		d = (int)digs_in[pos] - 0x30;  //ASCII -> digit
		old_nums[d] ++;
		d = d << 1; //d*=2
		d += r;
		r = d / 10;
		d = d % 10;
		digs_out[count++] = d;
		new_nums[d] ++;
	}
	if( r > 0)
	{
		//最高位
		digs_out[count] = r;
		new_nums[r] ++;
	}
	else
		count --;
	bool flag = true;
	for(int i=0; i<10; i++)
	{
		if(old_nums[i] != new_nums[i])
		{
			flag = false;
			break;
		}
	}
	if(flag)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	for(int i=count; i>=0; i--)
		cout << digs_out[i];
	return 0;
}

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N > 0 in base b >= 2, where it is written in standard notation with k+1 digits a_i as the sum of (a_ibⁱ) for i from 0 to k. Here, as usual, 0 <= a_i < b for all i and a_k is non-zero. Then N is palindromic if and only if a_i = a_k-i for all i. Zero is written 0 in any base and is also palindromic by definition.
Given any non-negative decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.
Input Specification:
Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 10⁹ is the decimal number and 2 <= b <= 10⁹ is the base. The numbers are separated by a space.
Output Specification:
For each test case, first print in one line “Yes” if N is a palindromic number in base b, or “No” if not. Then in the next line, print N as the number in base b in the form “a_k a_k-1 … a₀“. Notice that there must be no extra space at the end of output.
Sample Input 1:

27 2

Sample Output 1:

Yes
1 1 0 1 1

Sample Input 2:

121 5

Sample Output 2:

No
4 4 1

===========================
最近产量太低，都是有小bug的答案，唯独这道题终于。。。。
其实这道题相当简单，不想说啥了
时间空间都没有限制，如果机试碰到这种题，那估计是八辈子修来的福。。。
直接贴答案吧。。
===========================

#include 
using namespace std;
long resultSize = 0;
const int MAX_BUFF_SIZE = 30;
int buff[MAX_BUFF_SIZE];
void calcBase(long inputVal, long base)
{
	//计算以base为低的inputVal的值
	if(inputVal == 0)
	{
		resultSize = 1;
		buff[0] = 0;
		return;
	}
	resultSize = 0;
	while(inputVal > 0)
	{
		buff[resultSize++] = inputVal % base;
		inputVal /= base;
	}
}
bool isPalindrome()
{
	long limit = resultSize /2;
	for(long i=0; i> a >> b;
	calcBase(a, b);
	if( isPalindrome())
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	while(--resultSize)
	{
		cout << buff[resultSize] << " ";
	}
	cout << buff[0];
	return 0;
}

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is “yes”, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number “radix” is the radix of N1 if “tag” is 1, or of N2 if “tag” is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print “Impossible”. If the solution is not unique, output the smallest possible radix.
Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

=================================================================
貌似是浙大PAT通过率最低的一题，6%
一开始很不解，为啥通过率这么低，明明是很容易读和做的一题，而且内存、时间都挺宽裕。
做起来才发现，对于我来说有这些问题：
1）思维定势。一开始误以为只可能进制到36为止，因为题目输入的一个数的进制最高只能到36，后来想想，这货是无穷无尽的，
假定A为已知进制为r1的数，B为待测进制(r2)的数，那么当第一次遇到r2, s.t. B@r2 > A@r1时，才是终止条件。
2）收敛速度。解决问题1后，竟然尼玛有一个运行超时了，仔细想想，r2按照线性递增测算的话，遇到以下输入将会是无穷无尽的时间才能判断
e.g.

zzzzzzzzzz 1 1 36

所以r2肯定不能一个一个来。
然后写了个简单的回溯，弄了个加速度的东西accRate，具体见代码》。如果一路成功会越走越快，如果遇到失败，那么退回backup的值，然后加速度回到1，然后继续。粗略一算这货的收敛速度或许是log级别的，直接放到pat判题，然后全过了:)
另外，发现c++用里面的pow算乘方其实挺快的，本来以为速度慢在这里，呵呵。
还有使用long long是因为按照题目的限定来说，最大的数 zzzzzzzzzz 放在一个long里面似乎不够用…当然用double或许可以，不过…浮点运算对cpu来说是个恐怖的事情吧
=================================================================
以下是
我的参考答案，肯定不是最好的
里面有些不必要的东西，懒得删了。
：

#include 
#include 
#include 
#include 
using namespace std;
char *N1, *N2;
long tag, radix;
long valueOfChar(char c)
{
	//get the value of a char
	//0~9,a-z
	long iC = (long)c;
	if(iC >= 0x30 && iC <= 0x39)
		return iC - 0x30;
	else if(iC >=0x61 && iC <= 0x7a) //a-z
		return iC - 0x57;
	else //wrong input
	{
		cerr << "??? " << c < 1
		int X = valueOfChar(input[0]);
		long long Z = X * pow(radix, size-1);
		return Z + getDecVal(input+1, radix, size-1);
	}
}
long getMinPossibleRadix(char* input)
{
	//获得最小可能的基数
	long maxDigit = 0;
	long nowDigit;
	while( (*input) != '')
	{
		nowDigit = valueOfChar((*input));
		if(nowDigit > maxDigit)
			maxDigit = nowDigit;
		input ++;
	}
	return maxDigit + 1;
}
char *trial;
int main()
{
	clock_t start,mid;
	N1 = new char[10];
	N2 = new char[10];
	long minPossibleRadix;
	cin >> N1 >> N2 >> tag >> radix;
	start = clock();
	long long lDecVal;
	if( tag == 1)
	{
		lDecVal = getDecVal(N1,radix);
		minPossibleRadix = getMinPossibleRadix(N2);
		trial = N2;
	}
	else
	{
		lDecVal = getDecVal(N2,radix);
		minPossibleRadix = getMinPossibleRadix(N1);
		trial = N1;
	}
	long long rVal = -1;
	int strSize = strlen(trial);
	long long accRate = 1;//加速度
	long long i= minPossibleRadix;
	long long backup = i;
	bool inTrial = false; //正在尝试的状态
	while(true)
	{
		rVal = getDecVal(trial,i,strSize);
		if(rVal == lDecVal)
		{
			cout << i;
			//mid = clock();
			//cout << mid - start << endl;
			return 0;
		}
		else if(rVal > lDecVal)
		{
			if(!inTrial)
				break;
			else
			{
				//回溯
				inTrial = false;
				if( i == backup + 1)
					break;
				i = backup;
				accRate = 1;
			}
		}
		else
		{
			inTrial = true;
			backup = i;
			i += accRate;
			accRate *= 10;
			//cout << i << endl;
		}
	}
	mid = clock();
	//cout << mid - start << endl;
	cout << "Impossible";
	return 0;
}

1004. Counting Leaves (30)

ID K ID[1] ID[2] ... ID[K]

2 1
01 1 02

0 1

======================================================
恩恩，数叶子，倒腾了一晚上，一直报段错误，最后知道真相的我眼泪掉下来》。。
原来是指针指来指去，本来要指子节点的ID结果弄成了自己的ID，然后数组就不对了》。。
思路比较简单，他要hierarchy，我们就搞一个
他要Node，我们就弄个结构给他
Node之间用指针传上就行了..虽然带两个*号的东西好久没用了，但是心里想着这货是指针的数组就行了…
为了节约时间，最后找结果的时候用的静态数组100*100，比较无耻，反正题目给够了内存…
每一行计算的时候，把自己的孩子加到数组的下一行里面，搜索到世界的尽头…然后就结束了
=======================================================

#include 
using namespace std;
struct Node
{
	Node **childNodes; //array of ptrChilds
	int ID; //ID  = array index + 1 ??
	int childSize;
	int nowIndex; //If nowIndex ==0 , this node must be a childless one.
	//int level; //root level = 0
	Node(int id, int cSize = 100)
	{
		ID = id;
		childSize = cSize;
		childNodes = new Node*[childSize];
		nowIndex = 0;
	}
	bool insertChildNode(Node* pNode)
	{
		if(nowIndex > childSize)
		{
			cerr << "child over size!" << endl;
			return false;
		}
		childNodes[nowIndex++] = pNode;
		return true;
	}
};
static int M,N;
static Node** allNodes;
static int lvls[100][100] = {0};
int main()
{
	//--First line
	cin >> N;
	cin >> M;
	//--init Node* array
	if(N == 0 || M == 0)
	{
		cout << "1";
		return 0;
	}
//We presume that there is no gap between IDs (eg: 01 02 05 06 07)
//otherwise we need to create more new Nodes
	allNodes = new Node*[N];
	for(int i=0; ilevel = 0; //root node level
	//--read M lines for the child info
	int id, K;
	for(int line=0; line> id;
		id--;  //turn to the index
		Node* pParent = allNodes[id];
		cin >> K;
		int cId;
		while(K > 0)
		{
			//link every child
			cin >> cId;
			cId --;
			pParent->insertChildNode(allNodes[cId]);
			K--;
		}
	}
	//--finished reading
	Node* root = allNodes[0];
	//--init first line
	if(root->nowIndex == 0)
	{
		cout << 1;
		return 0;
	}
	else
	{
		cout << 0;
	}
	for(int i=0; inowIndex ; i++)
	{
		Node* childNode = root->childNodes[i];
		lvls[0][i] =childNode->ID -1;
	}
	//GOGOGO!!!
	int row=0, col=0;
	int nextColOffset = 0;
	int count = 0;
	while(true)
	{
		int posNow = lvls[row][col];
		if( posNow == 0)
		{
			if(col == 0)			//end of all things
				break;
			row ++;
			col = 0;
			cout << " " << count;
			count = 0; //reset line count
			nextColOffset = 0;
			continue; //move to the head of next line
		}
		Node* now = allNodes[posNow];
		if(now->nowIndex <= 0)
			count ++;
		else
		{
			//put its children into next line
			for(int i=0; inowIndex; i++)
			{
				lvls[row+1][nextColOffset++] = now ->childNodes[i] ->ID -1;
			}
		}
		col ++;
	}
	return 0;
}

1050. String Subtraction (20)
时间限制
10 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
Given two strings S1 and S2, S = S1 – S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1 – S2 for any given strings. However, it might not be that simple to do it fast.
Input Specification:
Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than 104. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.
Output Specification:
For each test case, print S1 – S2 in one line.
Sample Input:

They are students.
aeiou

Sample Output:

Thy r stdnts.

===================================================
不用动啥脑子的一道题，只要避免使用cin/cout就行了。反正内存给了好大好大，要争取时间的话，就给一共128个ascii字符做个map，里面存放是不是被ban掉了。
===================================================

#include 
using namespace std;
static char S1[10000];  //S1
static char S2[10000];  //S2
static char S3[10000];  //result
static bool mapAscii[127];
int main()
{
	char* pS1 = &S1[0];
	char* pS2 = &S2[0];
	gets(pS1);
	gets(pS2);
	int asc;
	while( (*pS2) != '')
	{
		asc = (int)(*pS2);
		mapAscii[asc] = true;
		pS2++;
	}
	char* pS3 = &S3[0];
	while( (*pS1) != '')
	{
		asc = (int)(*pS1);
		if(!mapAscii[asc])
		{
			(*pS3) = (char) asc;
			pS3++;
		}
		pS1++;
	}
	(*pS3) = ''; // EOL
	puts(&S3[0]);
	//system("pause");
	return 0;
}

一道难题？主要是木有方法。

1041. Be Unique (20)

7 5 31 5 88 67 88 17

31

5 888 666 666 888 888

None

本人解答：

//#include 
//#include 
#include 
#include 
using namespace std;
const int MAX_NUM_A = 10001;
//const int MAX_NUM_B = 10000;
int storage[MAX_NUM_A] = {0};
//list possibles;
int possibles[MAX_NUM_A] = {0};
//0代表尚未存储，-1代表已经超额，其余代表输入时的顺序（第几个输入的这个数）
//int sequence[MAX_NUM_B];
//list ary_list;
/*
inline void remove(int r)
{
	//remove item from array
	ary_list.remove(r);
}
*/
int main()
{
	clock_t  clockBegin, clockMid, clockEnd;
	int possibleN = 0;
	int N;
	//cin >> N;
	scanf("%u",&N);
	int input;
	clockBegin = clock();
	for (int i=0; i> input;
		scanf("%u", &input);
		if(storage[input] == 0)
		{
			//尚未输入过这个数
			storage[input] = i+1; //记录输入的顺序
			//possibleN ++;
			//possibles.push_back(input);
			possibles[possibleN++] = input;
		}
		else
		{
			//重复了！
			//if(storage[input] > 0)
			//{
				//possibles.remove(input);
				//possibleN --;
			//}
			storage[input] = -1;
		}
	}
	/*
	if(possibles.size() <= 0)
	{
		cout << "None";
		return 0;
	}
	*/
	clockMid = clock();
	//cout << clockMid - clockBegin << endl;
	printf("%un",clockMid - clockBegin);
	//int count = ary_list.size();
	int min_seq = MAX_NUM_A;
	int min_val = -1;
	int i=0;
	while(i < possibleN)
	{
		int temp = storage[possibles[i]];
		if(temp > 0)
		{
			//if(temp < min_seq)
			//{
				min_seq = temp;
				min_val = possibles[i];
				break;
			//}
		}
		//possibles.pop_front();
		i ++ ;
	}
	clockEnd = clock();
	//cout << clockEnd - clockMid << endl;
	printf("%un",clockEnd - clockMid);
	if(min_val != -1)
	{
		//cout << min_val;
		printf("%u",min_val);
		return 0;
	}
	//cout << "None";
	printf("None");
	return 0;
}

知道结论是什么么？
结论是sscan比cin效率高很多！