题目链接：https://vjudge.net/contest/147632#overview。
A题，状态压缩一下然后暴力即可。
B题，水题，略过。
C题，有负数，前缀和不是单调的，因此不能用尺取法。做法是枚举左端点i，然后在[i,n]这个范围内用线段树查找最左边的pre>=S+pre[i-1]的点，更新答案即可（和上次的巴比伦&&圣杯类似）。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <iostream>
#define t_mid (l+r>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
const int N = + ;
typedef long long ll;
typedef pair<int,int> pii; ll pre[N];
int n,S;
ll c[N<<];
void up(int o) {c[o] = max(c[ls], c[rs]);}
void build(int o,int l,int r)
{
if(l == r)
{
c[o] = pre[l];
return ;
}
build(lson);
build(rson);
up(o);
}
int Find(int o,int l,int r,int ql,int qr,ll f)
{
if(l == r)
{
if(pre[l] >= f) return l;
else return -;
}
int ans = -;
if(qr <= t_mid)
{
if(c[ls] >= f) return Find(lson,ql,qr,f);
}
else if(ql > t_mid)
{
if(c[rs] >= f) return Find(rson,ql,qr,f);
}
else
{
if(c[ls] >= f) ans = Find(lson,ql,t_mid,f);
if(ans == - && c[rs] >= f) ans = Find(rson,t_mid+,qr,f);
}
return ans;
}
void solve()
{
int ans = -;
for(int i=;i<=n;i++)
{
int now = Find(,,n,i,n,pre[i-]+S);
if(now != -)
{
if(ans == -) ans = now-i+;
else ans = min(ans, now-i+);
}
}
printf("%d\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&S);
for(int i=;i<=n;i++)
{
int t;
scanf("%d",&t);
pre[i] = pre[i-] + t;
}
build(,,n);
solve();
}
}
D题，比赛时手推了个O(n)的公式被卡- -，O(n/2)能过。做法是枚举i，在i*i的正方形内，如果i是奇数，那么里面最多有i个满足的矩形，i是偶数，则不存在。然后这样的个数有(a-i+1)*(b-i+1)个。枚举i求个和即可。当然预处理前缀和能O(1)解决。顺便记一下，前n项平方和是n(n+1)(2n+1)/6，奇数项的平方和为
1*1+3*3+5*5+...+(2n-1)*(2n-1) = 1/3*n*(2n-1)(2n+1)。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <iostream>
using namespace std;
const int N = + ;
typedef long long ll;
typedef pair<int,int> pii; int main()
{
ll a,b;
while(scanf("%lld%lld",&a,&b) == )
{
if(a == && b == ) break;
ll ans = ;
if(a > b) swap(a,b);
for(int i=;i<=a;i+=) ans += (ll)i*(a-i+)*(b-i+);
printf("%lld\n",ans);
}
return ;
}
E题，暴力枚举再组合数即可。