【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>usingnamespace std;int h,a,H,A;intfun(){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;}intmain(){int t; cin>>t;while(t--){ cin>>h>>a>>H>>A; cout<<fun()<<endl;}return0;}

二、字符串分类

题目解析

这里题目给定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>usingnamespace std;intmain(){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那就表示存在多少个城市群）。

代码实现

classSolution{public:bool vis[201]={false};voiddfs(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);}}intcitys(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;}};

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