思路：

对于small数据，由于求和及奇数数量两个限制条件均满足区间单调性，可以直接使用尺取法（滑动窗口法）求解。

对于large数据，奇数数量依然是满足区间单调性的。首先使用尺取法，找到所有满足奇数限制条件的区间，然后对于每个区间分别计算不超过D的最大连续子段和。具体来说，可将区间的所有前缀和放到一个multiset中，二分查找即可。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 const int MAXN = 500005;
 7 const ll INF = 0x3f3f3f3f3f3f3f3f;
 8 
 9 ll s[MAXN], sum[MAXN];
10 
11 int main()
12 {
13     int T, n;
14     ll o, d, a, b, c, m, l;
15     cin >> T;
16     for (int t = 1; t <= T; t++)
17     {
18         cin >> n >> o >> d;
19         cin >> s[1] >> s[2] >> a >> b >> c >> m >> l;
20         for (int i = 3; i <= n; i++)
21             s[i] = (a * s[i - 1] + b * s[i - 2] + c) % m;
22         for (int i = 1; i <= n; i++) s[i] += l;
23         for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i];
24         ll maxn = -INF;
25         int start = 1, odd = 0;
26         multiset<ll> st;
27         for (int i = 1; i <= n; i++)
28         {
29             odd += (s[i] & 1);
30             st.insert(sum[i - 1]);
31             while (start <= i && odd > o)
32             {
33                 odd -= (s[start] & 1);
34                 st.erase(sum[start - 1]);
35                 start++;
36             }
37             if (start <= i)
38             {
39                 auto it = st.lower_bound(sum[i] - d);
40                 if (it != st.end()) maxn = max(maxn, sum[i] - *it);
41             }
42         }
43         cout << "Case #" << t << ": ";
44         if (maxn == -INF) cout << "IMPOSSIBLE" << endl;
45         else cout << maxn << endl;
46     }
47     return 0;
48 }

 

版权声明：本文为wangyiming原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/wangyiming/p/9873586.html