一、 打怪
题目解析
我们现在要去刷毛球怪，我的攻击和血量是
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;}
};
到这里本篇文章内容就结束了
感谢各位的支持
