1. 小红杀怪
题目描述
小红在一个游戏里杀怪。这是个回合制游戏,小红和两只怪物相遇了。
第一只怪物有a血量,第二只怪物有b血量。
小红有两个技能:
第一个技能叫火球术,效果是对单体怪物造成x伤害。
第二个技能叫烈焰风暴,效果是对每只怪物造成y伤害。
小红想知道,自己最少使用多少次技能,可以击杀这两只怪物?(当怪物血量小于
等于0时,视为被击杀)
输入描述:
四个正整数a,b,x,y,用空格隔开。
1≤ a,b,x,y ≤ 20
输出描述:
小红使用技能的最少次数。
思路:贪心
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int res = 0;
int a,b,x,y;
int main()
{
cin>>a>>b>>x>>y;
if(y >= x) res = max((a + y - 1) / y, (b + y - 1) / y);
else
{
while(a > 0 || b > 0)
{
if(2 * y >= x && a > 0 && b > 0)
{
res ++;
a -= y;
b -= y;
}
else if(a > y && b > y)
{
res += 2;
a -= x;
b -= x;
}
else if((a > 0 && b > 0) && (a <= y || b <= y))
{
res ++;
a -= y;
b -= y;
}
else if(a > 0 && b <= 0)
{
res ++;
a -= x;
}
else if(b > 0 && a <= 0)
{
res ++;
b -= x;
}
}
}
cout<<res<<endl;
return 0;
}
2.小红标字母
题目描述
小红拿到了一个字符串,她可以做任意次以下操作:
标记这个字符串两个位置相邻的字母,并且这两个字母必须满足以下条件才可标
记:两个字母相同或者两个字母在字母表中相邻。小红可以获得这两个字母的分
数。
举个例子,'a’和b’在字母表相邻,t’和’s’在字母表相邻。
我们规定,已经被标记的字母无法被重复标记。
每个字符获得的分数是不同的,'a’可以获得1分,'b’可以获得2分,以此类
推,'z’可以获得26分。
小红想知道,自己最多可以获得多少分?
输入描述:
输入一行只包含小写字母的非空字符串s,代表小红拿到的字符串。
1 ≤ len(s) ≤ 200000
思路:dp,dp[i]代表s[i]之前的最大值。
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<int> dp(s.size() + 1);
for (int i = 2; i <= s.size(); i++)
{
if (abs(s[i - 1] - s[i - 2]) <= 1)
{
dp[i] = max(dp[i - 1], dp[i - 2] + s[i - 1] - 'a' + s[i - 2] - 'a' + 2);
}
else
{
dp[i] = max(dp[i - 1], dp[i - 2]);
}
}
cout << dp[s.size()];
}
3. 完全二叉树构造
题目描述
小红想构造一个总共n个节点完全二叉树,该二叉树满足以下两个性质:
1.所有节点的权值值为1~n的一个排列。
2.除了根节点以外,每个节点的权值和它父亲的权值的乘积为偶数。
请你帮小红构造出这个二叉树,并按层序遍历的方式打印所有节点。
输入描述:
一个正整数n,代表二叉树的节点数量。
2<n<105
输出描述:
输出一行n个正整数,代表小红构造的二叉树的层序遍历的序列。
思路:
根据完全二叉树性质,只需要把奇数全放在叶子结点即可,其他节点放偶数,则只需要先输出偶数,在输出奇数即可
方法1:先输出偶数,在输出奇数
void f2(int n)
{
vec2.clear();
int o = 2;
int j = 1;
while (o <= n)
{
vec2.push_back(o);
o += 2;
}
while (j <= n)
{
vec2.push_back(j);
j += 2;
}
for(auto &i:vec2) cout<<i<<" ";
}
方法2:倒叙复制,把叶子节点赋值为奇数,其他为偶数
void f1(int n)
{
vec1.clear();
int j;
int o;
if (n & 1)
{
j = n; o = n - 1;
}
else
{
j = n - 1;
o = n;
}
for (int i = n; i > 1; i--)
{
if (j > 0)
{
a[i] = j;
j -= 2;
}
else
{
a[i] = o;
o -= 2;
}
}
for (int i = 1; i <= n; i++) cout<<a[i]<<" ";
}
验证程序:
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
int a[10000];
vector<int> vec1, vec2;
void f1(int n)
{
vec1.clear();
int j;
int o;
if (n & 1)
{
j = n; o = n - 1;
}
else
{
j = n - 1;
o = n;
}
for (int i = n; i > 1; i--)
{
if (j > 0)
{
a[i] = j;
j -= 2;
}
else
{
a[i] = o;
o -= 2;
}
}
for (int i = 1; i <= n; i++) vec1.push_back(a[i]);
}
void f2(int n)
{
vec2.clear();
int o = 2;
int j = 1;
while (o <= n)
{
vec2.push_back(o);
o += 2;
}
while (j <= n)
{
vec2.push_back(j);
j += 2;
}
}
int main()
{
int n;
a[1] = 2;
srand(time(NULL));
for (int i = 0; i < 1000; i++)
{
int n = rand() % (10000)+3;
f1(n);
f2(n);
if (vec1 != vec2)
{
cout << "0";
return 0;
}
}
cout << "1";
return 0;
}
输出为:1,验证成功。
4.小红过沼泽
小红来到了一片沼泽地的岸边,她希望能通过这片沼泽地。
这个沼泽地地图用一个矩阵进行表示。1代表沼泽,0代表平地。小红刚开始在矩阵
的左上角,她需要从右下角离开地图。已知进入地图和离开地图的时间可以忽略。
小红可以向左、向右或者向下走。
当小红从沼泽进入沼泽,或者平地进入平地时,需要花费1单位时间。
当小红从沼泽进入平地,或者平地进入沼泽时,由于需要更换装备,所以要花2单位
时间。
小红可以从左上角进入地图,从右下角离开地图。
小红想知道,经过这片沼泽地,最少需要花费多少单位时间。
输入描述:
第一行输入两个正整数n和m,用空格隔开,代表矩阵的行数和列数。
接下来的n行,每行输入m个正整数ai.aj,用来表示矩阵。
2 ≤n,m ≤ 500 , 0 ≤ ai,aj≤ 1
思路:迪杰斯特拉算法,根据输入建立图
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
#include<vector>
using namespace std;
int n, m;
const int N = 10000;
int a[N][N], d[N], v[N];
int dijkstra()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
for (int i = 1; i <= m * n; i++)
{
int t = -1;
for (int j = 1; j <= m * n; j++)
{
if (!v[j] && (t == -1 || d[t] > d[j]))
{
t = j;
}
}
v[t] = true;
for (int j = 1; j <= n * m; j++)
{
d[j] = min(d[j], d[t] + a[t][j]);
}
}
return d[n * m];
}
int main()
{
cin >> n >> m;
vector<vector<int>> vec(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> vec[i][j];
}
}
memset(a, 0x3f, sizeof(a));
//////////////////////建图,a[x][y]表示从x号到y号的权重是a[x][y]
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (j != m && vec[i][j] == vec[i][j + 1])
{
a[(i - 1) * m + j ][(i - 1) * m + j + 1] = 1;
}
else if (j != m && vec[i][j] != vec[i][j + 1])
{
a[(i - 1) * m + j][(i - 1) * m + j + 1] = 2;
}
if (i != n && vec[i][j] == vec[i + 1][j])
{
a[(i - 1) * m + j][(i) * m + j ] = 1;
}
else if (i != n && vec[i][j] != vec[i + 1][j])
{
a[(i - 1) * m + j][(i) * m + j ] = 2;
}
}
}
//////////////////////////
cout << dijkstra();
}
Q.E.D.