https://www.acwing.com/problem/content/5157/
利用贡献思想入门的一道题,对于看起来复杂的问题,我们去考虑每一个元素在每一轮中的贡献,如果这道题不理解了可以去看视频讲解,里面说的非常明晰。
在本题实现过程中需要找到找到数组中的最大数,并且统计有几个同时最大的数,我的实现非常不好,用stl麻烦了,参考一下别人优雅的实现。
for (int i = 0; i < n; i ++ )
{
int t = ++ cnt[s[i]];
if (t > mx) mx = t, ct = 1;
else if (t == mx) ct ++ ;
}
- 上面代码中不断维护最大值以及最大值的数的个数
#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod =1e9+7;
const double eps = 1e-8;
int n, m;
int a[N];
int qmi(int a,int b,int p){
int res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res%p;
}
void solve(){
map<char,int>mp;
cin>>n;
string s;
cin>>s;
for(int i=0;i<n;i++){
mp[s[i]]++;
}
vector<int>v;
for(auto[x,y]:mp){
v.push_back(y);
}
int cnt=0;
int tmp=*max_element(v.begin(),v.end());
for(auto[x,y]:mp){
if(y==tmp)cnt++;
}
int ans=qmi(cnt,n,mod);
cout<<ans<<endl;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
t=1;
while (t--) {
solve();
}
return 0;
}
标签:cnt,int,long,++,5157,define
From: https://www.cnblogs.com/mathiter/p/17729485.html