第一次笔试没有参加,但是牛客上已经有题了,很遗憾只做出前两道.感觉有很多要注意的地方,要不然根本做不完啊.

编码

题目1: 给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续 出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。

.统计连续出现的字符数目.注意数字字符串之间转换,别要在这些细节上浪费太多时间,要不然后边题没时间做!代码:

#include<iostream> #include<sstream> int main() { std::string s ; std::cin >> s; std::string res=""; if(s==""){ std::cout <<""; return 0; } // kong zi fu int cnt =1 ; for(int i =1 ; i< s.length(); i++) if(s[i-1]==s[i])cnt++; else { std::stringstream ss; std::string str; ss<<cnt; ss>>str; res = res + str + s[i-1]; cnt=1; } std::stringstream ss; std::string str; ss<<cnt; ss>>str; res = res +str +s[s.length()-1]; std::cout <<res; return 0; }

简单搜索:

.题目2: 在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值

分析

.可优化之处在于”连续” N 个数字和,N大于等于D,每次当和中包含的数字第一次大于N时,要想得到当前和，只需要减去上一次最后一个 值再加上当前的值就可以了, 每次遍历求和时间O(n),横竖斜着遍历去找就可，总时间Ｏ（ｎ＾２） 考察编程熟练啊,被bug卡住就杯具了 .代码;

#include<iostream> #include<vector> using std::cin; using std::cout; using std::vector; using std::endl; int main() { /* 4 2 87 98 79 61 10 27 95 70 20 64 73 29 71 65 15 0 */ // input: int N , D; cin>>N>>D; vector<vector<int>> mm(N , vector<int>(N, 0)) ; for(int i =0 ; i< N ; i++) for(int j =0 ; j< N ; j++) cin>>mm[i][j]; int maxsum =0; for(int i =0 ; i < N ; i++) { int csum =0; for(int j =0 ; j < N ; j++) { csum = j < D? csum + mm[i][j] : csum + mm[i][j] - mm[i][j-D]; if(j>=D-1) maxsum = maxsum < csum? csum : maxsum; } csum =0 ; for(int j =0 ; j < N ; j++) { csum = j < D? csum + mm[j][i] : csum + mm[j][i] - mm[j-D][i]; if(j>=D-1) maxsum = maxsum < csum? csum : maxsum; } } int i = N-1 , j = 0; while(i>=0){ int m = i , n =j; int cnt =0; int csum =0; while(n<N&&m<N) { csum = cnt < D ? csum + mm[m][n]:csum+mm[m][n] - mm[m-D][n-D]; if(cnt>=D-1)maxsum = maxsum<csum? csum: maxsum; m++;n++;cnt++; } i--; } i = 0;j = 1; while(j<N) { int m = i , n = j; int cnt =0 ; int csum =0 ; while(m < N && n < N) { csum = cnt < D ? csum + mm[m][n] : csum+mm[m][n] - mm[m-D][n-D]; if(cnt >= D-1)maxsum = maxsum< csum?csum: maxsum; m++; n++;cnt++; } j++; } i =0 ; j = 0; while(j<N) { int m = i , n = j; int cnt =0; int csum =0 ; while(m<N&&n>=0) { csum = cnt < D ? csum +mm[m][n] : csum + mm[m][n] - mm[m-D][n+D]; if(cnt >= D-1) maxsum = maxsum < csum?csum:maxsum; m++;n--;cnt++; } j++; } i = 1; j =N-1; while(i < N) { int m = i , n = j; int cnt = 0; int csum = 0; while(m<N&&n>=0) { csum = cnt <D? csum + mm[m][n] :csum +mm[m][n] - mm[m-D][n+D]; if(cnt >= D-1) maxsum = maxsum <csum ? csum:maxsum; m++;n--;cnt++; } i++; } cout <<maxsum; return 0; }

推箱子

.题目3: 大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地 图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。 玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障 碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一 格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地 以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求 出玩家最少需要移动多少步才能够将游戏目标达成。 .输入格式代码注释里有,*表示箱子,X表示人,@表示目的地,#表示障碍

