【20191102】考试

T1 最大K段和

考场上想了一个贪心：处理出所有仅含正数的极大区间。如果区间数量$\le m$，直接把所有正数的和输出即可。否则，我们选取前$m$大区间，进行以下操作使结果最大化： · 合并两个已选区间，尝试选取更多未选区间 · 合并一个已选区间和一个未选区间 实现比较繁琐，敬请参考代码：

#include<bits/stdc++.h> #define ll long long using namespace std; const int mn = 100005; struct node{ int l, r, id; ll sum; bool operator< (const node x) {return sum > x.sum;} }h[mn], tmp[mn]; int a[mn], cnt, cho[mn], tot; ll s[mn]; bool vis[mn]; int main() { int n, m; ll ans = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + 1ll * a[i]; for(int i = 1; i <= n; i++) if(a[i] >= 0) { h[++cnt] = (node) {i, i + 1, 0, a[i]}, h[cnt].id = cnt; while(h[cnt].r <= n && a[h[cnt].r] >= 0) h[cnt].sum += a[h[cnt].r], ++h[cnt].r; --h[cnt].r, i = h[cnt].r; } if(cnt <= m) { for(int i = 1; i <= cnt; i++) ans += h[i].sum; printf("%lld\n", ans); return 0; } for(int i = 1; i <= cnt; i++) tmp[i] = h[i]; sort(tmp + 1, tmp + 1 + cnt); for(int i = 1; i <= m; i++) ans += tmp[i].sum, vis[tmp[i].id] = 1, cho[++tot] = tmp[i].id; ++m; int las = 1; for(int i = 1; i <= cnt && m <= cnt; ) if(vis[i]) { bool flg = 0; for(int j = las + 1; j <= cnt; j++) if(vis[j]) { flg = 1; if(h[i].r < tmp[m].l && tmp[m].r < h[j].l) { ll del = max(s[h[j].l - 1] - s[tmp[m].r], s[tmp[m].l-1] - s[h[i].r]); if(del + tmp[m].sum >= 0) ans += del + tmp[m].sum, vis[tmp[m].id] = 1, cho[++tot] = tmp[m].id, i = (del == (s[tmp[m].l-1] - s[h[i].r]) ? tmp[m].id : j), ++m; } else if(tmp[m].sum + s[h[j].l-1] - s[h[i].r] >= 0) ans += tmp[m].sum + s[h[j].l-1] - s[h[i].r], vis[tmp[m].id] = 1, cho[++tot] = tmp[m].id, i = j, ++m; else i = j; if(i == j) las = j; else las = j - 1; break; } if(!flg) break; } else ++i; sort(cho + 1, cho + 1 + tot); for(int i = 1; i <= cnt; i++) if(!vis[i]) { int r = lower_bound(cho + 1, cho + tot + 1, i) - cho; if(r == tot) { ll del = s[h[i].l-1] - s[h[cho[r]].r]; if(del + h[i].sum >= 0) ans += del + h[i].sum, cho[r] = i; } int l = cho[r - 1], pos = r; r = cho[r]; ll del = max(s[h[r].l - 1] - s[h[i].r], s[h[i].l-1] - s[h[l].r]); if(del + h[i].sum >= 0) { ans += del + h[i].sum; if(del == s[h[i].l-1] - s[h[l].r]) cho[pos] = i; else i = pos; } } printf("%lld\n", ans); }

---

T2

就是对原序列镜像以后求LIS

#include<bits/stdc++.h> using namespace std; const int mn = 100005; int a[mn << 1], f[mn << 1]; int c[mn], num[mn], cnt; inline void update(int p, int v) {while(p <= cnt) c[p] = max(c[p], v), p += p & -p;} inline int getmax(int p) { int ret = 0; while(p) ret = max(ret, c[p]), p -= p & -p; return ret; } int main() { //freopen("dequexlis.in", "r", stdin); //freopen("dequexlis.out","w",stdout); int n; scanf("%d", &n); for(int i = n + 1; i <= (n << 1); i++) scanf("%d", &a[i]), a[(n << 1) - i + 1] = a[i], num[++cnt] = a[i]; n <<= 1, sort(num + 1, num + 1 + cnt), cnt = unique(num + 1, num + 1 + cnt) - num - 1; for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + cnt, a[i]) - num; for(int i = 1; i <= n; i++) f[i] = getmax(a[i] - 1) + 1, update(a[i], f[i]); printf("%d\n", *max_element(f + 1, f + 1 + n)); }

---

T3 最大前缀和

机房dalao想出了$O(n)$方法。 我们把$+1$、$-1$看成在坐标系中走路，+1为往右上方走，-1往右下方走（如图） 那么原问题就相当于从图中的(0,0)走到(n+m,n-m)。由题意不难得出，走过去的方案数为$C_{n+m}^n$。 原问题要求我们求所有前缀最大值之和。不妨枚举这个最大值$i$（显然 $i\in [n-m,n]$），然后考虑计算每一个最大值的贡献。 枚举了$i$后，就是要求恰好过$y=i$的折线数目。不妨先求不超过$y=i$的折线数，那么就可以用总方案数-不合法数计算，即$C_{n+m}^n-C_{n+m}^{m+i+1}$。之后再减去在$y=i-1$及以下的数目即可。

#include<bits/stdc++.h> #define ll long long using namespace std; const int mn = 8005, mod = 998244853; ll frac[mn], inv[mn]; inline void init(int n) { frac[0] = 1; for(int i = 1; i <= n; i++) (frac[i] = frac[i-1] * 1ll * i) %= mod; inv[0] = inv[1] = 1; for(int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; for(int i = 2; i <= n; i++) (inv[i] *= inv[i-1]) %= mod; } inline ll C(int n, int m) {return n < m ? 0 : frac[n] * inv[m] % mod * inv[n - m] % mod;} int main() { int n, m; scanf("%d%d", &n, &m), init(n + m); ll ans = 0, las = 0; for(int i = n - m; i <= n; i++) { ll tmp = (((C(n + m, n) - C(n + m, m + i + 1)) % mod - las) % mod + mod) % mod; (las += tmp) %= mod; if(i > 0) (ans += tmp * 1ll * i) %= mod; } printf("%lld\n", ans); }