百度春招笔试 系统研发工程师 题解
第一题，经典题，给一个长度为n的数字，往里面插入k个乘号，求最大可能的乘积。我用了记忆化搜索。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
unsigned long long dp[100][100];
int n, k;
int val[100];
string input;
unsigned long long getval(int lend, int rend);
unsigned long long dfs(int nn, int kk)
{ if(kk == 0) return (dp[nn][kk] = getval(0, nn)); if(kk < 0) return 0;
if(dp[nn][kk] != -1)
return dp[nn][kk];
if(kk > nn)
return (dp[nn][kk] = 0);
unsigned long long ans = 0, temp;
for(int i = 0; i < nn; i++)//The pre multiply sign is after i-th number
{
temp = dfs(i, kk - 1) * getval(i + 1, nn);
ans = max(ans, temp);
}
return (dp[nn][kk] = ans);
}
unsigned long long getval(int lend, int rend)//zuobi youbi
{
unsigned long long ans = 0;
for(int i = lend; i <= rend; i++)
{
ans = ans * 10;
ans += val[i];
}
return ans;
}
int main(void)
{
memset(dp, -1, sizeof(dp));
cin >> n >> k;
cin >> input; for(int i = 0; i < n; i++) val[i] = input[i] - '0';
cout << dfs(n - 1, k) << endl;
return 0;
}
有一些小的bug，做了大概30min。
第二题，每个节点出度只有1，求整个图最小的环的大小。因为我没有保存代码所以说一下思路。
思路就是dfs，用一个dis数组记录距离，初始化为-1；如果搜索到一个已经搜过的节点（dis[i] != -1)，那么说明有环，直接减一下就可以。
这道题的麻烦之处在于可能有多个连通块，如果我们只从1号节点开始dfs，只能通过30%的数据。
那么如何处理多个连通块呢？这里一不小心，可能会只通过0%的数据，如果你这么写的话：
for(int i = 1;i <= n;i++)
if(dis[i] == -1)
dfs(i);
为什么呢？想象这样的情况：
1 ->2; 2 ->3; 3 ->2
如果我们之前已经搜索了2，3；这次从1开始搜索，那么2 3 这个环的大小就会被错误计算。
我的解决方案是使用并查集，每个连通块只dfs一次。我们能够保证如果每个连通块有环，那么dfs一次一定能找到对应的环。
代码因为忘了保存，希望楼下有聚聚能够贴上来qaq
#春招#