蚂蚁工程技术岗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)？

同问最后一题