P2697 宝石串 洛谷——前缀和（c语言）

可以认为G是-1，R是1，然后求一个前缀和s

如果s[i]==s[j]，那么j--->i这一整段，一定是一个和为0的区间，即红绿相等的稳定区间

用前缀和sum[i]表示前i个中R比G多几个，然后从首位个找出R比G多x个并分别存入各自的数组

记住，首个非常重要，所以会判断le【i】是否为0

#include        //万能开头
using namespace std;
const int N=1000001;
char a[N];
int le[2*N+10],rig[2*N+10],sum[N+10],s;
int main()
{
    int i,l;
    scanf("%s",a);
    l=strlen(a);
    for(i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713911.html