[编程题] 字符串编码
给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。
输入描述:
每个测试输入包含1个测试用例
每个测试用例输入只有一行字符串，字符串只包括大写英文字母，长度不超过10000。
输出描述:
输出编码后的字符串
输入例子:
AAAABCCDAA
输出例子:
4A1B2C1D2A#include<bits/stdc++.h>
using namespace std;
string solve(string& str){
int n=str.size();
int count=1;
string res;
for(int i=1;i<n;i++){
if(str[i]==str[i-1]) count++;
else{
res+=to_string(count)+str[i-1];
count=1;
}
}
res+=to_string(count)+str[n-1];
return res;
}
int main(){
string str;
cin>>str;
cout<<solve(str);
}
最大和
在一个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<bits/stdc++.h>
using namespace std;
int main(){
int n,d;
cin>>n>>d;
vector<vector<int>> v(n,vector<int>(n));
// vector<vector<int>> dp(n,vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>v[i][j];
}
}
int res=INT_MIN;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int sum1=0,sum2=0,sum3=0,sum4=0;
for(int k=0;k<d;k++){
if(j-0+1>=d) sum1+=v[i][j-k];
if(j-0+1>=d&&i-0+1>=d) sum2+=v[i-k][j-k];
if(i-0+1>=d) sum3+=v[i-k][j];
if(n-1-j+1>=d&&i-0+1>=d) sum4+=v[i-k][j+k];
}
res=max(res,sum1);
res=max(res,sum2);
res=max(res,sum3);
res=max(res,sum4);
}
}
cout<<res;
}
推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个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
#include<bits/stdc++.h>
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,bx,by;
int endx,endy;
for(int i=0;i!=n;++i)
{
string 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<<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;
}
赛马
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少
输入描述:
每个测试输入包含1个测试用例
输入只有一行，一个正整数N
1 <= N <= 1000
输出描述:
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
输入例子:
1
2
输出例子:
1.0000
1.5000#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
double res=0.0;
for(int i=1;i<n+1;i++){
res+=1.0/i;
}
cout<<setiosflags(ios::fixed)<<setprecision(4)<<res;
}
1. 竖式填空
CA6EFF0F-51E7-4A9C-97D0-8E270D8AD912.png
[编程|100分] 竖式填空 时间限制：1秒 空间限制：65536K 题目描述 小Q是名小学生，他最喜欢数学中的加法竖式填空了。例如下面的填空题，每个空格表示1…9中的一个数字。
有时候这种竖式题不一定只有唯一解，小Q很想知道，给定一个这样的竖式，总共可能的解有多少个。 被加数和加数的位数不会超过3位。和的位数不会超过4位。空格只可能存在于被加数和加数中。
输入描述: 每个输入数据包含多个测试点。 第一行为测试点的个数T(T<=30)。 每个测试点包含一行，包含了三个长度大于0的字符串，分别表示被加数，加数和结果。每个字符串之间有一个空格。每个字符串只会包含“X”和“1”…“9”，其中“X”表示竖式中的空格。保证竖式至少有一个解。
输出描述: 对于每个测试点，输出一行，表示一共可能的解的个数。
输入例子: 2 X7 9X 123 X X 4
输出例子: 1 3 （样例解释：样例1的解为27+96，样例2的解为1+3,2+2,3+1。）
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std
int getNum (string &numA, string &numB, string &sum,
int pos,
int carry)
{
if (
pos ==
-1)
{
if (carry)
return 0
else
return 1
}
else
{
int digitA = numA[
pos] -
'0', digitB = numB[
pos] -
'0', digitSum = sum[
pos] -
'0'
if (numA[
pos] !=
'X' && numB[
pos] !=
'X')
{
if ((digitA + digitB + carry) %
10 != digitSum)
return 0
else
{
int newCarry =
0
if (digitA + digitB + carry >=
10)
newCarry =
1
return getNum (numA, numB, sum,
pos -
1, newCarry)
}
}
else if (numA[
pos] ==
'X' && numB[
pos] ==
'X')
{
int cnt =
0
for (
int j =
1
for (
int k =
1
{
int tmp = j + k + carry
int newCarry =
0
if (tmp >=
10)
newCarry =
1
if (tmp %
10 == digitSum)
cnt += getNum (numA, numB, sum,
pos -
1, newCarry)
}
return cnt
}
else
{
int digit = digitA
if (numB[
pos] !=
'X')
digit = digitB
int cnt =
0
for (
int i =
1
{
int tmp = i + digit + carry
int newCarry =
0
if (tmp >=
10)
newCarry =
1
if (tmp %
10 == digitSum)
cnt += getNum (numA, numB, sum,
pos -
1, newCarry)
}
return cnt
}
}
}
int main ()
{
int testNum
scanf (
"%d", &testNum)
for (
int i =
0
{
string numA, numB, sum
cin >> numA >> numB >> sum
while (numA.size () != sum.size ())
numA.insert (numA.begin (),
'0')
while (numB.size () != sum.size ())
numB.insert (numB.begin (),
'0')
printf (
"%d\n", getNum (numA, numB, sum, (
int)sum.size () -
1,
0))
}
return 0
}
2.NTES
79F5A525-9438-4AF4-A98F-763AACF917A7.png
题目描述 NTES是网易在纳斯达克股票市场的代号，在财报公布后，NTES的股价接连大涨，创下了历史新高。 下面，我们用四个5x7的点阵来描述NTES这代号。
....
.#...
..#..
...#.
....
#
...#... ...#... ...#... ...#...
#
......
#
......
#
#
......
#
......#
#
假设我们认为每个点的周围的8个方向的点都和它是相连的，并且相连在一起的符号“#”我们可以认为在同一个联通分量，则上述四个点阵分别都包含了一个“#”的联通分量。
给定N * M的点阵，点阵只包含“.”和“#”两种符号。在点阵中可能包含了很多的联通分量。那么，在这点阵当中，你能找到多少个和标准的“N”,“T”,“E”,“S”一样的联通分量呢？ 下面是点阵中NTES对应的联通分量的一些限制： ❖ N、T、E、S可能被顺时针旋转90度、180度或270度。例如以下的7x11的点阵中，包含了两个完整的T（两个联通分量），一个与前文提到的T方向一致，另一个是顺时针旋转了270度。
...
......#...
......#...
..#...
......#...
..........
..........
❖ 对于任何一个完整的N、T、E、S对应的联通分量，必须和前面给出的标准的模板一致。即除了旋转外，不多出或者缺少任何一个“#”，否则认为不匹配。例如下图中虽然只包含了一个联通分量（根据八方向相连的定义，（1,7）和（0,6）上的“#”相连），但是其多了一个“#”在位置（1,7），因此，以下点阵中没有任何一个NTES对应的联通分量。
#.
...#...# ...#.... ...#.... ...#....
输入描述: 每个输入数据包含一个测试点。 第一行为点阵的大小N，M。其中1<=N<=500，1<=M<=500。 接下来N行，每行包含了M个“.”或“#”的字符，描述了给定的点阵。
输出描述: 输出包括四行，按顺序输出点阵中包含的NTES的数量。
输入例子: 输入样例1: 7 11
...
......#...
......#...
..#...
......#...
..........
..........
输入样例2: 12 23
#....#....
...#...##....#..#......
..#...#.#...#..
..#...#..#..#........
...#..#...#.#..
....#....##.........
.........#.............
#....#.##.##....
......#....#....#.#...#
#....#....#..#..
......#....#....#...#.#
#.#######.#....
输出例子: 输出样例1: N: 0 T: 2 E: 0 S: 0
输出样例2: N: 1 T: 1 E: 1 S: 1
3.装备强化
91522564-A74C-43F5-B6A4-8B9EE2B3832A.png
题目描述 网游中，装备强化是提升角色战力的常见方法。 现在你参与开发的游戏中也有这项功能，团队正在设计每件装备强化所能提升的战力及需要消耗的金币数。为了设计出一个合理的强化系统，决定先做一些强化模拟测试，而你现在就在是该模拟程序的开发者。 假设现在有n件可以同时穿戴的装备，对于第i件装备，最多可以强化mi 次，对于第i件装备的第j次强化，会增加fij 的战力，并需要消耗gij 个金币。现在给出所有装备的数据，以及初始拥有的金币数量，求最多可以增加多少战力。 输入描述: 输入文件的第一行为一个正整数T，表示测试数据组数。 接下来有T组数据。每组数据第1行为两个整数n和s，分别表示装备数量及初始拥有的金币数量。接下来是n行，每行表示一个装备，其中每行第一项为一个字符串，表示装备的名称，第二项为非负整数mi，表示装备最多可强化的次数，接下来为2*mi个非负整数，表示每次强化会增加的战力及消耗的金币数。
数据范围： 对于所有数据文件，1<=T<=10。装备的名称最大长度不超过32个字符，由大小写字母或数字组成。每件装备最多强化次数mi满足0<=mi<=3。所有战力数值和金币数为非负整数且不超过10,000,000。 对于其中的20%数据，满足装备数1<=n<=5； 另外有30%数据，满足装备数1<=n<=10； 另外有30%数据，满足装备数1<=n<=16； 最后剩下的20%数据，满足装备数1<=n<=20。
数据保证只有唯一的强化方案能达到最大战力。
输出描述: 对于每个测试数据，第一行为一个整数，表示最多可提升的战力。接下来是n行，表示达到这个战力时每件装备分别的强化次数，形式为“装备名称+强化次数”。输出装备的顺序要与输入数据一致。更详细的格式请参照输出样例。
输入例子: 3 4 100 Helm 1 20 30 Gloves 1 30 40 Boots 1 10 10 Sword 1 50 50 5 10 Item1 0 Item2 1 10000 100 Item3 1 10 10 Item4 3 1 0 2 1 3 2 Item5 3 0 4 1 1 5 1 6 256 1x 2 12 43 35 58 2x 2 34 54 88 31 3x 2 43 10 15 55 4x 2 32 54 19 19 5x 2 84 1 15 45 6x 2 19 40 99 12
输出例子: 90 Helm+0 Gloves+1 Boots+1 Sword+1 12 Item1+0 Item2+0 Item3+0 Item4+3 Item5+3 418 1x+0 2x+2 3x+1 4x+2 5x+1 6x+2
