百度2021批秋招笔试题解

$总结：果然笔试还是很欢乐的...$

T1

题意描述略…题目一大堆其实就是在告诉你“这题就是结构体排序！！！”

结构体排序板子题

C++代码：

#pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1000005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std; inline ll read() { ll x=0,w=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();} while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();} return w==1?x:-x; } ll n,m,k; struct node{ll p,w,v;}p[maxn]; inline bool cmp(node a,node b) { if(a.v!=b.v) return a.v>b.v; if(a.p!=b.p) return a.p<b.p; return a.w<b.w; } int main() { n=read(); m=read(); k=read(); rep(i,1,n) p[i].p=read(),p[i].w=read(),p[i].v=read(); sort(p+1,p+n+1,cmp); ll n1=0,n2=0,cnt=0; for(int i=1;i<=n;i++) { if((n1+p[i].p<=k)&&(n2+p[i].w<=m)) { n1+=p[i].p; n2+=p[i].w; cnt++; } } cout<<cnt<<endl; return 0; }

顺便现场学了一波Java的结构体排序…Java好难啊啊啊.jpg

import java.util.*; class node implements Comparable <node> { int p,w,v; public node(int p ,int w,int v) { this.p=p; this.w=w; this.v=v; } public int compareTo(node a) { if(this.v-a.v != 0) return a.v-this.v; else if(this.p-a.p!=0) return this.v-a.v; return this.w-a.w; } } public class zbr01 { public static void main(String[] args) { Scanner S=new Scanner(System.in); int n=S.nextInt(),m=S.nextInt(),k=S.nextInt(); node []p=new node[1000005]; for(int i=0;i<n;i++) { int u=S.nextInt(),v=S.nextInt(),w=S.nextInt(); p[i]=new node(u,v,w); } Arrays.sort(p,0,n); int cnt=0,n1=0,n2=0; for(int i=0;i<n;i++) { if((n1+p[i].p<=k)&&(n2+p[i].w<=m)) { n1+=p[i].p; n2+=p[i].w; cnt++; } } System.out.println(cnt); } }

T2

题意描述：给出n*n的带权值的矩阵，一步只能走四相邻的格子，花费为abs(两格权值差)，问从(1,1)走到(n,n)的最小代价。 $n<=100$

一眼Dijkstra板子题，贴板子就过过过了（（

#pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1000005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; inline int read() { int x=0,w=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();} while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();} return w==1?x:-x; } int N,n,m,s,dis[maxn],a[105][105]; struct node{int v,w;}; vector <node> mp[maxn]; struct node2{int dis,to;}; inline bool operator < (node2 a,node2 b){return a.dis>b.dis;} priority_queue <node2> que; bool vis[maxn]; const int kx[4]={0,0,1,-1}; const int ky[4]={1,-1,0,0}; inline int G(int a,int b){return N*(a-1)+b;} inline int A(int u,int v,int w) { mp[u].pb({v,w}); mp[v].pb({u,w}); } int main() { N=read(); rep(i,1,N) rep(j,1,N) a[i][j]=read(); s=G(1,1); n=N*N; rep(i,1,N) rep(j,1,N) { rep(k,0,3) { int tx=i+kx[k],ty=j+ky[k]; if(tx<=0||tx>N||ty<=0||ty>N) continue; A(G(i,j),G(tx,ty),abs(a[i][j]-a[tx][ty])); } } for(int i=1;i<=n;i++) dis[i]=inf; dis[s]=0; que.push((node2){0,s}); while(!que.empty()) { node2 u=que.top(); que.pop(); if(vis[u.to]) continue; vis[u.to]=1; int uu=u.to; for(int i=0;i<mp[uu].size();i++) { node v=mp[uu][i]; if(vis[v.v]) continue; if(dis[uu]+v.w<dis[v.v]) { dis[v.v]=dis[uu]+v.w; que.push((node2){dis[v.v],v.v}); } } } printf("%d\n",dis[G(N,N)]); return 0; }

T3？？？

题意描述：每个格子权值为自己权值+四相邻格子权值平均值；

（是每场笔试必有的签到题… Java代码如下：（顺便现学了一波Java的四舍五入…）

import java.util.*; public class Main { static int [][]a=new int[1005][1005]; static int []kx={0,0,1,-1}; static int []ky={1,-1,0,0}; public static void main(String[] args) { Scanner S=new Scanner(System.in); int n=S.nextInt(),m=S.nextInt(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=S.nextInt(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int cnt=0,tmp=0; for(int k=0;k<=3;k++) { int tx=i+kx[k],ty=j+ky[k]; if(tx<=0||tx>n||ty<=0||ty>m) continue; cnt++; tmp+=a[tx][ty]; } double p=(tmp+a[i][j])/(cnt+1.0)+0.5; a[i][j]=(int)p; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) System.out.print(a[i][j]+" "); System.out.println(); } } }

T4？？？

题意描述：n级楼梯，每次最多走m步，最少走1步，且每一步不能与上两步的步数相同，问共有多少种走楼梯的方法。 $n<=1e5,m<=7$ 样例：$n=7,m=2,ans=2$ $([1,2,3,1],[1,3,2,1])$

由于某些不可描述的原因，看到这题已经快结束了hhh。 不过这显然是个div2C难度的dp… 设状态$dp[i][j][k]$为当前在i级楼梯，前一步为k，前两步为j的方案数，然后胡乱转移即可。

$(弱菜博主，在线口胡.jpg)$ 代码当然咕咕咕。