校招全国统一模拟笔试（五月场）编程题参考代码
模拟笔试试卷地址：https://www.nowcoder.com/test/10714908/summary
独立的牛牛
分析
首先计算能保证的房屋能租多少天,如果有剩余再考虑购买水果。
时间复杂度
O(1)
参考代码
#include <bits/stdc++.h>
using namespace std;
int x, f, d, p;
int solve(int x, int f, int d, int p) {
int tmp1 = d / x;
if(tmp1 <= f) return tmp1;
d -= f * x;
return f + d / (x + p);
}
int main() {
cin >> x >> f >> d >> p;
cout << solve(x, f, d, p) << endl;
return 0;
}
牛牛炒股票
分析
题目可以被抽象为一个多重背包：我们把借来的钱看成容量，买入价看成物品的重量，卖出价看成物品的价值。答案就等于总价值和总重量的差值。
注意处理所有股票都处于跌价状态的情况。
时间复杂度
O(N * M)
参考代码
#include <bits/stdc++.h>
using namespace std;
int dp[1005];
int c[1005][2];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) dp[i] = i;
for(int i = 1; i <= n; i++) {
scanf("%d%d", &c[i][0], &c[i][1]);
for(int j = c[i][0]; j <= m; j++)
dp[j] = max(dp[j], dp[j-c[i][0]] + c[i][1]);
}
printf("%d\n", dp[m] - m);
return 0;
}
牛牛吃雪糕
分析
我们要按照一定的策略来安排这些雪糕来让能撑过的天数最大。
首先我们考虑只吃一盒两份或者一盒三份的雪糕，那么每天我们吃3盒每盒两份的雪糕或者2盒每盒三份的雪糕。接下来用一盒一份的雪糕来填补空隙。空隙从小到大依次是：1盒两份+1盒三份的组合缺1盒一份，2盒两份的组合缺2盒一份，1盒三份的组合缺3盒一份，1盒两份的组合缺4盒一份。按照这个顺序依次填补存在的空隙，剩下来的每盒一份的雪糕，每6盒撑过一天。最后答案取决于能撑过的天数和高温天数的大小比较。
时间复杂度
O(T)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, n, a, b, c;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d%d", &n, &a, &b, &c);
n -= c / 2;
c = c % 2;
n -= b / 3;
b = b % 3;
if(a >= 1 && b >= 1 && c == 1) {
a--;
b--;
c--;
n--;
}
if(b == 2 && a >= 2) {
b = 0;
a -= 2;
n--;
}
if(c == 1 && a >= 3) {
c = 0;
a -= 3;
n--;
}
if(b == 1 && a >= 4) {
c = 0;
a -= 4;
n--;
}
n -= a / 6;
a = a % 6;
if(n > 0)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
牛牛打响指
分析
按照题目描述的那样去模拟就可以得到答案。唯一的问题是N太大了无法表示，所以我们把数字分割成很多位来处理，需要采用高精度加法和高精度除以2两种操作。
注意处理N=999这种过程中会超出N长度的情况。注意处理N=1的情况。
时间复杂度
O(logN)
参考代码
#include <bits/stdc++.h>
using namespace std;
char s[105];
int main() {
int l, ans = 0, tops = 1, now;
scanf("%s", s + 1);
l = strlen(s + 1);
for(int i = 1; i <= l; i++) s[i] -= '0';
while(tops < l || s[tops] != 1) {
ans++;
if(s[l] % 2) {
now = l;
s[now]++;
while(s[now] == 10) {
s[now - 1]++;
s[now] = 0;
now--;
if(now < tops) tops = now;
}
} else {
for(int i = tops; i <= l; i++) {
if(s[i] % 2)
s[i + 1] += 10;
s[i] = s[i] / 2;
if(i == tops && s[i] == 0)
tops++;
}
}
}
printf("%d\n", ans);
return 0;
}
牛牛取快递
分析
实际上题目要求我们分别求出从S到T和从T到S的最短路再把他们加起来。所以我们只要分别以S和T为起点跑单源最短路，再把两次的终点的坐标加起来就可以了。
注意图是有向图。
时间复杂度
O(M * logM)
参考代码
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int dis,to;
bool friend operator <(Edge x1,Edge x2)
{
return x1.dis>x2.dis;
}
}temp,now;
vector <Edge> vec[10005];
bool life[10005];
int dis[10005],n;
priority_queue <Edge> q;
void init()
{
for(int i=1;i<=n;i++)
dis[i]=100000000;
memset(life,0,sizeof(life));
while(!q.empty())
q.pop();
}
int dij(int s,int t)
{
init();
temp.to=s;
temp.dis=0;
q.push(temp);
dis[s]=0;
while(!q.empty())
{
now=q.top();
q.pop();
if(!life[now.to])
{
life[now.to]=1;
for(int i=0;i<vec[now.to].size();i++)
{
if(!life[vec[now.to][i].to] && dis[now.to]+vec[now.to][i].dis<dis[vec[now.to][i].to])
{
dis[vec[now.to][i].to]=dis[now.to]+vec[now.to][i].dis;
temp.to=vec[now.to][i].to;
temp.dis=dis[vec[now.to][i].to];
q.push(temp);
}
}
}
}
return dis[t];
}
int main()
{
int m,s,t,u,v,d;
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
scanf("%d%d%d",&u,&v,&d);
temp.dis=d;
temp.to=v;
vec[u].push_back(temp);
}
printf("%d\n",dij(s,t)+dij(t,s));
return 0;
}
https://www.nowcoder.com/test/10714908/summary
全国统一模拟笔试产品试卷五月场：
https://www.nowcoder.com/test/10714983/summary
全国统一模拟笔试运营试卷五月场：
https://www.nowcoder.com/test/10714961/summary
#笔试题目##校招#
