一、 打怪

題目解析

我們現在要去刷毛球怪，我的攻擊和血量是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;}
};

到這里本篇文章內容就結束了
感謝各位的支持