分析

.后来做才发现这是宽度优先的题目,在一个图结构当中如果每条边权重是1的话,宽度优先搜索第一次到达目的地步数就是到此位置的最小代价. 分析这道题最好的方式就是画出状态转移关系,小人和箱子的位置确定了当前玩家的一个状态,下一步要去往的状态无非是这么两种情况: . 人走到另一个空地,箱子没动 .人推箱子前进一步

实现简述

.声明一个四位数组来st,当前状态表示为st[x][x][bx][bx]:人位 置(x,y),箱子位置(bx,by),并将初始位置数组值设为1,将初始值压 入一个队列中 .每次从队列中取出一个元素,宽度优先下一个未曾到达的状态(以上分 析的两种)判断箱子是否到达终点.如果是打印路长并退出. .没有找到相关路径打印-1. #include<iostream> #include<vector> #include<queue> using std::cin ; using std::cout; using std::vector; using std::endl; using std::queue; /* 4 4 .... ..*@ .... .X.. */ int st[10][10][10][10]; int x,y,bx,by,tx,ty; int m , n ; vector<vector<char>> mm ; bool valid(int x,int y ){ //cout <<m<<" "<<n<<"-"<<endl; if(x>=0&&x<m&&y>=0&&y<n&&mm[x][y]!='#')return true; return false; } int main(){ cin >> m >>n; mm= vector<vector<char>>(m , vector<char>(n ,' ' )); for(int i =0 ; i < m ; i++) for(int j=0 ; j< n ; j++) { char t ; cin >>t; if(t=='X'){ x = i;y = j; // cout <<x<<" "<<y<<endl; } if(t == '*'){ bx = i ;by = j; } if(t == '@'){ tx = i ; ty = j; } mm[i][j] = t; } // record every state of the vector<vector<int>> next= {{-1, 0},{1,0},{0,1},{0,-1}}; queue<vector<int>> que ; que.push({x,y,bx,by}); st[x][y][bx][by] =1 ; while(!que.empty()) { vector<int> t = que.front(); que.pop(); x = t[0]; y = t[1]; bx=t[2]; by = t[3]; for(int i =0 ; i < next.size() ; i++) { int nx = x+next[i][0],ny =y+next[i][1]; int nnx = nx+next[i][0],nny =ny+next[i][1]; if(valid(nx,ny)&&(nx!=bx||ny!=by)&&st[nx][ny][bx][by]==0) { st[nx][ny][bx][by]= st[x][y][bx][by]+1; que.push({nx,ny,bx,by}); continue; }else if(nx==bx&&ny==by&&valid(nnx,nny)&&st[nx][ny][nnx][nny]==0){ st[nx][ny][nnx][nny] = st[x][y][bx][by]+1; if(mm[nnx][nny]=='@'){cout<<st[nx][ny][nnx][nny]-1;return 0;} que.push({nx,ny,nnx,nny}); } } } cout <<-1; return 0; }

赛马

.题目4: 在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开 始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速 度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了 前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长 的时间后，赛道上剩余的马匹数量的数学期望是多少

分析

.开始认为几匹快马速度一样才可能同时留下来,没好好读题,其实人家说了马的速度都不一样.假设几匹马的速度是 a1<a2<a3<...<an , 因为只有在第一匹快马后面才能留下来,这是i种情况之一, 第i匹马留下期望 0∗(i−1)/i+1/i ,由 E(X+Y)=E(X)+E(Y) 得到所有马期望和1 + 1 / 2 + 1 / 3 + 1 / 4 + … + 1 / N，就是调和级数。

#include<iostream> #include<stdio.h> #include<math.h> using std::cin; using std::cout; int main(){ int n ; cin >>n; if(n==0) { cout <<0; return 0; } float sum =0.0; for(int i =1 ; i<=n ; i++) { sum+= 1.0/i; } printf("%.4f",sum); return 0; }