一、打怪
题目解析
我们现在要去刷毛球怪，我的攻击和血量是
h和a、毛球怪的攻击和血量是H和A；我们和毛球怪的对决是轮流攻击 (我们先手)，当血量小于等于
0时死亡；现在我们要求在自己存活的条件下，最多能够杀死几只毛球怪；最后输出这个数量。
注意：如果能够杀死无数只怪物，就输出 -1
算法思路
对于这道题，首先我们想到的可能就是模拟整个打怪过程，然后记录杀死怪物的数量。
而对于模拟整个过程，程序运行的时间也太长了；而且如果我们能够杀死无数只怪物，那我们要一直模拟整个过程；那也太麻烦了。
有没有更加简单的方法？
这道题我们每一个怪物的血量和攻击都是固定的，那我们能不能求出来我们杀死一只怪物所受到的伤害，在根据我们自身的血量，不就可以直接计算出我们能够杀死多少只怪物吗？
所以我们的思路就是先求出来我们杀死一只怪物要攻击多少次，再求出自己所受到的伤害，最后直接计算出能够杀死怪物的数量。
计算杀死一只怪要攻击多少次：m = H/a + (H%a == 0?0:1);
我们要受到多少次攻击：n = m-1;（我们先手，所以我们受到攻击的次数比我们攻击的次数少一）
我们杀死一只怪要受到的伤害：r = n*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;
return 0;
}
三、城市群数量
题目解析
题目给定一个
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;
}
};