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个食堂，中有多少个可以打饭的窗口 求最长排队长度期望啥的
题目都没大记清，只晓得，自己概率论忘了...不会，尴尬
考点：概率论，求期望