找闭区间上最多的字母个数

Question

这个为什么不能找到在闭区间[l,r]上最多的字母个数啊？自己测的全对，提交直接WA了，而且0分

#include<bits/stdc++.h>
using namespace std;
int n,m;
char ch[1000000];
int  f[1000000][30];
int main()
{
    cin>>n>>m;
    scanf("%s",ch);
    int i,j;
    for(i=0;i<26;i++)
    {
        for(j=0;ch[j]!='\0';j++)
        {
            f[i][j+1]=f[i][j]+(ch[j]=='a'+i);
    }
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        int maxn=0;
        for(i=0;i<26;i++)
        {
            int cint=f[i][r]-f[i][l-1];
            maxn=max(maxn,cint);
    }
        cout<<maxn<<endl;
    }
    return 0;
}

Answer 1

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7787965
• 这篇博客你也可以参考下：【C语言】请统计某个给定范围[L, R]的所有整数中，数字 2 出现的次数。
• 除此之外, 这篇博客: 求区间[L,R]内某个数出现的次数（二分/分块）中的 思路 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  ---

  用vector保存每个数的下标，所有a[x]中就会保存x在数组中所有的下标，并且我们是按顺序添加的，所有下标是递增的，然后枚举所有小于等于最大编号并且是x的倍数的编号，二分查找这个数的所有满足在[L,R]内数有多少个。

  ---

  #include <bits/stdc++.h>
  #define ull unsigned long long
  #define ll long long
  const int inf = 0x3f3f3f3f;
  const int mod = 1e9+7;
  const int N = 2e6+7;
  const int ds = 1e8+7;
  const int base = 233;
  const double PI = 3.141592653589793238462643383;
   
  using namespace std;
  
  int a[N];
  vector<int>b[N];
  void solve() {
  	int n,q,mmax = 0;
  	cin >> n >> q;
  	for(int i = 1; i <= n; i++) {
  		cin >> a[i];
  		b[a[i]].push_back(i);
  		mmax = max(mmax,a[i]);
  	}
  	while(q--){
  		int l,r,x;
  		cin >> l >> r >> x;
  		int ans = 0;
  		for(int i = x; i <= mmax; i += x){
  			if(b[i].size() == 0) continue;
  			int xb1 = lower_bound(b[i].begin(),b[i].end(),l) - b[i].begin();
  			int xb2 = upper_bound(b[i].begin(),b[i].end(),r) - b[i].begin();
  			ans += xb2-xb1;
  		}
  		cout << ans << endl;
  	}
  }
  
  int main() { 
  //	int t;
  //	scanf("%d",&t);
  //	while(t--)
  		solve();
  	return 0;
  }

  https://ac.nowcoder.com/acm/contest/12478/A

  ---

  如果两个字符串，通过不同的字目映射关系可以转换为一样的中文意思，那么称这两个暗号本质相同,比如“lff”，“dee”，“kbb”“lff”，“dee”，“kbb”“lff”，“dee”，“kbb”都是本质相同的。

  其实也就是成语中的AABB形，ABAB形成语这种说法。如果给出n个串，q次询问，问[L,R]与串t本质相同的个数。

  ---

  先处理n个串，判断每个串是哪种形的，利用数字来表示，比如1212，就是ABAB形，1122就是AABB形，然后用map<string,vector<int>>mp去保存这种形的串的下标。

  然后q次询问的时候先判断t是哪种形的串，同样利用二分去查找下标在[L,R]内有多少个。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^