1、已知两个数字为1~30之间的数字，甲知道两数之和，乙知道两数之积，甲问乙：“你知道是哪两个数吗？”乙说：“不知道”。乙问甲：“你知道是哪两个数吗？”甲说：“也不知道”。于是，乙说：“那我知道了”，随后甲也说：“那我也知道了”，这两个数是什么？
答：1和4 或者1和7
2、一个环形公路，上面有Ｎ个站点，A1, …, AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。
高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)
它给出了部分代码如下：
#define N 25
double D[N]
….
void Preprocess()
{
//Write your code1;
}
double Distance(int i, int j)
{
//Write your code2;
}
[cpp] view plaincopyprint
const int N = 10;
int D[N];

int A1toX[N];

void Preprocess()
{
srand(time(0));

for (int i = 0; i < N; ++i)
{
D[i] = (rand()/(RAND_MAX+1.0)) * N;
}

A1toX[1] = D[1]; //from A1 to A2
for (int i = 2; i < N; ++i)
{
A1toX[i] = A1toX[i-1] + D[i]; //distance from A1 to each point
}
A1toX[0] = A1toX[N-1] + D[0]; // total length
}

int distance(int i, int j)
{
int di = (i == 0) 0 : A1toX[i-1];
int dj = (j ==0) 0 : A1toX[j-1];
int dist = abs(di - dj);
return dist > A1toX[0]/2 A1toX[0] - dist : dist;
}

int main(void)
{
Preprocess();
for (int i = 0; i {
cout< }
cout< for (int i = 1; i <= N; ++i)
{
cout<<"distance from A1 to A"< }
return 0;
}

3、 一个字符串，压缩其中的连续空格为1个后，对其中的每个字串逆序打印出来。比如"abc efg hij"打印为"cba gfe jih"。
[cpp] view plaincopyprint
#include
#include
#include
#include
using namespace std;

string reverse(string str)
{
stack stk;
int len = str.length();
string ret = “”;

for (int p = 0, q = 0;p < len;)
{
if (str[p] == ‘ ‘)
{
ret.append(1,’ ‘);
for (q = p; q < len && str[q] == ‘ ‘; q++)
{}
p = q;
}
else
{
for (q = p; q < len && str[q] != ‘ ‘; q++)
{
stk.push(str[q]);
}
while(!stk.empty())
{
ret.append(1,stk.top());
stk.pop();
}
p = q;
}
}
return ret;
}
int main(void)
{
string s = “abc def ghi”;
cout< return 0;
}

4、将一个较大的钱，不超过1000000(10^6)的人民币，兑换成数量不限的100、50、10、5、2、1的组合，请问共有多少种组合呢？（完全背包）（其它选择题考的是有关：操作系统、树、概率题、最大生成树有关的题，另外：谷歌不给人霸笔的机会。）。