首页 > 2020.09.14-百度C++研发笔试复盘
头像
whoway
编辑于 2020-09-15 11:20
+ 关注

2020.09.14-百度C++研发笔试复盘

百度C++研发(9.14)笔试复盘

百度2021校招-C++/PHP研发工程师笔试卷(9月14日)

蹲一个第3题(牛牛排队)题解

图片说明 图片说明 图片说明

一、能吃几份

1)题目描述

1<=n<=1000(食物的个数)
1<=m<=1000(吃饱,需要的分量)
n个食物各自分别的分量,第i份
i的分量最多不超过10

问,最少吃多少个食物,就能感受到吃撑了。
样例:
5 10
1 2 9 4 5
输出
2
1 3
//表示,最少吃两份就好了,比如吃第1份和第3份,也就是1+9

考点:贪心
思路历程:一道“裸”的贪心题目
看到范围都很少,直接用数组模拟。
关于题意,那个“吃撑了”,先前,我想的是意思要>m才行吗
但是从样例看来,1+9=10,那么等于也是可以的,
也就是说>=(umm,果然,不能用我的语文来理解题目,幸好样例间接告诉了我)

Tips:这个题目中告诉我们,这题有Special Judge(特判)
也就是说,比如我们前的样例,其实输出下面也能AC掉题目,关于Special Judge(特判),好像没接触的人是会不知道那是啥...感谢没事干,刷的ICPC水题

2
3 5
//表示,最少吃两份就好了,比如吃第3份和第5份,也就是9+5>10也可以

正是因为有特判,所以,我们的贪心算法才好写嘛。不然,就要去猜测样例那样是咋想的(反而自己吓自己增加难度)

做法
从大到小排贪心,用pair保留原先的下标

2)代码AC

#include<bits/stdc++.h>
using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.first>b.first;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;++i)
        {
            int num,m;
            scanf("%d%d",&num,&m);
            int sum=0;
            vector<pair<int,int> > solve;

            for(int j=1;j<=num;++j)
            {
                int temp;
                scanf("%d",&temp);
                sum+=temp;

                pair<int,int> mp;
                mp.first=temp;
                mp.second=j;
                solve.push_back(mp);
            }

            if(sum<m)
            {
                printf("-1\n");
                continue;
            }
            else if(sum==m)
            {
                for(int j=1;j<=num;++j)
                {
                    printf("%d ",j);
                }
                continue;
            }

            sort(solve.begin(),solve.end(),cmp);


            vector<int> out;
            sum=0;
            int tag=0;
            for(int j=0;j<num;++j) 
            {
                sum+=solve[j].first;

                if(sum>=m)
                {
                    ++tag;
                    out.push_back(solve[j].second);
                    break;
                }
                else
                {
                    ++tag;
                    out.push_back(solve[j].second);
                }
            }

            printf("%d\n",tag);
            for(int ss=0;ss<out.size();++ss)
            {
                if(ss==out.size()-1)
                {
                    printf("%d\n",out[ss]);
                }
                else
                {
                    printf("%d ",out[ss]);
                }

            }
        }
    }

    return 0;
}

二、牛牛的奇偶序列

1)题目描述

求区间[L,R]内乘积为奇数或者偶数的个数

样例说明,
n表示区间长度,注意是从1-n编号
m表示查询次数
1表示查询奇数,L,R
2表示查询偶数,L,R

样例
4 2
1 2 3 4
1 1 3
2 1 3 
输出
3
4

考点
数学嘛?我用的组合数

我的思路

找到下面规律
第1类:

  • 奇*奇=奇

第2类:

  • 奇*偶=偶
  • 偶*奇=偶
  • 偶*偶=偶

抽象化:奇为1,偶为0
借助前缀和,用dp数组来保存,截止到i,包括i一共有多少个奇数
加快速度。
用cheng[maxn]数组,保存已经被模1e9+7后的阶乘,空间换时间,

感觉,不晓得哪里出问题了,现在看来是组合数超时了

后续想要改变超时,好像记得在Linux下有个小把戏:
在main函数之前运行,我都忘记是什么了,记得编译原理中我写过。
PS:后续查了一下,就算用下面的编译也好像不能改变评测的超时...

__attribute((constructer)) void beforeMain()
{
    yu();//在main函数之前准备阶乘打表
}

思路
复盘后找时间复杂度大的地方:
奇数和偶数求组合数的函数,循环太多。查询速度过慢,用二项式定理来解决的
(1+1)n=2n=++...
所以,++...=2n
这样查询时间就降到了O(1),此外为了更快,可以用左移运算,修改代码附下
此外用这种方式,还能省去对阶乘的打表优化耗费的空间。

