腾讯编程交流~

只编完了第一题和第二题，和测试案例是匹配的。但是，最后一题还没来得及读就结束了。

硬币是把它二进制数的10序列中10的数量相乘+1再相乘 11111000100011； 最右的1不管，有两个10序列，一个是11111000，另一个1000； 序列内相乘就是 5*3+1=16,1*3+1=4； 然后所有的相乘，16*4=64。 反正我的用例对了，是不是对的就不造了...第二题选错了语言，吐血

心累 ，一次次失去机会

思想说说啊

我觉得我后悔没有做模拟题了

第一道，bfs 第二道，dfs，应该过不了大数 第三道，不会

有方案嘛硬币。。 贪心算法 但是不会。。。

第三道题我觉得也是bfs，但是我没来得及写，硬币那个就是把这个数弄成一个2进制数，还有最短路那题我是用dfs的，结果不知道对不对  ，反正测试用例对了，把k改成1也对了

怎么说这次腾讯的题呢！怎么写都知道，就是不能用那个编译器写出来

感觉硬币就把数字转为二进制，然后从后往前分别记录当前比特会进位和不会进位的情况数。

第一题直接下一页跳过回不去了...二三题一个DP一个BFS十分钟敲完过样例，能不能AC就不确定了...这破系统坑的一笔

第三题有做出来的么

全部递归。。 感觉都会超时，药丸。。。

还有个abAB的，先判断(A-a)==(B-b),然后c=A/a找到乘2的次数，d=A-a*c找到加的上数，把d分解成1/2/4/8/16....相加，找到加数最少的方式。然后要注意加数<=d。不知道这样对不对？

不能用本地IDE实在太难调了。  第一题写了个BFS+剪枝，不过大数据肯定过不去。 第二题本来想写个二维dij跑最短路的，但是dij模板一下子忘了没写。 第三题想到了和n的二进制10关系有关，最后就剩10分钟没时间写了。 基本GG， 感觉比头条算法岗位还难的题啊

硬币动态规划感觉时间复杂度太高了吧

第一题手滑下一页，没了。 第二题最短路，有点难做不出来。 为什么最简单的抛硬币在第3....看完题目就到点了（16:45）

第二题要考虑所有路径，因为k有限制。 比如用例里，k=2，取最短路0->2->1，其时间为4/2 + 4/2 = 4。 但k=1时，最短路0->2->1的时间为4/2 + 4 = 6，而0->1的时间为9/2 = 4.5。

技术大佬，买片打折哦 比心心 以后可以交流哦 微信：sssxy999 哈哈哈

//硬币问题 转化为二进制 //对于（7）111这类只有一种解法 //对于111.1000.0连续n个1,m个0的共有n * m +1种解法 //然后把二进制串分为x个连续的（11.100.0） //最左的一个(11.100.0) ans[0] = n0 * m0 +1; //先计算最右边两个 (11.100.0)(11.100.0),设有n1个1，m1个0；n0个1，m0个0，那么有 // ans[1] = (n1*m1+1)* (n0*m0+1) + m0中解法； //然后再和左边一个10串计算ans[2] = (n2*m2+1)* ans[1] + m1*ans[0]+ m0; //从优向左依次计算 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { unsigned long long n; while(cin >> n) { vector<int> num; long long onezero[30][2]; long long ans[30]; while(n) { num.push_back( n & 1); n = n >> 1; } // for(int i = num.size()-1; i >=0; --i) // { // cout <<num[i]; // } // cout <<endl; int pair01 = 0; int cnt0 = 0; int cnt1 = 0; bool flag; while((flag = num.front())&& !num.empty()) { num.erase(num.begin()); } if(num.empty()) { cout << 1 <<endl; } else { for(int i = 0; i < num.size(); ++i) { if(num[i] == 1) { if(!flag) { onezero[pair01][0] = cnt0; cnt0 = 0; flag = true; } ++cnt1; if( i == num.size()-1) { onezero[pair01][1] = cnt1; } } else { if(flag) { onezero[pair01++][1] = cnt1; cnt1 = 0; flag = false; } ++cnt0; } } ans[0] = onezero[0][1] * onezero[0][0] +1; for(int k = 1; k <= pair01; ++k) { int join = onezero[0][0]; for(int j = 1; j < k; ++j) { join += onezero[j][0] * ans[j-1]; } ans[k] = (onezero[k][1] * onezero[k][0] +1) * ans[k-1] + join; } cout << ans[pair01]<<endl; } } return 0; }