百度2021校招C++/PHP研发工程师笔试卷（9月3日）编程题解题报告
2020.9.3
序言
单选题有15道，不定项选择题有5道(3份)，选择题涉及的知识面很广，包括计网，Linux命令(df/du)， AVL，二叉树，操作系统(生产者-消费者问题)，数据结构，C++虚函数，java代码…编程题有3道，每道20份
第一题，铺地毯
题目描述：
T组数据，T<=1000, 在长度为L的走廊铺地毯，铺n块，每块的范围是[Left_i,Right_i]), n<=1000, 问最后每个位置的地板上有多少张地毯铺在上面。
思路：差分。[left,right]铺地板，那么差分数组a[left]++,a[right+1]–
#include <bits/stdc++.h>
using namespace std
;
const int N
= 2000;
int a
[N
],b
[N
];
int main(void) {
int T
,L
,n
,x
,y
;
cin
>>T
;
while(T
--) {
memset(a
,0,sizeof(a
));
memset(b
,0,sizeof(b
));
scanf("%d%d",&L
,&n
);
while(n
--) {
scanf("%d%d",&x
,&y
);
a
[x
]+=1;
a
[y
+1]-=1;
}
for(int i
=1;i
<=L
;++i
) {
b
[i
] = b
[i
-1]+a
[i
];
}
for(int i
=1;i
<L
;++i
)
printf("%d ",b
[i
]);
printf("%d\n",b
[L
]);
}
return 0;
}
第二题：分配角色
T组输入，T<=100， n个人，m个角色。每个人分配一个角色，每个人的戏份的期望值为ai, 每个角色的戏份为bi。给每个人分配的角色的戏份必须不小于此人的期望值。否则无法分配。现在要求满足愿望的人数最大话，输出每个人分配的角色，如果没分配，输出-1
分析：贪心，把人按照戏份期望升序排列，角色用平衡二叉树(STL::set)维护，从头开始，每次分配能满足期望最小的角色(set::lower_bound)，然后从书中删去这个角色。
#include <bits/stdc++.h>
using namespace std
;
const int N
= 1000+100;
struct Node
{
int id
,want
,op
;
bool operator < (const Node
& rhs
)const{
return want
==rhs
.want
?id
<rhs
.id
:want
< rhs
.want
;
}
}node
[N
];
bool cmp(const Node
& a
,const Node
& b
) {
return a
.id
< b
.id
;
}
int main(void) {
int T
,m
,n
;
cin
>>T
;
while(T
--) {
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;++i
) {
scanf("%d",&node
[i
].want
);
node
[i
].id
= i
;
node
[i
].op
= -1;
}
set
<pair
<int,int> > st
;
pair
<int,int> pr
;
for(int i
=1;i
<=m
;++i
) {
pr
.second
= i
;
scanf("%d",&pr
.first
);
st
.insert(pr
);
}
sort(node
+1,node
+1+n
);
for(int i
=1;i
<=n
;++i
) {
pr
.first
= node
[i
].want
;
pr
.second
= 0;
auto it
= st
.lower_bound(pr
);
if(it
==st
.end()) break;
node
[i
].op
= it
->second
;
st
.erase(it
);
}
sort(node
+1,node
+1+n
,cmp
);
for(int i
=1;i
<n
;++i
) {
printf("%d ",node
[i
].op
);
}
printf("%d\n",node
[n
].op
);
}
return 0;
}
第三题：走台阶
n步路，每次最少走1步，最多走m步。(n<=100,000,2<=m<=7), 每一步和前面的两部的步长都不能相同。问有多少种方案。
分析：肯定可以dfs(), 可以过40%的数据。我们DP。dp[i][j][k]代表当前在位置i，前一次走了k步，再前一次走了j步。(k!=j) , 那么dp[i][j][k] = (dp[i][j][k]+dp[i-k][fa][j])%mod;(fa!=j&&j!=k&&fa!=k), 我们可以强制令第一次走了0步，这样就使得至少走两次。
#include <bits/stdc++.h>
using namespace std
;
const int N
= 1e5+10;
const int mod
= 1e9+7;
typedef long long LL
;
LL dp
[N
][8][8];
int record
[N
];
int cnt
;
void dfs(int x
,int n
,int m
,int presum
) {
if(presum
>n
) return;
if(presum
==n
) {
++cnt
;
return;
}
int pre
=-1,fa
=-2;
if(x
-1>=0) pre
= record
[x
-1];
if(x
-2>=0) fa
= record
[x
-2];
for(int i
=1;i
<=m
;++i
) {
if(i
==pre
||i
==fa
) continue;
record
[x
] = i
;
dfs(x
+1,n
,m
,presum
+i
);
}
}
int main(void) {
int n
,m
;
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=m
;++i
) {
dp
[i
][0][i
] = 1;
}
for(int i
=1;i
<=n
;++i
) {
for(int j
=1;j
<=m
;++j
) {
for(int k
=1;k
<=m
;++k
) {
if(k
==j
) continue;
if(i
<j
+k
) continue;
for(int fa
=0;fa
<=m
;++fa
) {
if(fa
==j
||fa
==k
) continue;
dp
[i
][j
][k
] = (dp
[i
][j
][k
]+dp
[i
-k
][fa
][j
])%mod
;
}
}
}
}
LL ans
= 0;
for(int i
=0;i
<=m
;++i
) {
for(int j
=1;j
<=m
;++j
){
if(i
!=j
) ans
= (ans
+dp
[n
][i
][j
])%mod
;
}
}
printf("%lld\n",ans
);
return 0;
}
2020.9.3 21:18
