4道题2小时，又是一道，不过这次的比较难，但第二道不应该的，又是审题不仔细导致没过
题目1：
给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。
思路：就简单的字符串处理
#include <iostream>
#include <string>
using namespace std ;
int main(){
string str , ans ;
cin >> str ;
ans = "" ;
for(int i=0;i<str.length();i++){
int cnt = 1 ;
char temp = str[i] ;
while((i+1)<str.length()&&temp==str[i+1]){
cnt++ ;
i++ ;
}
ans = ans + to_string(cnt) + temp ;
}
cout << ans << endl ;
}
第二题：
在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值
输入描述:
每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :
3 <= N <= 100
1 <= D <= N
接下来有N行，每行N个数字d:
0 <= d <= 100
输出描述:
输出一个整数，表示找到的和的最大值
输入例子1:
4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0
输出例子1:
193
这道没过不应该了，自以为题目中的左上到右下和右上到左下是一个意思，然后就少算了一种情况，于是只能过80%的样例，最后有个疑问，既然0<=d<=100，为什么还要考虑负数。。
#include <iostream>
#include <algorithm>
using namespace std ;
int findMax(vector<vector<int>> map,int x,int y,int D){
int l , d , ld ,rd;
int lc, dc, ldc ,rdc ;
int m = 0 ;
l = d = ld = rd = 0 ;
lc = dc = ldc = rdc = 0 ;
for(int i=0;i<D;i++){
if(x+i<map.size()){
d += map[x+i][y] ;
dc++ ;
}
if(y+i<map[0].size()){
l += map[x][y+i] ;
lc++ ;
}
if(x+i<map.size()&&y+i<map[0].size()){
ld += map[x+i][y+i] ;
ldc++ ;
}
if(x+i<map.size()&&y-i>=0){
rd += map[x+i][y-i] ;
rdc++ ;
}
}
if(lc!=D) l = 0 ;
if(dc!=D) d = 0 ;
if(ldc!=D) ld = 0 ;
if(rdc!=D) rd = 0 ;
m = max(m,l) ;
m = max(m,d) ;
m = max(m,ld) ;
m = max(m,rd) ;
return m ;
}
int main(){
int n , d ;
cin >> n ;
cin >> d ;
vector<vector<int>> map(n,vector<int>(n)) ;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> map[i][j] ;
}
}
int ans = 0 ;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ans = max(ans,findMax(map,i,j,d)) ;
}
}
cout << ans << endl ;
}
题目三：推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述:
每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子1:
4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...
输出例子1:
3
11
思路：老实说觉得挺难的，而且好久没有做广搜的题了，一开始想着人和箱子分两个阶段，人找到箱子之前和找到箱子之后，然而写的一团乱，反正没写出来，后面看了评论区大神的写法，用一个思维数组vis[x][y][wx][wy]记录状态人在x,y箱子在wx,wy时需要多少步
之后在中间判断人的移动有没有造成箱子的移动就行了。
#include <iostream>
#include <queue>
#include <string>
using namespace std ;
struct State{
int x , y , wx , wy ;
State(int x,int y,int wx,int wy){
this->x = x ;
this->y = y ;
this->wx = wx ;
this->wy = wy ;
}
};
int vis[10][10][10][10] ;
int map[10][10] ;
int ex, ey, x, y, wx, wy , m , n ;
int a[]={0,0,1,-1}, b[]={1,-1,0,0} ;
queue<State> q ;
int bfs(){
vis[x][y][wx][wy] = 1 ;
State s(x,y,wx,wy) ;
q.push(s) ;
while(!q.empty()){
State t = q.front() ;
q.pop() ;
if(t.wx==ex&&t.wy==ey) return vis[t.x][t.y][t.wx][t.wy]-1 ;
for(int i=0;i<4;i++){
int nx = t.x+a[i] ;
int ny = t.y+b[i] ;
if(nx<0||ny<0||map[nx][ny]=='#'||nx>=n||ny>=m) continue ;
if(nx==t.wx&&ny==t.wy){
int nwx = nx+a[i] ;
int nwy = ny+b[i] ;
if(nwx<0||nwy<0||map[nwx][nwy]=='#'||nwx>=n||nwy>=m) continue ;
if(vis[nx][ny][nwx][nwy]) continue ;
vis[nx][ny][nwx][nwy] = vis[t.x][t.y][t.wx][t.wy]+1 ;
State s(nx,ny,nwx,nwy) ;
q.push(s) ;
}else{
if(vis[nx][ny][t.wx][t.wy]) continue ;
vis[nx][ny][t.wx][t.wy] = vis[t.x][t.y][t.wx][t.wy]+1 ;
State s(nx,ny,t.wx,t.wy) ;
q.push(s) ;
}
}
}
return -1 ;
}
int main(){
cin >> n >> m ;
for(int i=0;i<n;i++){
string row ;
cin >> row ;
for(int j=0;j<m;j++){
map[i][j] = row[j] ;
if(row[j]=='X'){
x = i ;
y = j ;
}
if(row[j]=='*'){
wx = i ;
wy = j ;
}
if(row[j]=='@'){
ex = i ;
ey = j ;
}
}
}
cout << bfs() << endl ;
}
题目4：赛马
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少
输入描述:
每个测试输入包含1个测试用例
输入只有一行，一个正整数N
1 <= N <= 1000
输出描述:
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
输入例子1:
1
2
输出例子1:
1.0000
1.5000
思路：算是数学题，然而在时间有限的情况下没想明白。之后看了评论区答案：速度最大的马无论在什么位置都可以不被淘汰，所以速度最大的马存活的概率是1，然后速度第二大的马只有在速度最大的马后面才能存活，只有在它前后两种情况，所以存活的概率是1/2，同理，速度第三大的马有三种排列情况（不考虑前面两匹马的排列），存活概率是1/3,依次类推，所以最后的情况就是1+1/2+1/3+......1/n。注意不是通过每种排列情况计算能存活下来的马的数量，而是根据每匹马能存活的概率计算。
#include <iostream>
#include <iomanip>
using namespace std ;
int main(){
int n ;
double ans = ;
cin >> n ;
for(int i=;i<=n;i++){
ans+=(1.0/i) ;
}
cout<<setiosflags(ios::fixed)<<setprecision()<<ans<<endl ; }