C++笔试强训day23

1.打怪

2.字符串分类

3.城市群数量

1.打怪

链接

模拟题目，按题意进行模拟就行。

#include <iostream>
using namespace std;
// 简单模拟
int solve()
{int h, a, H, A;cin >> h >> a >> H >> A;if (a >= H)return -1;int cnt = 0;int tmpH = H;while (h > 0){tmpH -= a;if (tmpH > 0)h -= A;if (tmpH <= 0){cnt++;tmpH = H;}}return cnt;
}
int main() {int t;cin >> t;while (t--)cout << solve() << endl;
}

2.字符串分类

链接

我的思路是将每个 string 存入 vector 里面，然后排序每个string，遍历vector，将不同种类的string存入tmp（vector<string>）中，返回tmp.size()即可。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {int n;cin >> n;vector<string> vs(n);for (int i = 0; i < n; ++i)cin >> vs[i];for (auto& s : vs)sort(s.begin(), s.end());vector<string> tmp;for (int i = 0; i < n; ++i){int flag = 1;for (auto s : tmp){if (vs[i] == s)flag = 0;}if (flag)tmp.push_back(vs[i]);}cout << tmp.size() << endl;return 0;
}

方法二：

也可以不用这么麻烦，可以直接定义一个unordered_set，将排序后的每个string扔进去，直接返回它的size即可。

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
int n;
string s;
int main()
{cin >> n;unordered_set<string> hash;while (n--){cin >> s;sort(s.begin(), s.end());hash.insert(s);}cout << hash.size() << endl;return 0;
}

3.城市群数量

链接

我的方法是用图存储每个城市连接的城市（多个），for循环遍历每个城市，若没有遍历过，之间cnt++，然后dfs遍历该城市连接所有城市，以及它连接的城市连接的所有城市。

#include <unordered_map>
#include <vector>
#include <algorithm>
vector<bool> vim(210);
class Solution {
public:// 检查连接的城市是否遍历完bool Check(int i) {for (int e : edges[i])if (vim[e] == false)return true;return false;}// DFSvoid f(unordered_map<int, vector<int>> edges, int i) {vim[i] = true;if (Check(i) == false)return;for (int e : edges[i]) {if (vim[e] == false) {f(edges, e);}}}// 建图unordered_map<int, vector<int>> edges;int citys(vector<vector<int> >& m) {int line = m.size();int col = m[0].size();for (int i = 0; i < line; ++i) {for (int j = 0; j < col; ++j) {if (m[i][j] == 1 && i != j) {edges[i + 1].push_back(j + 1);}}}int cnt = 0;for (int i = 1; i <= line; ++i) {if (vim[i] == false) {cnt++;f(edges, i);}}return cnt;}
};

唯一的细节就是：

遍历到的这个城市先标记后，再去判断是否有连接的但是没遍历到的城市。