一、打怪
思路
由于是先手攻击，如果一次攻击就能杀死小怪，那么说明可以为无限杀小怪。
再计算杀一只小怪要扣多少血就好了，再用总生命值去除这个扣血量，得到的就是最多杀死小怪的数量。注意，由于最后一定要活下来，最少要保留一滴血。我们可以拿h-1去计算就好了。
时间复杂度O(1),总时间复杂度O(t)。
代码：
#include <iostream> using namespace std; int main() { int t; cin>>t; while(t--){ int h,a,H,A; cin>>h>>a>>H>>A; if(a>=H){ cout<<"-1"; if(t)cout<<endl; continue; } int k1=(H+a-1)/a;//几个回合杀死小怪 int c=(k1-1)*A;//每杀死一个小怪寇多少血 cout<<(h-1)/c; if(t)cout<<endl; } return 0; } // 64 位输出请用 printf("%lld")
二、字符串分类
思路
思考这样一个结论：一个字符串如果可以任意交换相邻位置，代表这个字符串可以随意排列。
即如果字符串A和字符串B有一样种类的字符且每种字符数量都相等。那么AB一定可以通过交换位置变成相等。
所以我们只需要比较AB每一种字符的数量和种类是否相等就好了。
给出一个技巧，直接将AB排序之后比较看是否一样就好了。时间复杂度为O(nlogm),m为字符串长度。
代码：
#include <iostream> #include<unordered_map> #include<string> #include<algorithm> using namespace std; const int N=60; int main() { int n; cin>>n; string str; int ans=0; unordered_map<string,int> mp; for(int i=1;i<=n;i++){ cin>>str; sort(str.begin(),str.end()); if(!mp.count(str)){ ans++; mp[str]++; } } cout<<ans<<endl; return 0; }
三、城市群的数量
思路
并查集。染色搜索也行。
每次将一条边上的两个点加入到一个集合里面，最后计算集合的·数量就好了。数组p[i]的值表示 i节点所在集合的编号。初始时所有的城市所在集合编号就是他自己。
代码：
class Solution { public: int find(int x,vector<int>& p){ if(p[x]!=x)p[x]=find(p[x],p); return p[x]; } int citys(vector<vector<int> >& m) { int n=m.size(); vector<int> p(n+1); for(int i=1;i<=n;i++)p[i]=i; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(m[i][j]==1){ int x=find(i+1,p); int y=find(j+1,p); if(x==y)continue; p[x]=y; } } } int ans=n; for(int i=1;i<=n;i++){ if(p[i]!=i)ans--; } return ans; } };
