本文主要是介绍CF 780 F2. Promising String (hard version)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题外话：本次考试基本都是数据结构题目。博主感觉做起来很顺......当然WA是不可避免的......
题目大意：一个字符串只包含+ 和 -两种字符，满足要求的子串或者是+和-数量相同，如+-，++--。或者是-号与+号的数量差为3的倍数，因为两个-可以升级成promising一个+。
这样问题就是求某个子串，其中-号数量减去+号数量是3的倍数。
解题思路：我们把+号看成-1，减号看成1。这样问题就变成求一个序列中有多少个子段，其“子段和大于等于0且为3的倍数”。
本题目还有个F1 （easy）版本，长度小于3000，可以双循环暴力枚举子段[i,j]，用前缀和预处理[i,j]这一段的结果，判断是否满足条件，复杂度O(n^2）。
本题解法：如果一个子段右端点是i,那么如何找到满足条件的左端点，根据前缀和的思想距离，例如sum[i]=8,那么只要左端点前结果是8,5,2-1，-4.....，sum[i]减去这些值结果一定是3的倍数，这些值的特点是对3求余均为2。插播一个小知识，负数求余直接%结果是错的哦，如果解决请参看下方代码。因此当处理到第i个字符时，如果此时sum[i]=X,那么i左侧有多少个位置，其前缀和<=X,同时与X对3同余，这些位置都能和i组成满足条件的字段。
这样为题就转换成求sum[i]左边有多少个比它小且同余的sum[?]数量。由于递推过程中，不同数组的数量也在不断变化，这种可变的区间和问题可用树状数组或线段树解决。至于如何处理同余，因为对3求余结果只有3种可能，我这里开了3个树状数组，分别存储余数为0,1,2的对应数据。根据余数到对应树状数组求和。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t,n,sum[3][800005];
char s[200005];
int lowbit(int x)/**< lowbit的作用请草稿纸模拟 */
{return x&(-x);
}
void update(int pos,int P) /**< 树状数组模板 */
{for(; pos<=n+n; pos+=lowbit(pos))sum[P][pos]++;
}
int getsum(int pos,int P)
{int s=0;for(;pos>0;pos-=lowbit(pos))s+=sum[P][pos];return s;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j;cin>>t;while(t--){int cnt=0;ll ans=0;cin>>n>>s+1;for(i=0;i<=4*n;i++)/**< 树状数组初始化 */sum[0][i]=sum[1][i]=sum[2][i]=0;update(0+n,0);/**< 这个处理区间[1...i]满足条件的情况 */for(i=1; i<=n; i++){cnt=cnt+(s[i]=='+'?-1:1);ans+=getsum(cnt+n+1,(cnt%3+3)%3);/**< 找到比cnt小的数字个数 */update(cnt+n+1,(cnt%3+3)%3);/**< 把数据存到树状数组，因为可能是负数，所以加一个偏移量 *//**< 切记不能出现0，不然死循环，我开始写的cnt+n，连挂几次 */}cout<<ans<<endl;}return 0;
}
这篇关于CF 780 F2. Promising String (hard version)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
