蚂蚁工程技术岗3.21笔试
投票
最后一题找不到很具体的规律,感觉时间不够,就直接交了
全部评论
第二题思路:第一个点为R,或W,只有两种情况,两次bfs确定次数
最后一题暴力只有20%。。。没时间写第二题😢
第二题是这样吗:#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;
}
最后一题先暴力输出前几项,发现从奇数得到偶数,是直接 f(7)*7 = f(8), 但是偶数得到奇数没发现什么规律。。
有没大佬讲一下最后一题的规律
为什么第二题dp超时啊
为什么第二题dfs过不了
蹲一个大佬讲讲第三题
第二题是树形dp题目,一次dfs就能出结果。要记录当前子树的节点数以及子树节点满足两两颜色不同需要的次数,然后就是定义状态转移方程出结果。
第三题, 如果n是偶数, dp[n]=(n-1)*dp[n-1); 如果n是奇数, dp[n] = (n-1)!*(n-1) + (n-1)*dp[n-1)?
同问最后一题
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客220859485号:唉,加油吧老哥,硕士拿13已经很吃亏了。感觉老哥是选择做错了,卷一卷java去互联网后端没问题的,华子也不是只收c++。all in C++是把路走窄了。
点赞 评论 收藏
分享