Codeforces Round 959 (Div. 1 + Div. 2) C. Hungry Games题解
大致题意： 给定一个长度为n的数组，并且给出一对l,r表示一个区间，如果 ∑ i = l r a [ i ] \sum_{i=l}^{r}a[i] ∑i=lra[i]不为0的话称这样的一个区间是好区间。相加的过程中遵循如下操作：当累加值小于等于x不执行操作，如果大于x，那么累加值就变为0。
思路分析： 本题可以使用DP来求解。我们定义
d
p
[
i
]
dp[i]
dp[i]表示以i为区间左端点满足题意区间的数量。根据a的取值发现，累加过程中，在
g
<
=
x
g<=x
g<=x 时，g是逐渐增大的。那么如果存在的这样一个
r
r
r 使得
g
g
g 的值第一次超过而变成0,那么之后的状态可以通过
d
p
[
r
+
1
]
dp[r+1]
dp[r+1] 来转移。
记这样的
r
r
r 为idx。那么可以得到状态转移方程。
d
p
[
i
]
=
d
p
[
i
d
x
]
+
i
d
x
−
i
dp[i]=dp[idx]+idx-i
dp[i]=dp[idx]+idx−i
这样的
r
r
r 可以通过二分或者直接使用
u
p
p
e
r
b
o
u
n
d
upper_bound
upperbound函数来求得。
***代码如下： ***
#include <iostream>
#include <cstring>
#include <map>
#include <cmath>
#include <numeric>
#include <queue>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
using pii=pair<int,int>;
const int N=2e5+10;
long long a[N];
int dp[N];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof dp);
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=n;i>=1;i--)
{
int l=i,r=n;
int res=n+1;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]-a[i-1]>x)
{
r=mid-1;
res=mid;
}
else l=mid+1;
}
dp[i]=dp[res+1]+res-i;
}
long long ans=0;
for(int i=1;i<=n;i++) ans+=dp[i];
cout<<ans<<endl;
}
return 0;
}