蚂蚁工程技术岗3.21笔试

投票
最后一题找不到很具体的规律,感觉时间不够,就直接交了
全部评论
第二题思路:第一个点为R,或W,只有两种情况,两次bfs确定次数
4 回复 分享
发布于 2023-03-21 20:44 北京
第二题是这样吗:#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 湖南
最后一题暴力只有20%。。。没时间写第二题😢
2 回复 分享
发布于 2023-03-21 20:43 北京
最后一题先暴力输出前几项,发现从奇数得到偶数,是直接 f(7)*7 = f(8), 但是偶数得到奇数没发现什么规律。。
1 回复 分享
发布于 2023-03-21 20:43 北京
同问最后一题
点赞 回复 分享
发布于 2023-03-22 08:52 江苏
第三题, 如果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 上海
第二题是树形dp题目,一次dfs就能出结果。要记录当前子树的节点数以及子树节点满足两两颜色不同需要的次数,然后就是定义状态转移方程出结果。
点赞 回复 分享
发布于 2023-03-21 21:00 江苏
蹲一个大佬讲讲第三题
点赞 回复 分享
发布于 2023-03-21 20:46 北京
为什么第二题dfs过不了
点赞 回复 分享
发布于 2023-03-21 20:44 北京
为什么第二题dp超时啊
点赞 回复 分享
发布于 2023-03-21 20:42 北京
有没大佬讲一下最后一题的规律
点赞 回复 分享
发布于 2023-03-21 20:36 北京

相关推荐

喵_coding:项目太烂了外卖+点评啊 而且寒假实习差不多到时候了 hc没多少了 要实在想要找那只能投投大厂试试了
点赞 评论 收藏
分享
2025-12-12 19:01
南京航空航天大学 C++
秋招没咋投,准备&nbsp;wxg&nbsp;转正之后摆烂了。结果不堪字节&nbsp;HR&nbsp;的骚扰还是面了一下字节。之前想去字节的时候怎么面都挂。现在想着随便面一下结果三面技术面都意外顺利还有加面。十月中旬字节发了意向,wxg&nbsp;转正结果无响应。十月底字节拉了保温群,wxg&nbsp;口头通过,系统显示考核中。十一月初和字节&nbsp;ld&nbsp;交流之后得知&nbsp;base&nbsp;居然能选海外,甚至能小&nbsp;wlb&nbsp;一下,wxg&nbsp;无响应无人联系。十一月中旬把字节&nbsp;base&nbsp;转到了海外,wxg&nbsp;流程灰了,一问超时忘处理了,过两天又变考核中了。十一月下旬字节换了海外&nbsp;HR&nbsp;对接,问了期望薪资,wxg&nbsp;考核终于显示通过,无&nbsp;HR&nbsp;保温,无其他保温。十一月底给字节报了个天价,想吓吓他们,同时告诉微信字节要开了,微信无响应。同样十一月底字节&nbsp;HR&nbsp;告诉我确实给不到那么高,但是能拿期权补上,问能不能接受。微信无响应。同样十一月底字节&nbsp;HR&nbsp;告知了具体方案,符合预期。&nbsp;微信无响应。十二月上旬催&nbsp;wxg&nbsp;不开我就盲拒了,wxg&nbsp;HR&nbsp;火急火燎的打电话问情况,问期望。我给了一个不算夸张的总包数字,因为今年市场在涨,过了三天还不联系我,我再催,约时间下午打电话,非得在我给出的数字上压下去几万,微信又不差这点,为什么不能满足我,让我没有拒绝的理由呢?一番纠结抗争,求稳还是追求挑战,最终选择接受迎接新的挑战,因为堂吉诃德永远不会停下脚步!回想起来,在&nbsp;wxg&nbsp;谈薪的阶段,我认为并没有给予我一定的重视,即使&nbsp;HR&nbsp;表示我在实习期间的表现和之前的面评都很靠前。也没有感觉到想要争取我,虽然我表示拒了&nbsp;offer&nbsp;之后要给我加面委定&nbsp;t6&nbsp;再涨,但我三个月没面试让我面面委那就是白给,还是算了。有缘再见了我亲爱的&nbsp;wxg,再见了曾经的梦中情厂,再见亲爱的&nbsp;mt,再见亲爱的朋友们。也再见,北京的一切。我想润了。秋招结束,卸载牛客,下一个三年,下一个五年,下一个十年后再来看看。
面试中的大熊猫爱吃薯...:我嫉妒得狗眼通红
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务