腾讯笔试编程题交流
第一题
给出一个n个节点的无向图，所有节点之间都有通路，通路的权值都是0-9，起点在0号节点，目标是1号节点。有一个附加条件，你可以使k条边的权值减半，求最短路径。
解法来自大佬
dp[i][j][k]表示当前在i要走j步到1，还可以使用k次魔法，然后j从0到n-1 dp
第二题
你有很多硬币，面额为1，2，4，8，....，2^k，每种面额的硬币有两个，要求凑出n元来，输出不同的凑硬币方案的数目。
动态规划，下面代码是从评论的大佬重总结的。
// dp[i][j] 表示从最低的二进制位到第 i 位，j = 0 表示不能进位，j = 1 表示可以进位的方案数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
ll dp[100][2];
int main(void) {
ll n;
while (cin >> n) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
dp[0][1] = 1;
if (n & 1) dp[0][1] = 0;
for (int i = 1; i <= 60; ++ i) {
if (n & (1LL<<i)) {
dp[i][0] += dp[i - 1][0];
dp[i][0] += dp[i - 1][1];
dp[i][1] += dp[i - 1][1];
} else {
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][0];
dp[i][1] += dp[i - 1][1];
}
}
cout << dp[60][0] << endl;
}
return 0;
}
第三题
输入4个数，a,b,A,B，可以对a,b进行两种操作，同时加一，或者乘2.
目标是使a==A，b==B，输出操作的最小次数。
下面代码是我和同学讨论之后得出的最优解了。
int method1(int a,int b,int A,int B){
if(a>A || b>B) return -1;
int c = a-b,
d = A-B;
if(c*d < 0) return -1;
if(c==0 && d==0){
// ok
}else if(c!=0 && d!=0){
if(d%c!=0) return -1;
int e = d/c;
if(e&(e-1)!=0) return -1;
}else return -1;
int res = 0;
while(true){
if(A==a) return res;
if(A%2==0){
if(A/2>=a){
A>>=1;
res++;
}else{
res += A-a;
return res;
}
}else{
A-=1;
res++;
}
}
}
