正文

奶牛抗议(代码片段)

wzx-rs-sthn  wzx-rs-sthn  2022-11-30  786

关键词：

题目

Description

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字
可正可负。约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之
和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必
须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。约翰想知道有多少种分组的方案，由于
答案可能很大，只要输出答案除以1000000009 的余数即可。

Input

第一行：单个整数N，1 ≤ N ≤ 100000
第二行到第N + 1 行：第i + 1 行有一个整数Ai，10^5 ≤ Ai ≤ 10^5

Output

单个整数：表示分组方案数模1000000009 的余数

Sample Input

Sample Output

Hint

说明
解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；
如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

思路：

如果不知道怎么求a前面小于a的个数

https://www.cnblogs.com/wzx-RS-STHN/p/13193271.html

暴力

首先我们先把这一题的dp思路想清；

dp[i]代表1-i的分组方案数；s[i]代表1-i的和；

如果j-i区间的和大于等于 0；dp[i]+=dp[j];

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read()

    ll a=0,ha=1; char c=getchar();
    while (c<‘0‘||c>‘9‘) if (c==‘-‘) ha=-1; c=getchar();
    while (c>=‘0‘&&c<=‘9‘) a=a*10+c-‘0‘; c=getchar();
    return a*ha;

const ll N=5*1e5;
const ll mod=1000000009;
ll s[N],ans,n,a[N],dp[N];
int main()

    n=read();
    for(ll i=1;i<=n;i++)
    
        a[i]=read();
        s[i]=s[i-1]+a[i];
    
    dp[0]=1;
    for(ll i=1;i<=n;i++)
    for(ll j=0;j<i;j++)
    
        if(s[i]>=s[j])//相当if(s[i]-s[j]>=0) 也就是看这一段和是否>=0 
            dp[i]=(dp[i]+dp[j])%mod;
    
    printf("%lld
",dp[n]);

正解

那么怎么优化呢？树状数组！！！

转移方程

    for(ll j=0;j<i;j++)
    
        if(s[i]>=s[j])//相当if(s[i]-s[j]>=0) 也就是看这一段和是否>=0 
            dp[i]=(dp[i]+dp[j])%mod;

很容易想到，这一段代码其实相当于求，s[i]前面比s[i]小的s[j]有多少个；dp[i]+=dp[j];

    ll x=findout(b[i]);//找出前面有多少数比b[i]小，并把那些位置上的方案数加上； 
        ans=x%mod;
        insert(b[i],ans);//将ans加入树状数组相当于暴力代码的记录dp[i]

b[i]是s[i]的离散化；

通过树状数组优化转移方程就ok了；

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read()

    ll a=0,ha=1; char c=getchar();
    while (c<‘0‘||c>‘9‘) if (c==‘-‘) ha=-1; c=getchar();
    while (c>=‘0‘&&c<=‘9‘) a=a*10+c-‘0‘; c=getchar();
    return a*ha;

const ll mod=1000000009;
ll n,m,sum[1000010];
ll b[1000010],a1[1000010],s[1000010];
struct oh

    ll v,num;
a[1000010];
inline ll lowbit(ll x)//树状数组基本操作 

    return x&(-x);

inline void insert(ll x,ll y)

    while(x<=n+1)
    
        sum[x]+=y;
        x+=lowbit(x);
    

inline ll findout(ll x)

    ll ans=0;
    while(x)
    
        ans+=sum[x];
        x-=lowbit(x);
    
    return ans;

inline ll cmp(oh a,oh b)

    if(a.v==b.v)
        return a.num<b.num;
    else
        return a.v<b.v;

int main()

    n=read();
    for(ll i=1;i<=n;i++)
    
        a1[i]=read();
        s[i+1]=s[i]+a1[i];//记录前缀和 
    
    s[1]=0;//边界相当于dp[0]=1 
    for(ll i=1;i<=n+1;i++)
    
        a[i].v=s[i];
        a[i].num=i;
    //离散化 
    sort(a+1,a+n+2,cmp);
    for(ll i=1;i<=n+1;i++)
        b[a[i].num]=i;
    //代码修改艰难痕迹 
//    cout<<endl;
//    for(ll i=1;i<=n+1;i++)
//        cout<<b[i]<<endl;
    insert(b[1],1);
    ll ans=0;
    for(ll i=2;i<=n+1;i++)
    
        ll x=findout(b[i]);//找出前面有多少数比b[i]小，并把那些位置上的方案数加上； 
        ans=x%mod;
        insert(b[i],ans);//将ans加入树状数组相当于暴力代码的记录dp[i] 
    
    printf("%lld
",ans);

//相当if(s[i]-s[j]>=0) 也就是看这一段和是否>=0

luogup2344奶牛抗议(树状数组优化dp)(代码片段)

...p; 传送门解题思路树状数组优化dp，f[i]表示前i个奶牛的分组的个数，那么很容易得出$f[i]=sumlimits_1leqjleqif[j-1]*(sum[i]gesum[j-1])$，但是这样的时间复杂度是$O(n^2)?$，所以考虑优化，发现必须满足$sum[i]gesum[j-1]?$才能进行转移... 查看详情

windows11升级惹众怒！微软无视用户抗议(代码片段)

????????关注后回复 “进群” ，拉你进程序员交流群????????作者丨汤泡饭来源丨扩展迷EXTFANS一个系统，若要升级，一般情况下大多数用户都不会产生过大的抵触情绪。毕竟升级的目的，都是为给用户带来更好的... 查看详情

奶牛排队(代码片段)

题意【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，... 查看详情

奶牛排序——rmq(代码片段)

【问题描述】奶牛在熊大妈的带领下排成了一条直队。显然，不同的奶牛身高不一定相同……现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛A是最矮的，最右边的B是最高的，且B高于A奶牛，且中间如果存在... 查看详情

奶牛会展(代码片段)

题目背景奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对N头奶牛进行了面试，确定了每头奶牛的智商和情商。题目描述贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，... 查看详情

java寻找公牛和奶牛(代码片段)

查看详情

p1578奶牛浴场(代码片段)

题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显... 查看详情

usaco2004moofest奶牛集会(代码片段)

题目问题描述约翰的n头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头奶牛的坐标是相... 查看详情

奶牛的聚会(代码片段)

农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为 w_iwi? ，他参加聚会所需行走的距离为 s_isi? ，那... 查看详情

奶牛家谱cowpedigrees(代码片段)

令人窒息的奶牛题题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)。这些二叉树有如下性质:每一个... 查看详情

[usaco]2004openmoofest奶牛集会(代码片段)

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

奶牛野炊(代码片段)

　　Thecowsarehavingapicnic!EachofFarmerJohn‘s K (1≤ K ≤100)cowsisgrazinginoneof N (1≤ N≤1,000)pastures,convenientlynumbered1...N.Thepasturesareconnectedby M 查看详情

洛谷1578：[wc2002]奶牛浴场——题解(代码片段)

...gu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置... 查看详情

[luogu2847]奶牛广播-金(代码片段)

...0)为了在他们之间传播信息,想要组织一个"哞哞广播"系统.奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫,所以每一头奶牛都必须有一个步话机.这些步话机都有一个限制传播半径,但是奶牛们可以间接地通过中... 查看详情

洛谷p1535游荡的奶牛(代码片段)

P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情

排序奶牛的编号(代码片段)

题目描述有N(1≤N≤1000)头奶牛，它们都被标上一个优先等级编号：1，2或3。用来表示它们喝水时的优先次序，编号为l的最优先，编号为2的其次，编号为3的最后。每天奶牛开始时排成一行，但总是很乱，需要你把它们重新排成... 查看详情

poj3263tallestcow(代码片段)

题面FJ的N头奶牛按序号1..N排成一排。每头奶牛都有正整数高度。你只被告知最高的奶牛的高度H（1≤H≤1,000,000）以及该奶牛的位置P.FJ已经列出了“牛17看到牛34”形式的R（0≤R≤10,000）行。这意味着奶牛34至少与奶牛17... 查看详情

观光奶牛(代码片段)

1#include<iostream>2#include<cstdio>3#include<queue>4usingnamespacestd;5typedefdoubledd;6constintmaxn=1007;7constintmaxm=5007;8intn,m,num;9ddl,r,mid;10ddd[maxn];11queue<int>q;1 查看详情