P1738 字符串查询 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年9月5日 22:46

字符串查询题解：

P1738

回复 0 | 赞 1 | 浏览 936

个人感觉求出f数组的过程更像是dp，而非前缀和，就是要找到状态转移方程。相减的过程倒是确实是前缀和的思想。设 f[i][j]为字母j在1到i的子串出现次数,那么f[i][j]=f[i−1][j]+(j==c[i]); 求出前缀和后，求a到b子串出现字符j的次数为 f[b][j]−f[a][j−1] 最后判断询问的两个子串所含每个字母的个数是否相同即可。如果过不了的话加上取消同步 ios::sync_with_stdio(false); #include<iostream> #include<cs...

2024年3月15日 16:59

字符串查询题解：错误50% 有没有大哥看看

P1738

回复 3 | 赞 0 | 浏览 525

#include<bits/stdc++.h> using namespace std; bool cmp(char a,char b){ return a<b; } int main(){ string str; cin>>str; int n; int a,b,c,d; char a1[50000]; char a2[50000]; while(cin>>n){ for(int i=0;i<n;i++){ ...

2022年9月3日 15:38

1738 前缀合+差分复习

P1738

回复 0 | 赞 2 | 浏览 5.5k

看到这种题目 “给定q个查询...”能够很明显的定位到用前缀合解决。因为虽然算法本身时间复杂度还过得去，但是每次查询都要经过一次计算，查询次数一多，非常容易超时。所以一定是先算再存再查，提高效率。解题思路判断两个子串中每个字母的出现次数是否相同，即要计算子串中每个字母出现的次数我们可以计算出遍历到第i个字符时，每个字母在前i个字符中出现的次数，用a[i][j]表示。i表示当前的位置，j表示字母字母j在l和r区间出现的次数就等于a[r][j]-a[l-1][j]。（为什么是l-1，自己写一个字符串一算就知道...

2020年6月28日 19:53

字符串哈希表上做前缀和

P1738

回复 2 | 赞 4 | 浏览 13.4k

#include<cstdio> #include<cstring> using namespace std; int pre[50005][26]={}; char s[50005]; int main() { //freopen("1.txt","r",stdin); scanf("%s",s); for(int i=1;i<=strlen(s);i++) { char c = s[i-1]; int cur = (c-'a'); for(int j=0;j<26;j++) ...

题目字符串查询

题解数量4

热门题解

1 字符串哈希表上做前缀和

2 1738 前缀合+差分复习

3 字符串查询题解：

4 字符串查询题解：错误50% 有没有大哥看看