第一题
【题意】 给出<a,b>，可以理解为a的爸爸是b，现在你要依次输出每个爸爸的所有儿子，儿子之间按照字典序排序
【思路】 思路不难，用map将爸爸的名字映射成数字，然后建一个二维vector，儿子push_back到对应爸爸后面，然后排序输出即可。
【坑点】竟然有重复的，最后三分钟才发现，有点坑啊!!!也就是a的爸爸是b这句话说了多遍，那么vector中的元素会有重复，需要去重，当然，直接用set自动去重就行了
【代码】
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define mst(a,b) memset((a),(b),sizeof(a))#define rush() int T;scanf("%d",&T);while(T--)const int maxn=1005;const int INF=0x3f3f3f3f;const ll mod=998244353;int n;int a[maxn];string s,tmp;map<string,int>mp;vector<string>ans[maxn];vector<string>vec;set<string>S[maxn];int main(){cin>>n;int cnt=0;for(int i=1;i<=n;i++){cin>>s>>tmp;if(mp[tmp]==0) mp[tmp]=++cnt,vec.push_back(tmp);S[mp[tmp]].insert(s);}for(int i=0;i<cnt;i++){cout<<vec[i];//sort(ans[i+1].begin(),ans[i+1].end());//for(int j=0;j<ans[i+1].size();j++) cout<<" "<<ans[i+1][j];set<string>::iterator it;for(it=S[i+1].begin();it!=S[i+1].end();it++) cout<<" "<<*it;puts("");}}
第二题
【思路】因为要使加油次数最少，显然要用贪心，每次油不足以到达当前的加油站时，说明前面必须要多加一次油，要加的话肯定是加前面加油站中油量最大的那个，所以用优先队列维护一下，每次弹出最大值即可
【代码】
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define mst(a,b) memset((a),(b),sizeof(a))#define rush() int T;scanf("%d",&T);while(T--)const int maxn=1005;const int INF=0x3f3f3f3f;const ll mod=998244353;int n,d,w;int a[maxn];string s;int dis[maxn];int main(){scanf("%d%d",&d,&w);getchar();getline(cin,s);int len=s.size();int n=1,cnt=0;for(int i=0;i<len;i++){if(s[i]>='0'&&s[i]<='9') cnt=cnt*10+s[i]-'0';else{dis[n++]=cnt;cnt=0;}}dis[n++]=cnt;//printf("%d\n",n);dis[0]=0;dis[n+1]=d;for(int i=1;i<=n;i++) scanf("%d",&a[i]);int ans=0;priority_queue<int,vector<int>,less<int> >q;for(int i=1;i<=n+1;i++){if(w>=dis[i]) q.push(a[i]);else{while(q.size()){int x=q.top();w+=x;ans++;q.pop();if(w>=dis[i]){q.push(a[i]);break;}}}}if(w>=d) printf("%d\n",ans);else puts("-1");}
第三题
【思路】经典的迷宫问题，只多了一个传送门，随便用什么东西把两个传送门之间连接起来即可，再用bfs广搜，每次到传送门的时候一个方案是向四周走，还有就是走到传送门的另一侧
但是不知道为什么一直超时87.5，检查了很久没有检查出来QAQ
【PS】有dalao提醒了，应该就是因为我走通道的时候没有vis判断…
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define mst(a,b) memset((a),(b),sizeof(a))#define rush() int T;scanf("%d",&T);while(T--)const int maxn=205;const int INF=0x3f3f3f3f;const ll mod=998244353;int n,m;int mp[maxn][maxn];int vis[maxn][maxn];const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};vector<pair<int,int> >vec[maxn*maxn];map<int,int>kk;struct node{int x,y,step;}now,nex;int bfs(int sx,int sy){vis[sx][sy]=1;queue<node>q;q.push({sx,sy,0});//printf("%d\n",mp[0][0]);while(q.size()){now=q.front();q.pop();//printf("%d %d %d %d\n",now.x,now.y,now.step,mp[now.x][now.y]);if(mp[now.x][now.y]==-3) return now.step;if(mp[now.x][now.y]>0){//puts("**");int x=kk[mp[now.x][now.y]];if(vec[x][0].first==now.x&&vec[x][0].second==now.y){nex.x=vec[x][1].first;nex.y=vec[x][1].second;nex.step=now.step+1;q.push(nex);vis[nex.x][nex.y]=1;}else{nex.x=vec[x][0].first;nex.y=vec[x][0].second;nex.step=now.step+1;q.push(nex);vis[nex.x][nex.y]=1;}//printf("@@%d %d\n",nex.x,nex.y);}for(int i=0;i<4;i++){nex.x=now.x+dir[i][0];nex.y=now.y+dir[i][1];nex.step=now.step+1;if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&mp[nex.x][nex.y]!=-1&&vis[nex.x][nex.y]==0){q.push(nex);vis[nex.x][nex.y]=1;}}}return -1;}int main(){scanf("%d%d",&m,&n);int sx,sy;int cnt=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&mp[i][j]);vis[i][j]=0;if(mp[i][j]==-2) sx=i,sy=j;if(mp[i][j]>0){if(kk[mp[i][j]]==0) kk[mp[i][j]]=cnt++;vec[kk[mp[i][j]]].push_back(make_pair(i,j));}}}//printf("%d %d\n",sx,sy);printf("%d\n",bfs(sx,sy));}
第四题
【思路】题目模型就是有依赖的树形dp(背包)，直接利用题目所给关系两个点之间连边，但是有可能无法构成一棵树(若干颗分散的树)，所以引入虚节点作为树根，将它和其他分散的树根连接起来(当依赖点为0的时候，用0连向这个点就好)构成一棵树就可以树形dp了
用dp[i][j]表示以i为根，用了j个节点的最大值，然后自下向上更新
最终答案就是dp[0][m+1]
【代码】
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define mst(a,b) memset((a),(b),sizeof(a))#define rush() int T;scanf("%d",&T);while(T--)const int maxn=205;const int INF=0x3f3f3f3f;const ll mod=998244353;int n,m;int val[maxn];int dp[maxn][maxn];vector<int>vec[maxn];void dfs(int u){for(int i=0;i<vec[u].size();i++){int v=vec[u][i];dfs(v);for(int j=m-1;j>=0;j--)for(int k=0;k<=j;k++){dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]); //这里是还没算当前树根u，所以总和是m-1}}for(int i=m;i>=1;i--) dp[u][i]=dp[u][i-1]+val[u];}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d%d",&x,&val[i]);vec[x].push_back(i);}m++;mst(dp,0);dfs(0);printf("%d\n",dp[0][m]);}
如果觉得《字节跳动校园招聘算法方向第一场考试题解》对你有帮助，请点赞、收藏，并留下你的观点哦！
