题目来源:牛客网/profile/7952866/test/7775568/76265
1.字符串编码
给定一个字符串,请你将字符串重新编码,将连续的字符替换成“连续出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。
输入例子:
AAAABCCDAA
输出例子:
4A1B2C1D2A
思路比较简单,只需要遍历字符串,对每一个单独的字符设置一个初始值为1的计数器,然后比较它和相邻的字符是否相同,如果相同则加1,直到遇到不同的字符,输出当前计数器的值并重置为1。
测试代码如下:
#include <cstdio>#include <string>#include <iostream>using namespace std;string num = "0123456789";string intToString(int n) {//int转成string,比如 12转为‘12’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这个位置再开始检索break;}}if (j == len) {ans = ans + intToString(cnt);ans = ans + cur;break;}}return ans;}int main(){string str;while (cin >> str){string ans = solve(str);cout << ans << endl;}return 0;}
测试结果:
2.赛马
在一条无限长的跑道上,有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后,所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样,且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时,被追上的马就出局。 请问按以上的规则比赛无限长的时间后,赛道上剩余的马匹数量的数学期望是多少
输入描述:
每个测试输入包含1个测试用例
输入只有一行,一个正整数N
1 <= N <= 1000
输出描述:
输出一个浮点数,精确到小数点后四位数字,表示剩余马匹数量的数学期望
输入例子:
1
2
输出例子:
1.0000
1.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的和,就是调和级数。
测试代码如下:
#include <cstdio>//调和级数int main() {int n;while (scanf_s("%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;}
测试结果:
3.最大和
在一个N*N的数组中寻找所有横,竖,左上到右下,右上到左下,四种方向的直线连续D个数字的和里面最大的值
输入描述:
每个测试输入包含1个测试用例,第一行包括两个整数 N 和 D :
3 <= N <= 100
1 <= D <= N
接下来有N行,每行N个数字d:
0 <= d <= 100
输出描述:
输出一个整数,表示找到的和的最大值
输入例子:
4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0
输出例子:
193
思路:直接从行、列、左上到右下,右上到左下,四种方向暴力搜索
测试代码:
#include <iostream>#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() {int n, d;while (scanf_s("%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_s("%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++) {sum = sum + arr[row][j];}if (sum > Max)Max = 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++){sum = sum + arr[j][col];}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 (check1(x, y, d, n)) {int cnt = 0;int sum = 0;while (cnt < d) {sum = sum + arr[x][y];cnt++;x++;y++;}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)) {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", Max);}return 0;}
测试结果如下:
4.推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个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...
.@#...
输出例子:
3
11
思路:利用BFS,每一步有4中情况,用四维数组记录每一个人和箱子所在位置的状态,如果之前出现过这种状态,直接跳过,否则计数加一,一直遍历,若队列为空还没有输出,则无法到达。否则可以到达。by:/njudongchen/article/details/61415043
测试代码如下:
#include <iostream>#include <string>#include <queue>#include <vector>using namespace std;struct humanbox{//创建一个结构体:人和箱子的坐标int hx, hy, bx, by;humanbox(int x, int y, int bbx, int bby) :hx(x), hy(y), bx(bbx), by(bby){};};int main(){int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m, 0));int hx, hy; //玩家起点坐标int bx, by; //箱子坐标int endx, endy; //目的地坐标for (int i = 0; i != n; ++i){//更新地图mapstring str;cin >> str;for (int j = 0; j != m; ++j){if (str[j] == 'X'){map[i][j] = 'X';hx = i;hy = j;}else if (str[j] == '#')map[i][j] = '#';else if (str[j] == '@'){map[i][j] = '@';endx = i;endy = j;}else if (str[j] == '*'){map[i][j] = '*';bx = i;by = j;}}}//枚举四个方向:向右走、向左走、向下走、向上走int stepx[4] = { 0, 0, 1, -1 };int stepy[4] = { 1, -1, 0, 0 };//更新步数int count[10][10][10][10] = { 0 };queue<humanbox> que;que.push(humanbox(hx, hy, bx, by));count[hx][hy][bx][by] = 1;while (!que.empty()){humanbox top_que = que.front();que.pop();if (top_que.bx == endx&&top_que.by == endy){//到达终点cout << (count[top_que.hx][top_que.hy][top_que.bx][top_que.by]) - 1;//输出减1是因为起始从1开始cout<< endl;return 0;}for (int i = 0; i != 4; ++i){int hnx = top_que.hx + stepx[i];int hny = top_que.hy + stepy[i];if (hnx<0 || hny<0 || hnx >= n || hny >= m || map[hnx][hny] == '#')//当越界或者遇到障碍物continue;if (hnx == top_que.bx&&hny == top_que.by){//当玩家遇到箱子int bnx = top_que.bx + stepx[i];int bny = top_que.by + stepy[i];if (bnx<0 || bny<0 || bnx >= n || bny >= m || map[bnx][bny] == '#') //当箱子越界或者遇到障碍物continue;if (count[hnx][hny][bnx][bny]) continue;count[hnx][hny][bnx][bny] = count[top_que.hx][top_que.hy][top_que.bx][top_que.by] + 1;que.push(humanbox(hnx, hny, bnx, bny));}else{if (count[hnx][hny][top_que.bx][top_que.by])continue;count[hnx][hny][top_que.bx][top_que.by] = count[top_que.hx][top_que.hy][top_que.bx][top_que.by] + 1;que.push(humanbox(hnx, hny, top_que.bx, top_que.by));}}}cout << -1 << endl;return 0;}
测试结果: