直接暴力从前往后寻找。假设找到1/3sum的位置，那么标记++。找到2/3的位置,总数加上标记数。
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 550000
#define mod 10000007
#define LL __int64
LL a[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
LL sum=0;
for(int i=1;i<=n;i++)
{
scanf("%I64d",&a[i]);
sum+=a[i];
}
if(sum%3)
{
cout<<"0"<<endl;
continue;
}
sum=sum/3;
LL ans=0;
LL now=0;
LL s=0;
for(int i=1;i<n;i++)
{
now+=a[i];
if(sum*2==now)
{
ans+=s;
}
if(now==sum)
{
s++;
}
}
cout<<ans<<endl;
}
return 0;
}
先把a数组变成须要加多少变成h。
然后在对a数组前向差分得出b数组。
cnt：标记到当前位置，有几个l没有和r匹配
假设b[i]==1：
说明当前位置有一个l，cnt++;
假设b[i]==0:
1，当前位置什么都没有
2，当前位置有一个l,一个r。
由于有一个l，所以cnt++.
有一个r。所以总数*=cnt,cnt--;
相当于总数*=（cnt+1）；
假设b[i]==-1:
当前位置有一个r，所以总数*=cnt,cnt--;
假设b[i]不等于上面的三种情况，说明无解！
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 550000
#define mod 1000000007
#define LL __int64
LL a[maxn];
LL b[maxn];
int main()
{
int n,h;
while(~scanf("%d%d",&n,&h))
{
for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
for(int i=1;i<=n;i++)a[i]=h-a[i];
for(int i=1;i<=n+1;i++)
{
b[i]=a[i]-a[i-1];
}
LL ans=1;
LL cnt=0;
for(int i=1;i<=n+1;i++)
{
if(b[i]==1)
{
cnt++;
}
else if(b[i]==-1)
{
ans=ans*(cnt)%mod;
cnt--;
}
else if(b[i]==0)
{
ans=ans*(cnt+1)%mod;
}
else
{
ans=0;break;
}
ans=ans%mod;
}
cout<<ans<<endl;
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。