几道中南大学考研机试题
哪位老哥大神能告诉我每道题考得什么算法
要是能求解，上代码就更好了。谢谢帮助
题目 B（20 分）
问题描述：
有一个愚蠢的机器人走进了一个 w*h 的迷宫，迷宫里有空地和陷阱。它想要走遍每一个方格，但是它很笨，只会按照指令方向走。当下一步是边界或者是陷阱时，它会向右旋转 90 度。请问这个机器人最多可以经过多少个方格？


数据输入：
对于每组数据，第一行两个数 w 和 h，分别表示迷宫的行和列（1≤w,h≤10）
接下来 w 行，每行有 h 个字符用于描述这个迷宫。迷宫中的‘.’表示空地，即可以走的地方；‘*’表示陷阱，即不能走的地方；迷宫中有一个英文字母，表示机器人的出发点。字母只可能是‘U’、‘D’、‘L’、‘R’，分别表示机器人初始指令方向是向上、向下、向左、向右。

结果输出：
对于每组数据，输出一个整数，表示机器人一共经过了多少个方格

输入示例：
2 3
U..
.*.
4 4
R...
.**.
.**.
....

输出示例：
4
12



题目 C（15 分）
问题描述：
在一片 n*m 的土地上，每一块 1*1 的区域里都有一定数量的金子。这一天，你来到这里淘金。然而当地人告诉你，如果你要挖(x,y)区域的金子，那么你就不能挖(x-1,y)、(x+1,y)以及纵坐标为 y-1 和 y+1 的金子（也就是说你挖某一区域的金子，左边、右边、上一行、下一行的金子你都不被允许挖了）。那么问题来了，你最多能淘多少金？


数据输入：
对于每组数据，第一行两个数 n 和 m，分别表示土地的长度和宽度（1≤n,m≤200）
接下来 n 行，每行有 m 个数表示每个区域金子的数量，每个区域金子数量不超过 1000


结果输出：
对于每组数据，输出最多能得到的金子数量

输入示例：
4 6

11 0 7 5 13 9

78 4 81 6 22 4

1 40 9 34 16 10

11 22 0 33 39 6

输出示例：
242



题目 D（20 分）
问题描述：
巨人国的小学生放学了，老师要给小朋友们排队了。可是这个老师有强迫症，一定要让路队上的小朋友按身高从高到矮排序。小朋友们呢也很调皮，一旦老师给他排好了队就不愿意动了。这时候小朋友们一个一个从教室里出来了，每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友们排几条路队？

数据输入：
对于每组数据，第一行一个整数 n，表示小朋友的总数（1≤n≤10000）第二行 n 个整数，表示每个小朋友的身高，身高不超过 30000

结果输出：
对于每组数据，输出一个整数，表示最少的路队数

输入示例：
8

389 207 155 300 299 170 158 65

输出示例

2

样例解释：
最少要排两条路队，其中一种方案是：389-207-155-65 和 300-299-170-158



题目 E（15 分）
问题描述：
你收到通知被中南大学录取了，高兴地来到长沙。很快你就来到了麓山南路上，已知你的位置是 N，中南大学的位置是 K。为了去中南大学，你有两种移动方式：走路或者坐公交车。走路：你可以从位置 X 移动到 X+1 或者 X-1 搭公交：你可以从位置 X 移动到 2X；
每次走路和搭公交所需的时间都是一分钟，你现在想尽快到中南大学，所需的时间是多少呢？

数据输入：
对于每组数据，输入一行，分别是 N 和 K（1≤N,K≤100,000）

结果输出：
对于每组数据，输出一个整数，表示所需时间

输入示例：
5 17

输出示例：
4

样例解释：
其中的一种方案是：5-10-9-18-17 所需时间是 4 分钟。

[此贴子已经被作者于2017-4-26 22:03编辑过]

感觉真的比蓝桥杯要高一等~不过还是和真正的AC竞赛题还是有差距的(我都不一定能找到解题思路~但这4题我有一定把握)

第一题代入规则运算就行了~标记重复走过的路和方向~如果在同一个方格上走同一个方向就可以结束判断了~

第二题应该是动态规划与剪枝~应该先找到其中一个解然后不断找最大值优化200*200=40000这样明显不能用穷举的~这个有一定的难度~我也没有很大的把握能做出来~~~

第三题应该是拓补排序~虽然我还没学到那~但应该是把数据的值和所在的排位用一个结构体联立起来再进行拓补排序~数数拓补后最少有多少个分支入口就行了~

