首页 > 其他分享 >5157

5157

时间:2023-09-26 10:13:24浏览次数:47  
标签:cnt int long ++ 5157 define

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

相关文章

  • 浅析GeoServer CVE-2023-25157 SQL注入
    简介GeoServer是一个开源的地图服务器,它是遵循OpenGISWeb服务器规范的J2EE实现,通过它可以方便的将地图数据发布为地图服务,实现地理空间数据在用户之间的共享。影响版本geoserver<2.18.72.19.0<=geoserver<2.19.72.20.0<=geoserver<2.20.72.21.0<=geoserver<2.21.42.22.0<=......
  • hdu 5157(manacher+前缀和+树状数组)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5157解题思路:我们可以先用mancher算法对字符串进行处理,把以每个点为中心的回文串半径求出来,然后进行处理。加入对以p为中心的点,从p-r[i]+1~p都是回文串的开头,那么对于每个回文串(开头是j)只要记录结尾从1~j-1的回文串个数,我们可......