主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
答疑区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
shanniah
2024年9月5日 22:46
字符串查询 题解:
P1738
回复 0
|
赞 1
|
浏览 863
个人感觉求出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...
08193003
2024年3月15日 16:59
字符串查询 题解:错误50% 有没有大哥看看
P1738
回复 3
|
赞 0
|
浏览 506
#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,自己写一个字符串一算就知道...
all-clear
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% 有没有大哥看看