蚂蚁工程技术岗3.21笔试

投票
最后一题找不到很具体的规律,感觉时间不够,就直接交了
全部评论
第二题思路:第一个点为R,或W,只有两种情况,两次bfs确定次数
4 回复 分享
发布于 2023-03-21 20:44 北京
最后一题暴力只有20%。。。没时间写第二题😢
2 回复 分享
发布于 2023-03-21 20:43 北京
第二题是这样吗:#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; const int MAXN=1e5 + 5; vector<int>edges[MAXN]; string color; int dp[MAXN][2]; int vis[MAXN]; void add(int u,int v){ edges[u].push_back(v); edges[v].push_back(u); } void dfs(int u){ dp[u][0]=0; dp[u][1]=1; vis[u]=1; for(auto& v:edges[u]){ if(vis[v]==1)continue; vis[v]=1; dfs(v); vis[v]=0; if(color[v] == color[u]){ dp[u][0]+=min(dp[v][0]+1,dp[v][1]); dp[u][1]+=min(dp[v][1],dp[v][0])+1; }else { dp[u][0]+=min(dp[v][0],dp[v][1]+1); dp[u][1]+=min(dp[v][1],dp[v][0]+1); } } } int main(){ int n;cin>>n; cin>>color; for(int i=1;i<n;i++){ int a,b;cin>>a>>b; add(a-1,b-1); } dfs(0); cout<<min(dp[0][0],dp[0][1])<<endl; return 0; }
2 回复 分享
发布于 2023-03-21 21:07 湖南
最后一题先暴力输出前几项,发现从奇数得到偶数,是直接 f(7)*7 = f(8), 但是偶数得到奇数没发现什么规律。。
1 回复 分享
发布于 2023-03-21 20:43 北京
有没大佬讲一下最后一题的规律
点赞 回复 分享
发布于 2023-03-21 20:36 北京
为什么第二题dp超时啊
点赞 回复 分享
发布于 2023-03-21 20:42 北京
为什么第二题dfs过不了
点赞 回复 分享
发布于 2023-03-21 20:44 北京
蹲一个大佬讲讲第三题
点赞 回复 分享
发布于 2023-03-21 20:46 北京
第二题是树形dp题目,一次dfs就能出结果。要记录当前子树的节点数以及子树节点满足两两颜色不同需要的次数,然后就是定义状态转移方程出结果。
点赞 回复 分享
发布于 2023-03-21 21:00 江苏
第三题, 如果n是偶数, dp[n]=(n-1)*dp[n-1); 如果n是奇数, dp[n] = (n-1)!*(n-1) + (n-1)*dp[n-1)?
点赞 回复 分享
发布于 2023-03-21 21:08 上海
同问最后一题
点赞 回复 分享
发布于 2023-03-22 08:52 江苏

相关推荐