第四题比较简单~有两种解法~第一种是广度搜索~第二种是用数学方法~数学方法见10楼~~

还是先把这贴收录到待关注状态~最近比较忙~以后抽出空来再打算弄清楚具体思路和看看算法实现方法以及代码~~

[此贴子已经被作者于2017-4-28 12:45编辑过]

谢谢噢！

//本想练练手的，结果第一道题就折腾了一下午加小半个晚上。
#include<stdio.h>
int w,h;
char**arr;
int start_x,start_y;
char start_drt;
struct data
{
    short north;//记录该单元格是否往北走过，下同
    short east;
    short south;
    short west;
};
struct data**d;
void Initialize(int _w,int _h)
{
    int i,j;
    arr=(char**)malloc(sizeof(char*)*_h);
    d=(struct data**)malloc(sizeof(struct data*)*_h);
    for(i=0;i<_h;i++)
    {
        arr[i]=(char*)malloc(sizeof(char)*_w);
        d[i]=(struct data*)malloc(sizeof(struct data)*_w);
    }
    for(i=0;i<_h;i++)
    {
        for(j=0;j<_w;j++)
        {
            arr[i][j]=getch();
            printf("%c",arr[i][j]);
            if(arr[i][j]=='U'||arr[i][j]=='D'||arr[i][j]=='L'||arr[i][j]=='R')
            {
                start_x=j;start_y=i;start_drt=arr[i][j];
            }
            d[i][j].north=d[i][j].east=d[i][j].south=d[i][j].west=0;
        }
        printf("\n");
    }
}
void Free(int _h)
{
    int i;
    for(i=0;i<_h;i++)
        free(arr[i]);
    free(arr);
}
int Scan(int y,int x,char drt)
{
    int covered=0;
    int determined=0;
    while(1)
    {
        determined=0;//判断离开当前位置的去向是否确定
        while(!determined)
        {
            switch(drt)
            {
            case 'U':
                if(y==0||arr[y-1][x]=='*')
                    drt='R';
                else
                {
                    if(d[y][x].north) return covered;//返回走过的坐标数
                    else
                    {
                        covered+=(d[y][x].north==0&&
                            d[y][x].east==0&&d[y][x].south==0&&
                            d[y][x].west==0);//足迹累加
                        d[y][x].north=1;y--;
                        determined=1;
                    }
                }
                break;
            case 'R':
                if(x==w-1||arr[y][x+1]=='*')
                    drt='D';
                else
                {
                    if(d[y][x].east) return covered;//返回走过的坐标数
                    else
                    {
                        covered+=(d[y][x].north==0&&
                            d[y][x].east==0&&d[y][x].south==0&&
                            d[y][x].west==0);
                        d[y][x].east=1;x++;
                        determined=1;
                    }
                }
                break;
            case 'D':
                if(y==h-1||arr[y+1][x]=='*')
                    drt='L';
                else
                {
                    if(d[y][x].south) return covered;//返回走过的坐标数
                    else
                    {
                        covered+=(d[y][x].north==0&&
                            d[y][x].east==0&&d[y][x].south==0&&
                            d[y][x].west==0);
                        d[y][x].south=1;y++;
                        determined=1;
                    }
                }
                break;
            case 'L':
                if(x==0||arr[y][x-1]=='*')
                    drt='U';
                else
                {
                    if(d[y][x].west) return covered;//返回走过的坐标数
                    else
                    {
                        covered+=(d[y][x].north==0&&
                            d[y][x].east==0&&d[y][x].south==0&&
                            d[y][x].west==0);
                        d[y][x].west=1;x--;
                        determined=1;
                    }
                }
                break;
            }
        }
    }
}
int main()
{
    int answer;
    printf("请输入行数，列数（空格隔开）:");
    scanf("%d %d",&h,&w);
    Initialize(w,h);
    answer=Scan(start_y,start_x,start_drt);
    printf("走过的位置数：%d\n",answer);
    Free(h);
    return 0;
}

老哥幸苦了，谢谢你哦

老哥幸苦了，谢谢你哦