2)代码

版本1(暴力求和组合数)

超时,版本2代码是优化版本1的查询,能显著降低时间复杂度

#include<bits/stdc++.h>
using namespace std;

const int maxn=200000+5;
const int down=1000000000+7;
int solve[maxn];
//截止到i,包括i一共有多少个奇数 
int dp[maxn]; 
int qus,L,R;

//打表加速 
long long  cheng[maxn];
void yu()
{
    cheng[1]=1;
    for(int jj=2;jj<maxn-3;++jj)
    {
        cheng[jj]=cheng[jj-1]*jj;
        cheng[jj]%=down;
    }
}


//求组合数 
long long combination(int n,int i)
{
    if(0==i)
    {
        return 1;
    }
    if(n==i)
    {
        return 1;
    } 

    long long up=cheng[n];
    long long num=cheng[i]*cheng[n-i];
    num%=down;
    up/=num;
    return up;
}



//奇数 
long long  ji()
{
    int sum=dp[R]-dp[L];
    if(dp[L])
    {
        ++sum;
    }

    long long rt=0;
    for(int i=0;i<sum;++i)
    {
        //Cn 0---(n-1) 
        rt+=combination(sum,i);
        rt%=down;
    }


    rt%=down;
    return rt;
}



//偶数 
long long  ou()
{
    long long rt=0;
    int num=R-L+1;

    for(int i=0;i<num;++i)
    {
        //Cn 0---(n-1) 
        rt+=combination(num,i);
        rt%=down;
    }

    rt-=ji();

    return rt;
} 



void solution()
{

    if(1==qus)
    {
        printf("%lld\n",ji());
    }
    else
    {
        printf("%lld\n",ou());    
    }
}


//处理前缀 
void dpsolve(int n)
{
    for(int i=1;i<=n;++i)
    {
        if(1==i)
        {
            continue;
        }

        if(1==dp[i])
        {
            dp[i]=dp[i-1]+1;
        }
        else
        {
            dp[i]=dp[i-1];
        }
    }

}



int main()
{
    int n,m;

    yu();
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&solve[i]);
            if(solve[i]&1) 
            {
                dp[i]=1;//表示奇数 
            }
        }

        //处理前缀 
        dpsolve(n);


        for(int i=0;i<m;++i)
        {
            scanf("%d%d%d",&qus,&L,&R);    
            solution();
        }
    }

    return 0;
}

版本2(用二项式求和组合数)

  • 10:47改为版本2的2.0,感谢牛油大佬Carits

查询时间复杂度降到O(1)

#include<bits/stdc++.h>
using namespace std;

const int maxn=200000+5;
const int down=1000000000+7;
int solve[maxn];

//截止到i,包括i一共有多少个奇数 
int dp[maxn]; 
int qus,L,R;


int Storage[10000+5]; 


void init()
{
    Storage[0]=1; 
    for(int i=1; i<10000+5; ++i)
    {
        Storage[i]=(Storage[i-1]<<1);
        Storage[i]%=down;
    }
}


//奇数 
long long  Odd()
{
    int sum=dp[R]-dp[L];
    if(dp[L])
    {
        ++sum;
    }
    long long rt=1;

    //二项式定理 
    rt=Storage[sum]-1;
    return rt;
}



//偶数 
long long  even()
{
    long long rt=1;
    int num=R-L+1;
    //二项式定理 
    rt=Storage[num]-1;

    rt-=Odd();
    return rt;
} 


void solution()
{

    if(1==qus)
    {
        printf("%lld\n",Odd());
    }
    else
    {
        printf("%lld\n",even());    
    }
}


//处理前缀 
void dpsolve(int n)
{
    for(int i=1;i<=n;++i)
    {
        if(1==i)
        {
            continue;
        }

        if(1==dp[i])
        {
            dp[i]=dp[i-1]+1;
        }
        else
        {
            dp[i]=dp[i-1];
        }
    }

}



int main()
{
    int n,m;
    init();

    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&solve[i]);
            if(solve[i]&1) 
            {
                dp[i]=1;//表示奇数 
            }
        }

        //处理前缀 
        dpsolve(n);

        for(int i=0;i<m;++i)
        {
            scanf("%d%d%d",&qus,&L,&R);    
            solution();
        }
    }

    return 0;
}

三、牛牛排队

1)题目描述

n个人,m个食堂,接下来输入m个食堂,中有多少个可以打饭的窗口
求最长排队长度期望啥的

题目都没大记清,只晓得,自己概率论忘了...不会,尴尬

考点:概率论,求期望

蹲一个第3题题解

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