题解 P2344 【奶牛抗议】

· · 题解

欢迎踩踩我的博客

{\color{cyan}{>>Question}}

二维偏序dp

方程很简单

令f[i]表示到i的方案数

有

f[i] = \sum f[j],\sum_{k = j+1}^i a[k] \geq 0

写成前缀和的形式便是

f[i] = \sum f[j],sum[i]-sum[j]\geq 0

暴力是O(n^2)(话说居然有70pts),考虑优化

观察可知i由j转移来有两个条件

1.$ $j < i 2.$ $sum[j] <= sum[i]

那可把i看成(i,sum[i])的点,就成了一个二维偏序问题

不了解二维偏序的可以康康这篇博客(其实逆序对就是最经典的二维偏序(动态逆序对就是三维偏序) )

可以离散化,也可以不离散化

离散化就离散sum[i],i天然有序

不离散化就以sum[i]为第一关键字,i为第二关键字排序

外面都套个树状数组即可

但我太菜了,第一次处理树状数组0基准的情况(f[0] = 1),犯了很多错才调出来,具体看代码吧

离散化版

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
using namespace std; 

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) x = -x , putchar('-');
    if(x > 9) out(x/10);
    putchar(x%10 + 48);
}
//-------------------------------------------------------

const int N = 1e5+7,mod = 1e9+9;
int n;
ll b[N],ans;

struct node {
    int pos;ll sum;
}p[N];

struct map {
    int pos;ll sum;
    bool operator < (const map &x) const {
        return sum == x.sum ? pos < x.pos : sum < x.sum;//sum < x.sum;
    }
}a[N];

void A(int pos,ll k) {
    for(int i = pos;i <= n;i += i&-i) b[i] = (b[i]+k)%mod;
}

ll Q(int pos) {
    ll res = 0;
    for(int i = pos;i;i -= i&-i) res = (res + b[i])%mod;
    return res;
}

int main() {
    //freopen("0.in","r",stdin);
    //freopen("my.out","w",stdout);
    int i; ll x;
    in(n);
    a[0].pos = a[0].sum = 0;
    for(i = 1;i <= n; ++i) p[i].pos = i,in(x),p[i].sum = p[i-1].sum + x,a[i].pos = i,a[i].sum = p[i].sum;
    sort(a,a+n+1);//debug a[0]
    p[a[0].pos].sum = 1; int _id = 1;
    for(i = 1;i <= n; ++i) {
        if(a[i].sum != a[i-1].sum) ++_id;//debug i-1越界 
        p[a[i].pos].sum = _id;
    }
    //for(i = 1;i <= n; ++i) cout << p[i].sum << endl;
    A(p[0].sum,1);
    for(i = 1;i <= n; ++i) {
        ans = Q(p[i].sum);
        A(p[i].sum,ans);
        if(i == n) out(ans);
        //out(ans),putchar('\n');
    }
    //out(ans);
    return 0;
}

不离散化版

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
using namespace std; 

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) x = -x , putchar('-');
    if(x > 9) out(x/10);
    putchar(x%10 + 48);
}
//-------------------------------------------------------

const int N = 1e5+7,mod = 1e9+9;
int n;
ll b[N],ans;
ll f[N];

struct node {
    int pos;ll sum;
    bool operator < (const node &x) const {
        return sum == x.sum ? pos < x.pos : sum < x.sum;
    }
}p[N];

void A(int pos,ll k) {
    for(int i = pos;i <= n+1;i += i&-i) b[i] = (b[i]+k)%mod;//debug n+1 -> n
}

ll Q(int pos) {
    ll res = 0;
    for(int i = pos;i;i -= i&-i) res = (res + b[i])%mod;
    return res;
}

int main() {
    //freopen("0.in","r",stdin);
    int i; ll x;
    in(n);
    p[0].pos = 1,p[0].sum = 0;
    for(i = 1;i <= n; ++i) p[i].pos = i+1,in(x),p[i].sum = p[i-1].sum + x;
    sort(p,p+n+1);
    for(i = 0;i <= n; ++i) {
        if(p[i].pos == 1) A(p[i].pos,1);
        f[p[i].pos-1] = Q(p[i].pos);
        ll x = f[p[i].pos-1];
        //if(p[i].pos == 1) A(p[i].pos,1);//debug//debug 
        if(p[i].pos == 1) continue;
        A(p[i].pos,x);
    }
    out(f[n]);
    //for(i = 1;i <= n; ++i) cout << f[i] << endl;
    return 0;
}

谢谢各位看官老爷支持,如果觉得还看得下去的话,不妨点个赞, 投个币（づ￣3￣）づ╭❤～

另外有意愿的大佬们可以去切一下这道题,一样的思路