看到这个题目我第一个联想到的关键词是“二进制，位运算”。x+1，x-1正好对应+1.-1，x*2对应<<1.要算的就是二进制数N变成K需要多少步。
比如上面的5 17  转换成二进制数就是101 10001
因为5的二进制数共有3位，所以我们截取17的二进制前三位100.101和100的二进制数距离为1,+1步；
17的二进制除了和5共有的前3位以外还有2位,+2步；
17的二进制后两位中有1个“1”,+1步;
综上所诉，至少需要1+2+1=4步。
101-100-1000-10000-10001
用这个思路我们验证一下9->101
9=01001;101=01100101;
01001和01100的距离为3,+3步；
101除了和9共有的前4位以外还有3位，+3步；
101的二进制后3位中有两个“1”，+2步；
综上所述：共需3+3+2=8步（9-10-11-12-24-25-50-100-101）
--------------------我认为这种方法得到的“成长路径”一定是最优解，虽然我不太能说清楚怎么证明。。。

[此贴子已经被作者于2017-4-27 21:31编辑过]

收到的鲜花

• rjsp 于 2017-04-28 00:28 送鲜花  20朵   附言：妙

8楼的思路虽然较优较容易理解~但细想一下似乎欠缺考虑一些东西~

例如从1变到255 就相当于1到1111111

按楼主的思路应该是1-2-3-6-7-14-15-30-31-62-63-126-127-254-255这样~~
明显有比它更快的方法是1-2-4-8-16-32-64-128-256-255

问题关键是每个节点的的走法有三种不是两种~相当于比两种走法多了一条回路~~
其实这问题本质上是一个有向图的问题~求有向图已知两点距离的最优解~~
如果要求已知点到任意一点的距离就适宜用Dijkstra算法~~
如果两点都已知就用广搜吧~当然Dijkstra算法可以通过调整堆来优化~~除了头顶点外每个顶点都有三条边(网上百度搜过优化后的算法复杂度为0(n*log(m+n)))在可以接受的范围内~个人感觉还是广搜比较稳妥~

收到的鲜花

• 书生牛犊 于 2017-04-28 07:39 送鲜花  10朵   附言：谢谢指正

确实没考虑周全。M的后半截应该比较考虑“0”多还是“1”多。
如果“1”多，那么M的前半段就应该调整至N+1，后半段数有多少个“0”，就再调整多少步；否则，那就数有多少个“1”，就是需要调整多少步。
------------------------------
9楼说把这题当做“图的最短路径”问题来求解，，是不是类似于那种“上台阶问题”？如果是的话，由于要递归回溯神马的，我觉得算法复杂度会比较高。。如果不是，可否就具体例子讲讲是怎么做的。

其实如果把它当作图来做~要知道这不是一般的图~而是所有边的权值都相等为1的图~这样求最短路径完全可以用广搜~~

其实这题细想一下也可以用数学方法来求解~关键是要处理连续1的问题~

举个例子

1到10011101

1-10-100
前面这些都不难理解~关键是后面处理连续1的问题~可以先用0来补位~后者位数遇到0时再减1就行了~下面是关键部分~

100-1001-10010-100100-1001000-100111

因为用加法0-1要消耗一个单位的资源~所以在数位相等的前提下应尽量减少0-1的操作~
用减法一次就能把连续1部分的数位对齐~就相当于节约了用加法0变1的资源了~

后面就不用多说了
100111-1001110-10011100-10011101


当然~这只是讨论起点为1的情况~如果起点不为1时就要分两种情况~
看是用加法先使得数位对齐还是用减法先使得数位对齐(要考虑加法运算和减法运算使得自身位数变化的问题)~


其实算法思想可以相当于递归或者叫求局部最优解的贪心算法~~其实数位对齐的部分完全可以忽略不看~

举个例子
100到100011

忽略前三个数100位相当于
NULL-011
如果NULL理解上来有难度就这样理解试试
相当于0-0011

这题就等效于0-0011这种情况~当然和一般数不同的是前导0是不能忽略的~把这些数位一个一个拆分来看看起来虽然显得这个数有点不正常~不过却可以精简算法思想~

这样无论这个数有多长~对齐部分的数位是不会再发生改变的~接下来只需要看剩余的部分就行了~所以通过递归方法可以证明出这个解会是最优解~
例如证明1-11101的最优解可以先证明1-111的最优解再证明NULL-01的最优解~
这样递推就可以求出并证明其路径是最优解了~


再补充一下~~
10-101110111101可以先求
NULL-111的最优解
再求0-01111的最优解
再求0-01的最优解~
其中求0-01111相当于求
1-11111
可以证明其最优解是
1-10-100-1000-10000-100000-11111

感觉这用递归和贪心算法思想理解倒是挺合适的~

PS：等下回家去了~这个过程可能回不了~先自己消化一下~

[此贴子已经被作者于2017-4-28 12:46编辑过]