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;
}