題目轉載自：http://blog.csdn.net/uncle_gy/article/details/77977436

2017年9月13日：?

騰訊有一道機試題：?
大概意思是：?
小Q非常富有，擁有非常多的硬幣，小Q的擁有的硬幣是有規律的，對于所有的非負整數K,小Q恰好各有兩個數值為2^k，的硬幣，所以小Q擁有的硬幣是1，1，2，2，4，4……，小Q賣東西需要支付n元錢，請問小Q想知道有多少種組合方案。?
輸入：一個n (1<=n<=10^18),代表要付的錢?

輸出：表示小Q可以拼湊的方案數目

數位dp是一個不錯的解法

但是我想用記憶化搜索來做：

思路

對于n可以選擇一個最接近的硬幣選擇使用0,1,2個硬幣去填充。然后遞歸到下一層去處理，采用記憶化搜索的方法。

計算復雜度帶log，遞歸次數跟數位dp差不多。

#include<stdio.h> #include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<set> #include<map> using namespace std; #define ll long long struct Node{ll l;int d; }; bool operator <(const Node a,const Node b) {if(a.d == b.d) return a.l < b.l;return a.d < b.d; } map<Node,int> haha; int c = 0; int getAns(ll n,int d){c++;if(n == 0){return 1;}Node x;x.l = n;x.d = d;if(haha.find(x) != haha.end()) return haha[x];ll t = 0;for(int i = 0;i <= d; i++){t += (1ll<<i)*2;}if(t < n) return 0;int ans = 0;t = 0;for(int i = d;i >= 0; i--){t = 1ll<<i;if(t > n) continue;if(t<=n) ans+=getAns(n-t,i-1);t += t;if(t<=n) ans+=getAns(n-t,i-1);ans += getAns(n,i-1);break;}haha[x] = ans;return ans;}int main(){ll n;while(cin>>n){c = 0;cout<<getAns(n,60)<<endl;cout<<c<<endl;continue;set<ll> s;for(int i = 0;i <=n/2;++i){ll p = (n-i)^i;s.insert(p);}cout<<s.size()<<endl;} } /*** 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10000000000 100000000000 1000000000000 10000000000000 100000000000000 1000000000000000 10000000000000000 100000000000000000 1000000000000000000 **/

總結

以上是生活随笔為你收集整理的2017年腾讯笔试题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。