2017 ZSTU寒假排位赛 #2

　　题目链接：https://vjudge.net/contest/147632#overview。

　　A题，状态压缩一下然后暴力即可。

　　B题，水题，略过。

　　C题，有负数，前缀和不是单调的，因此不能用尺取法。做法是枚举左端点i，然后在[i,n]这个范围内用线段树查找最左边的pre>=S+pre[i-1]的点，更新答案即可（和上次的巴比伦&&圣杯类似）。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <iostream>
 9 #define t_mid (l+r>>1)
10 #define ls (o<<1)
11 #define rs (o<<1|1)
12 #define lson ls,l,t_mid
13 #define rson rs,t_mid+1,r
14 using namespace std;
15 const int N = 500000 + 5;
16 typedef long long ll;
17 typedef pair<int,int> pii;
18 
19 ll pre[N];
20 int n,S;
21 ll c[N<<2];
22 void up(int o) {c[o] = max(c[ls], c[rs]);}
23 void build(int o,int l,int r)
24 {
25     if(l == r)
26     {
27         c[o] = pre[l];
28         return ;
29     }
30     build(lson);
31     build(rson);
32     up(o);
33 }
34 int Find(int o,int l,int r,int ql,int qr,ll f)
35 {
36     if(l == r)
37     {
38         if(pre[l] >= f) return l;
39         else return -1;
40     }
41     int ans = -1;
42     if(qr <= t_mid)
43     {
44         if(c[ls] >= f) return Find(lson,ql,qr,f);
45     }
46     else if(ql > t_mid)
47     {
48         if(c[rs] >= f) return Find(rson,ql,qr,f);
49     }
50     else
51     {
52         if(c[ls] >= f) ans = Find(lson,ql,t_mid,f);
53         if(ans == -1 && c[rs] >= f) ans = Find(rson,t_mid+1,qr,f);
54     }
55     return ans;
56 }
57 void solve()
58 {
59     int ans = -1;
60     for(int i=1;i<=n;i++)
61     {
62         int now = Find(1,1,n,i,n,pre[i-1]+S);
63         if(now != -1)
64         {
65             if(ans == -1) ans = now-i+1;
66             else ans = min(ans, now-i+1);
67         }
68     }
69     printf("%d
",ans);
70 }
71 
72 int main()
73 {
74     int T;
75     scanf("%d",&T);
76     while(T--)
77     {
78         scanf("%d%d",&n,&S);
79         for(int i=1;i<=n;i++)
80         {
81             int t;
82             scanf("%d",&t);
83             pre[i] = pre[i-1] + t;
84         }
85         build(1,1,n);
86         solve();
87     }
88 }

View Code

　　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)。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <iostream>
 9 using namespace std;
10 const int N = 500000 + 5;
11 typedef long long ll;
12 typedef pair<int,int> pii;
13 
14 int main()
15 {
16     ll a,b;
17     while(scanf("%lld%lld",&a,&b) == 2)
18     {
19         if(a == 0 && b == 0) break;
20         ll ans = 0;
21         if(a > b) swap(a,b);
22         for(int i=1;i<=a;i+=2) ans += (ll)i*(a-i+1)*(b-i+1);
23         printf("%lld
",ans);
24     }
25     return 0;
26 }

View Code

　　E题，暴力枚举再组合数即可。