先吐槽一下，学校的机房。我严重怀疑学校机房的VS2010是不是坏的，折腾了半天，一个测试的hello world程序都不能跑。最后，二十多分钟之后，我放弃了，果断选择了VC6.0.虽然很多东西编译不过，但是没办法啊。唉，结果最后人家性格测试都做完了，我才做了1/3。性格测试就不吐槽了。
OK，废话不多说了，本来是可以三道题都做完的，结果最后一道题，scanf的时候，scanf("%d", &map[i][j]);写成了scanf("%d", &map);回来才发现的啊，我都想扇自己两下。（咳咳，貌似有点暴力了）。觉得好的话，默默顶一下？妹纸码字也不容易哈~
第一题解析：
其实就是排序算法嘛，直接快排，比较好些，效率也可以，没什么好说的。这道题的难点在于输入的时候，是以字符串形式输入，然后事先不知道当前这一次排序有多少个数字，所以需要一点技巧。废话不多说，直接上代码，时间紧急，可能不是很漂亮。
void quickSort(int *arr, int nLen)第二题解析
{
if(arr == NULL || nLen < 1)
return;
int Begin = 0;
int End = nLen - 1;
int key = arr[Begin];
while(Begin < End)
{
while(Begin < End && arr[End] >= key)
--End;
if(Begin < End)
arr[Begin++] = arr[End];
while(Begin < End && arr[Begin] < key)
++Begin;
if(Begin < End)
arr[End--] = arr[Begin];
}
arr[Begin] = key;
quickSort(arr, Begin);
quickSort(arr + Begin + 1, nLen - Begin - 1);
}
void Print(int *arr, int nLen)
{
if(arr == NULL || nLen < 1)
return;
printf("%d", arr[0]);
for(int i = 1; i < nLen; ++i)
{
printf(",%d", arr[i]);
}
printf("\n");
}
int main()
{
const int max_len = 1030;
const int size = 130;
char str[max_len];
int arr[size];
int nLen,i;
while(gets(str))
{
nLen = 0;
i = 0;
while(str[i] != '\0')
{
sscanf(&str[i], "%d", &arr[nLen]);
++nLen;
while(str[i] != '\0' && str[i] != ',')
++i;
if(str[i] == ',')
++i;
}
quickSort(arr, nLen);
Print(arr, nLen);
}
return 0;
}
这个丑数，也没什么好说的。我写的是最2的一种方法，当然可以用3个队列进行优化。其实题目变一下，就是一个OJ的题，比如说，求因子只有{2,3,5,7}的第n个数是多少。最好用队列解，效率高。这里，由于数字可能比较大，所以需要用unsigned long long类型，不过坑爹的VC6.0是不能编译过的，害得我写好了发给别人远程帮我编译一下，好坑！上代码：
bool IsTrue(unsigned long long num)第三题解析：
{
while(num % 2 == 0)
num /= 2;
while(num % 3 == 0)
num /= 3;
while(num % 5 == 0)
num /= 5;
return num == 1;
}
int main()
{
const int size = 501;
unsigned long long arr[size];
unsigned long long base = 1;
int count = 0;
while(count < size)
{
if(IsTrue(base))
{
arr[count++] = base;
}
++base;
}
int n;
while(scanf("%d", &n) != EOF)
{
if(n < 1 || n > 500)
printf("-1\n");
else
printf("%d\n", arr[n - 1]);
}
return 0;
}
其实这是一个深搜问题，不过呢，你可以看到题目截图中有答案提示：城市数目较多，因此不能使用完全遍历，无法满足时间复杂度要求。所以需要对数据做一下预处理，也就是将map转换为链表形式的，本来map应该是只有0,1的值，表示有路径或者没路径。不过为了节约点内存（虽然没什么必要），所以map复用。当前节点i如果和另外的节点j相连，则将节点j放在map中。第0个元素存放当前访问到第几个节点（从1开始，深搜回溯的时候有用），后面依次存放与之相邻的节点，最后以-1结束。
map转化完成之后，剩下的就是深搜了。不明白？直接看代码吧。想到那个scanf的错误，我现在都伤心啊......
#include<stdio.h>贴出三道题的题目图片：
#include<string.h>
int main()
{
const int N = 10;
int map[N][N];
int stack[N];
bool visited[N];
int n,a,b;
int Begin;
int i,j;
while(scanf("%d %d %d", &n, &a, &b) != EOF)
{
for(i = 0; i < n; ++i)
{
for(j = 0; j < n; ++j)
{
scanf("%d", &map[i][j]);
}
}
for(i = 0; i < n; ++i)
{
int index = 0;
map[i][0] = 1;
for(j = 0; j < n; ++j)
{
if(map[i][j] && i != j)
map[i][++index] = j;//记录下可达的点
}
map[i][++index] = -1;//-1结束
}
//深搜
memset(visited, 0, N * sizeof(bool));
int top = -1;
int ans = 0;
stack[++top] = a;//a入栈
visited[a] = true;
while(top > -1)//栈不空
{
Begin = stack[top];//取栈顶元素
for(i = map[Begin][0]; map[Begin][i] != -1; ++i)
{
if(map[Begin][i] != b && !visited[map[Begin][i]])//未访问过
{
stack[++top] = map[Begin][i];
visited[map[Begin][i]] = true;
map[Begin][0] = i + 1;
break;
}
if(map[Begin][i] == b)
++ans;
}
if(map[Begin][i] == -1)//这个点的所有路径都走过了，退栈
{
--top;
}
}// end for while
printf("%d\n", ans);
}
return 0;
}
题目编号一次为1，2,3；
