2月15号参加的网易游戏实习在线笔试（内推），以为会考小题的，背了一天计算机网络和操作系统，结果拿到题只有4道编程大题，囧~如果没有一点算法竞赛的知识，想拿下来还是挺困难的。（网易游戏应该算国内笔试很难的了）
题目地址：/test/4111169/summary
1.字符串编码
输入描述:
每个测试输入包含1个测试用例每个测试用例输入只有一行字符串，字符串只包括大写英文字母，长度不超过10000。
输出描述:
输出编码后的字符串
输入例子:
AAAABCCDAA
输出例子:
4A1B2C1D2A
思路分析：这道题好像以前是一家企业的面试题，LeetCode Easy级别，思路弄清楚，10分钟AC。
#include <cstdio>#include <string>#include <iostream>using namespace std;string num = "0123456789";string intToString( int n ) {string str = "";while( n ) {str = num[n % 10] + str;n = n / 10;}return str;}string solve( string str ) {int len = str.size();int i = 0;char cur;int cnt;string ans = "";while( i < len ) {cur = str[i];cnt = 0;int j = 0;for( j = i; j < len; j++ ) { // 从当前位置开始检索if( str[j] == cur ) {cnt++;}else if( str[j] != cur ) {ans = ans + intToString( cnt );ans = ans + cur;i = j; // 从i = j这个位置再开始检索//cout << ans << endl;break;}}if( j == len ) {ans = ans + intToString( cnt );ans = ans + cur;//cout << ans << endl;break;}}return ans;}int main() {string str;while( cin >> str ) {string ans = solve( str );cout << ans << endl;}return 0;}
2.最大和
输入描述:
每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :3 <= N <= 1001 <= D <= N接下来有N行，每行N个数字d:0 <= d <= 100
输出描述:
输出一个整数，表示找到的和的最大值
输入例子:
4 287 98 79 6110 27 95 7020 64 73 2971 65 15 0
输出例子:
193
思路分析：这道题数据量比较小，只有100，所以暴力枚举即可（注意要搞清楚逻辑再写，写40多分钟都有可能的）。另外可以用dp的想法，维护前缀和。
#include <cstdio>#define MAX 100 + 10int Max = 0;bool check1( int x, int y, int d, int n ) {if( x + d - 1 > n ) return false;if( y + d - 1 > n ) return false;return true;}bool check2( int x, int y, int d, int n ) {if( x + d - 1 > n ) return false;if( y - d < 0 ) return false;return true;}int main() {//freopen( "123.txt", "r", stdin );int n, d;while( scanf( "%d%d", &n, &d ) != EOF ) {Max = 0;int arr[MAX][MAX];for( int i = 1; i <= n; i++ ) {for( int j = 1; j <= n; j++ ) {scanf( "%d", &arr[i][j] );}}// 先从每行开始找for( int row = 1; row <= n; row++ ) {for( int i = 1; i <= n - d + 1; i++ ) {int sum = 0;for( int j = i; j < d + i; j++ ) {//printf( "add %d %d\n", row, j );sum = sum + arr[row][j];}if( sum > Max ) Max = sum;//printf( "%d\n", sum );}}// 再从每列开始找for( int col = 1; col <= n; col++ ) {for( int i = 1; i <= n - d + 1; i++ ) {int sum = 0;for( int j = i; j < d + i; j++ ) {//printf( "add %d %d\n", j, col );sum = sum + arr[j][col];}if( sum > Max ) Max = sum;//printf( "%d\n", sum );}}// 再从左上到右下对角线开始找for( int i = 1; i <= n; i++ ) {for( int j = 1; j <= n; j++ ) {// 从i,j起点开始找int x = i;int y = j;if( check1( x, y, d, n ) ) {//printf( "从 %d %d开始\n", x, y );int cnt = 0;int sum = 0;while( cnt < d ) {sum = sum + arr[x][y];cnt++;x++;y++;}//printf( "%d\n", sum );if( sum > Max ) Max = sum;}}}// 再从右上到左下对角线开始找for( int i = 1; i <= n; i++ ) {for( int j = 1; j <= n; j++ ) {// 从i,j起点开始找int x = i;int y = j;if( check2( x, y, d, n ) ) {//printf( "从 %d %d开始\n", x, y );int cnt = 0;int sum = 0;while( cnt < d ) {sum = sum + arr[x][y];cnt++;x++;y--;}if( sum > Max ) Max = sum;//printf( "%d\n", sum );}}}printf( "%d\n", Max );}return 0;}
3.推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述:
每个测试输入包含1个测试用例第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子:
4 4......*@.....X..6 6...#........#*##....##.#..X....@#...
输出例子:
311
思路分析：考查搜索。但是我当时没写出来，这道题只过了3个测试点。说一下别人的思路：
1.DFS，不知道他怎么写的，判断条件应该比较复杂吧。
2.BFS，四维BFS，增加两个维度代表箱子的位置（我当时考试只想到三维了，没想到四维，豁然开朗。。下去再练练）
去年有一道也是推箱子，不过那个是纯模拟，简单一点。有兴趣的可以在hihoCoder上看一下。
（代码暂时没有）
4.赛马
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少
输入描述:
每个测试输入包含1个测试用例输入只有一行，一个正整数N1 <= N <= 1000
输出描述:
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
输入例子:
12
输出例子:
1.00001.5000
思路分析：题目看上去有点费解，个人更感觉像是一道智力题。我们假设有N匹马赛跑，最后剩下的那个是冠军。注意题目中说每个马的速度不一样，这就说明最后只会剩下一个马，不可能出现并列的情况。另外数学期望的意思就是如果这匹马的编号是i，那P（i）表示i是冠军的概率，就是数学期望。可以这样想一下：如果只有一匹马，那么这匹马肯定是冠军，数学期望显然是1。如果有两匹马，那么某一匹马是冠军的概率是0.5，某一时刻其中一个马被淘汰了，那么另一个马的数学期望变成1，相加就是1.5。依次类推，如果刚开始有N匹马，P（i） = 1 / N，某一时刻P（i） = 1 / （N - 1）、1/（N - 2）......所以这道题的答案就是计算1 + 1 / 2 + 1 / 3 + 1 / 4 + ... + 1 / N的和，就是调和级数。
另外见群里有ACM大神说根据某某定理，先打个表，然后高精度运算得出结果，没听懂他的做法。我感觉调和级数这个还是好理解的。
#include <cstdio>int main() {int n;while( scanf( "%d", &n ) != EOF ) {double sum = 0.0;for( int i = 1; i <= n; i++ ) {sum = sum + 1.0 / i;}printf( "%.4lf\n", sum );}return 0;}