11-30 21:28
已编辑
南京市金陵中学 C++
最后以华为13级这个并不那么满意的offer结束支离破碎的秋招。bg:本硕双9电子信息类,非计算机,论文只有一篇ei会议。秋招目标:私企(问就是亲眼所见国企关停)转码前:研一时虽然大部分师兄师姐在转码,但是各种渠道渲染我们的专业很强,当时的想法是不转码肯定能找到满意的私企,然后拿本科毕设投了个ei会议,并开始自己找课题研究(导师放养)。研一下找到方向,研二上在仿真和写论文的时候开始意识到形势不好,越来越多的学长学姐申请华为的对口职位流程挂或只有个别勉强拿到offer,在萌生转码的念头时论文写到一半,于是决定论文写完再转码,觉得论文对找工作有用(现在来看对找开发的工作作用聊胜于无)。论文写完已经是12月中旬,一次次找导师改收到的是一次次拖延,直到3月份一个字没改让我投顶刊我才意识到这一年半的努力在秋招时不可能再转化为成果了。一个408只学过计算机网络,语言只学过c++且期末也只是刚及格的牛马从12月底才开始了转码。转码:算法卷院校卷顶刊没戏,只可能转开发,由于很多学长学姐都转码拿到华为的offer,难度不高,所以我最开始的目标是通过c++技术栈拿下华为并尝试互联网后端。零基础一切都要现学,所以就先从数据结构、操作系统、算法题这些开发类必备的知识学起,寒假开始刷力扣,当时根本不算是刷题,全是在看题解,印象很深刻的是第一题两数之和折磨了我一下午。三月刷力扣+背408八股,到三月底听计算机的同学说暑期实习后端卷麻了,相反前端今年相对简单,经过几天的考虑,最终决定两线作战:前端和c++,此时认为华为能稳稳作为保底。四月9106匆忙学了html+css+js,五月学了vue就去投实习了,b站腾讯阿里国际美团滴滴给了面试,但只有美团到了终面,结果还因为过于紧张以及没经验说错了话,与offer失之交臂。五月剩下的时间为华为准备了一个c++开源项目,六七月学react并准备了一个前端项目。本来的梦想是秋招签阿里等华为,然而噩梦就要开始了。秋招:先说结论吧,眼高手低,互联网一个都没拿到,老本行拿到某雷达所,前端拿到体面厂和性价比厂,c++拿到某学历厂、华子外包、迪子和两个通信大厂,两个前端base一个杭州一个南京,总包都不到25,c++的几个里华子外包和迪子base深圳,另外三个base上海且薪资降序。八月九月上旬集中投递前端岗位,每天都在笔试测评,但给面试的只有美团京东淘天,美团终面面试官百般刁难,甚至拷打前端发展历史这种问题,寄了之后美团再没捞我,必然是脏了面评,京东一面hr面,拷打我本科成绩和无竞赛奖项,直接寄,淘天二面挂。然后九月中旬发现互联网希望渺茫,慢一步投递了c++相关岗位,华为线下面试一天速通池子后拒了研究所的oc,抱着华为稳了的想法准备结束秋招,结果几天后问面试情况被告知面评非3A。这最后一根稻草压垮了996半年的我,整日的emo和严重的焦虑导致我不停的胡思乱想,加上那几天我的室友和我同一时间投递的三家都有进展甚至oc而我没有任何进展,我在发呆焦虑迷茫中度过了那一周。而一周之后算是有些好消息,开始有offer了,至少不至于毕业即失业。为了给华为留一线生机拒了最早来的一家(听说华为不等这家毁约),体面厂在接受意向后,华为在经过一系列沟通后告知可以给offer,因此未签三方,性价比厂oc后紧接着收到华为通知报批通过,接着就是现在华为第一批开奖了。总结:看着现在同学没有杂七杂八想法单一技术栈allin华为oc14甚至15级很不甘心,回想起来我可能在每个节点都做错了选择:在研一时不做充分调研就对不转码找工作过于自信,不该在只有几个月时间准备的情况下开辟第二战场转前端,不该在找不到暑期实习后还继续梭哈前端,不该在互联网全线溃败时面试华为导致面试官觉得我不够自信……太多的错误导致了这个结局。看好华为的平台以及去上海的意愿让我最后做出了接受13级的选择。回顾这接近19年的学习阶段,我总是在尝试向上卷:中考和全市人竞争重点高中,高考和全省人竞争985,考研更是千军万马过独木桥。我卷进了重点高中,但是我的努力收获的是高三一次比一次差的成绩,高考我考了一个高三从未考到过的成绩,曾经我认为这才是我的真实水平,但是现在我觉得我错了,本科时我卷不过同学,花费几倍于别人的努力却只能勉强达到差不多的水平;考研初试我靠着接近一年的995才收获高分,而准备同样时间的复试我就远远落后于别人;花费同样的时间在科研上也不能获得与别人差不多的成果。曾经我也自命不凡,但我现在意识到自己就是个平凡到不能再平凡的人,我的努力在命运面前仿佛沧海一粟。借用自己很喜欢的一首歌的歌词来结尾吧:“难以释怀的&nbsp;让时间冲淡&nbsp;至少我还在期盼。”希望工作顺利,希望生活如意。
牛客220859485号:唉,加油吧老哥,硕士拿13已经很吃亏了。感觉老哥是选择做错了,卷一卷java去互联网后端没问题的,华子也不是只收c++。all in C++是把路走窄了。
点赞 评论 收藏
分享
评论
点赞
4
分享
牛客网
牛客企业服务