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效率高很多！