【C++】 —— 笔试刷题day_23

一、 打怪

题目解析

我们现在要去刷毛球怪，我的攻击和血量是h和a、毛球怪的攻击和血量是H和A； 我们和毛球怪的对决是轮流攻击(我们先手)，当血量小于等于0时死亡； 现在我们要求在自己存活的条件下，最多能够杀死几只毛球怪；最后输出这个数量。

注意：如果能够杀死无数只怪物，就输出-1

算法思路

对于这道题，首先我们想到的可能就是模拟整个打怪过程，然后记录杀死怪物的数量。

而对于模拟整个过程，程序运行的时间也太长了；而且如果我们能够杀死无数只怪物，那我们要一直模拟整个过程；那也太麻烦了 有没有更加简单的方法？

这道题我们每一个怪物的血量和攻击都是固定的，那我们能不能求出来我们杀死一只怪物所受到的伤害，在根据我们自身的血量，不就可以直接计算出我们能够杀死多少只怪物吗？

所以我们的思路就是先求出来我们杀死一只怪物要攻击多少次，再求出自己所受到的伤害，最后直接计算出能够杀死怪物的数量。

• 计算杀死一只怪要攻击多少次：m = H/a + (H%a == 0?0:1);
• 我们要受到多少次攻击：n = m-1;（我们先手，所以我们受到攻击的次数比我们攻击的次数少一)
• 我们杀死一只怪要受到的伤害：r = m*A;（我们受到的伤害就等于受到攻击的次数*怪物的攻击）
• 能杀死怪物的最多数量：ret = h%r==0?(h/r-1):h/r; 题目的前提是我们要存活下来，如果h%r==0，那在面对第h/r这只怪物时，我们的生命值是先减到0的，所以我们杀不死这一只怪，杀怪的数量就等于h/r -1；如果h%r != 0，那就说明杀死第h/r只怪以后我们还是存活的，那杀怪的数量就是h/r。

最后我们来处理一下能够杀死无数只怪的问题

如果能够杀死无数只怪，那就说明我们杀死一只怪是没有掉生命值的； 那只有我们能够一次攻击杀死怪物才会无伤打怪，那也就是说我们的攻击a要大于等于怪物的生命H的。 所以当a>=H时，输出-1即可。

代码实现

#include<iostream>
using namespace std;
int h,a,H,A;

int fun()
{
    if(H<=a)
        return -1;
    int n = H/a + (H%a == 0?0:1);//几次攻击能杀死一只怪
    int m = n-1;//杀死一只怪要受到几次怪物的攻击。
    int r = m*A;//杀死一只怪要受到的伤害
    int ret = h%r == 0? h/r-1:h/r;
    return ret;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>h>>a>>H>>A;
        cout<<fun()<<endl;
    }
    return 0;
}

二、字符串分类

题目解析

这里题目给定t个字符串，让我们对这t个字符串进行分类； 对于字符串A和B，如果A可以通过交换任意位置的两个字符，可以变换到B（可以交换无数次）那字符串A和B就是属于同一类字符串； 例如：abcd、abdc、dcba这些字符串都属于同一类。

算法思路

对于两个字符串，如果它们属于同一类，那这两个字符串中字符的种类和每一个字符出现的次数都是相等的。

如果我们直接去判断两个字符串中字符种类和字符出现的次数，那就非常麻烦了； 这里我们想一想，如果A和B字符串属于同一类，那它们中字符的种类和出现的次数都是相等的，那如果我们将字符串排一下序，那A和B排序后的结果是不是同一个字符串呢？

很显然是的，abcd和dcba排序之后都是abcd；

那字符串经过排序后的字符串是相等的，那这些字符串是不是都属于同一类字符串；

所以，我们这里思路就是：先对字符串进行排序，在记录一下排序后字符串的种类即可

• 排序字符串：使用sort即可
• 记录排序后字符串的种类：使用hash记录排序后字符串的种类
• **结果：**我们只需要去hash表中查看字符串要多少种即可。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

int main() {
    int t;
    cin >> t;
    unordered_set<string> hash;
    while (t--) {
        string str;
        cin >> str;
        sort(str.begin(), str.end());
        hash.insert(str);
    }
    cout << hash.size() << endl;
}

三、城市群数量

题目解析

题目给定一个n阶矩阵，其中每一个位置是0或1； 如果dp[i][j] == 1就表示，第i个城市和第j个城市相连；（如果a城市和b城市相连，b和c城市相连，那就任务a城市和c城市相连。 现在我们要去求在这n个城市中，有多少个城市群。

算法思路

这道题，就是一道搜索题目，我们要使用深度优先遍历dfs或者广度优先遍历来解决bfs。

思路简单来说就是，遍历每一个城市，如果这个城市还没有和其他城市成群，那就从当前城市来一次深度优先遍历dfs，将它所在城市群的所有城市成群；

最后，我们只需要记录进行了几次dfs（进行了多少次dfs那就表示存在多少个城市群）。

代码实现

class Solution {
  public:
    bool vis[201] = {false};
    void dfs(vector<vector<int> >& m, int pos, int n) {
        vis[pos] = true;
        for (int i = 0; i < n; i++) {
            if (m[pos][i] == 1 && vis[i] == false)
                dfs(m, i, n);
        }
    }
    int citys(vector<vector<int> >& m) {
        int n = m.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (vis[i] == false) {
                ret++;
                dfs(m, i, n);
            }
        }
        return ret;
    }
};

到这里本篇文章内容就结束了 感谢各位的支持