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.