天津市建设银行租房网站,口碑营销例子,合肥企业网站建设专家,苏州html网站模板小郑的蓝桥平衡串
思路#xff1a;把 L 看成 1#xff0c;Q 看成 -1#xff0c;利用前缀和来得到输入串的前缀子串中LQ 的和#xff0c;利用前缀和差的性质得到子串#xff0c;通过枚举看它是否平衡。 将L看做1#xff0c;Q看做#xff0d;1#xff0c;只有当某个区间…小郑的蓝桥平衡串
思路把 L 看成 1Q 看成 -1利用前缀和来得到输入串的前缀子串中LQ 的和利用前缀和差的性质得到子串通过枚举看它是否平衡。 将L看做1Q看做1只有当某个区间的和为0时字符串是平衡的。 我们可以预处理出前缀和然后枚举所有区间这一步的时间复杂度是On^2的得到所有平衡区间的长度最后取大输出即可。
#includeiostreamusing namespace std;
const int len 1e310;
char str[len];
int prefix[len];int main( ){scanf(%s,str1);int n strlen(str1);for(int i1;in;i)prefix[i] prefix[i-1](str[i]L?1:-1);int ans0;for(int i1;in;i){for(int ji;jn;j){if(prefix[j]-prefix[i-1]0){ans max(ans,j-i1);}}}coutans\n;return 0;
}
区间次方和
思路利用前缀和求出各个幂次的区间和询问的时候直接查询。 由于k比较小所以我们可以处理出五个数组分别表示不同的次方例如a3中的元素都是数组a中元素的3次方。 再对五个数组预处理出前缀和对于每次询问利用前缀和的性质可O1解决。
#includeiostream
using namespace std;
using ll long long;
const int N 1e510;
const ll p 1e97;
int l,r,k;
int n,m;
ll a[6][N],prefix[6][N];int main( ){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i)cina[1][i];for(int i2;i5;i)for(int j1;jn;j)a[i][j](a[1][j]*a[i-1][j])%p;for(int i1;i5;i){for(int j1;jn;j){prefix[i][j] ( prefix[i][j-1]a[i][j])%p;}}while(m--){cinlrk;cout(prefix[k][r]-prefix[k][l-1]p)%p\n;}return 0;
}
