YACS 2022年12月月赛 甲组 T1 分割序列 题解
管理员
这题是 子串的平均数 的进阶版，建议先去做子串的平均数再来做这一题。
双倍经验：$LuoguP2344$。
暴力
先考虑 $O(n ^ 2)$ $dp$，设 $f[i]$ 为分到第 $i$ 头牛的合法方案数。
那么枚举这一组怎么分，就可以了。
状态转移方程：$f[i] = sumlimits_{j = 0}^{i-1} (sum_i geq sum_{j})times f[j]$
代码：
#include <iostream> using namespace std; int n; int a[200005], f[200005]; long long sum; int main () { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; f[0] = 1; for (int i = 1; i <= n; i ++) { long long sum = 0; for (int j = i; j >= 1; j --) { sum += a[j]; if (sum >= 0) f[i] = (f[i] + f[j - 1]) % 10000007; } } cout << f[n] << "n"; return 0; }
优化
这个东西一看就知道可以用动态开点权值线段树来优化，算出了 $f[i]$ 后，我们就在 $sum[i]$ 的位置加上 $f[i]$。
$f[i +1]$ 就是小于等于 $sum[i +1]$ 的所有位置的和。
最终时间复杂度：$O(nlog _{400000000000})$
代码（欣赏一下我的线段树码风）：
#include <iostream> #define int long long using namespace std; int n, x, y = 1, sum = 1, mod = 1000000007; int a[200010], f[200010], tree[8000010], ls[8000010], rs[8000010]; void add (int l, int r, int k) { tree[k] = (tree[k] + y) % mod; if (l == r) return; int mid = l + r >> 1; if (x <= mid) { if (!ls[k]) ls[k] = ++ sum; add (l, mid, ls[k]); } else { if (!rs[k]) rs[k] = ++ sum; add (mid + 1, r, rs[k]); } } int query (int l, int r, int k) { if (x <= l && y >= r) return tree[k]; int mid = l + r >> 1, res = 0; if (x <= mid) res += query (l, mid, ls[k]); if (y > mid) res = (res + query (mid + 1, r, rs[k]) ) % mod; return res; } signed main () { cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i]; a[i] += a[i - 1]; } f[0] = 1; for (int i = 0; i <= n; i ++) { if (i == 0) add (-200000000000, 200000000000, 1); else { x = -200000000000; y = a[i]; f[i] = query (-200000000000, 200000000000, 1); x = a[i]; y = f[i]; add (-200000000000, 200000000000, 1); } } cout << f[n]; return 0; }