題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5573

這個題……規律暫時還找不到，先貢獻兩發TLE的代碼吧，一個dfs一個狀壓枚舉。

1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 typedef long long ll; 23 const int maxn = 66; 24 25 ll n, k; 26 ll path[maxn][3]; 27 int pcnt; 28 //1 + 0 - 29 bool exflag; 30 void dfs(ll cur, ll lv, ll id) { 31 if(exflag) return; 32 if(cur == n && lv == k) { 33 for(ll i = 0; i < pcnt; i++) { 34 printf("%I64d %c\n", path[i][0], path[i][1] == 1 ? '+' : '-'); 35 } 36 exflag = 1; 37 return; 38 } 39 if(cur != n && lv == k) return; 40 41 path[pcnt][0] = id; 42 path[pcnt++][1] = 1; 43 dfs(cur+id ,lv+1, id*2); 44 pcnt--; 45 46 path[pcnt][0] = id; 47 path[pcnt++][1] = 1; 48 dfs(cur+id ,lv+1, id*2+1); 49 pcnt--; 50 51 path[pcnt][0] = id; 52 path[pcnt++][1] = 0; 53 dfs(cur-id ,lv+1, id*2); 54 pcnt--; 55 56 path[pcnt][0] = id; 57 path[pcnt++][1] = 0; 58 dfs(cur-id ,lv+1, id*2+1); 59 pcnt--; 60 } 61 62 int main() { 63 // freopen("in", "r", stdin); 64 int T, _ = 1; 65 scanf("%d", &T); 66 while(T--) { 67 scanf("%I64d %I64d", &n, &k); 68 pcnt = 0; exflag = 0; 69 printf("Case #%d:\n", _++); 70 dfs(0, 0, 1); 71 } 72 return 0; 73 } DFS #include <algorithm> #include <iostream> #include <iomanip> #include <cstring> #include <climits> #include <complex> #include <fstream> #include <cassert> #include <cstdio> #include <bitset> #include <vector> #include <deque> #include <queue> #include <stack> #include <ctime> #include <set> #include <map> #include <cmath>using namespace std;typedef long long ll; const int maxn = 66; ll n, k; ll f[maxn]; ll ans[maxn]; bool sub[maxn];void init() {f[0] = 1;for(int i = 1; i < maxn; i++) {f[i] = f[i-1] * 2;} }int main() {// freopen("in", "r", stdin);int T, _ = 1;init();scanf("%d", &T);while(T--) {scanf("%I64d %I64d", &n, &k);for(int i = 1; i <= k; i++)ans[i] = f[i-1];if(n % 2 == 0) ans[k]++;ll nn = 1 << k;bool exflag = 0;for(ll i = 1; i < nn; i++) {if(exflag) break;ll cur = 0;memset(sub, 0, sizeof(sub));for(ll j = 1; j <= k; j++) {if((1 << j) & i) {sub[j] = 1;cur -= ans[j];}else cur += ans[j];}if(cur == n) exflag = 1;}printf("Case #%d:\n", _++);for(ll i = 1; i <= k; i++) {printf("%I64d ", ans[i]);if(sub[i]) printf("-\n");else printf("+\n");}}return 0; } ENUM

?

這個題想了很多天，想明白了其實還蠻簡單的。

題目給了一棵滿二叉樹，按照層次遍歷從左到右挨個編號1 2 3....問蛤蛤從根節點向下走，走到一個點可以加上當前節點編號也可以刪掉當前節點編號。問走k層能否恰好續夠n。

題目中給了一個條件：N≤2^K≤2^60

因為讀題坑掉了沒看到這個條件，浪費了很多時間在例如n=10 k=3的情況上。這種情況在我的搜索中是完全有結果的，但是實際上這個情況不會在題目中出現，因為8<10。

這樣就好辦了，我們考慮任何一個十進制數都可以表示為二進制，這個二進制表示了某一位上是否要加上對應的2的冪次。

（以上皆為口胡+腦補，正常題解在下面）

N<=2^k意味著我們總能找到第k+1個節點，使得N小于k+1節點的數值。既然如此，我們貪心地選取最左邊的一條鏈。這樣，最左邊那個點必然是整層最小的。對于本題目而言，總有2^(k+1)-1≥n。

由于最左側的鏈均為2的冪次，我們以前的知識中一定有這樣一條規律：2^(k)-1=∑i(1,k-1)2^i。表達不清楚，舉個例子：32-1=1+2+4+8+16。

我們假設整條長度為k鏈都是加的，那它的總和就是2^(k+1)-1，我們現在知道要求的n，那我們不需要的那部分的值為2^(k+1)-1-n。

假設這個值為x，那x也總是能表達為一個二進制數，我們只需要在這個鏈子上找到可以表示x的二進制數的位置，把它們標記為'-'即可。

1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 typedef long long ll; 23 const int maxn = 66; 24 ll n, k; 25 ll f[maxn]; 26 ll ans[maxn]; 27 bool sub[maxn]; 28 29 void init() { 30 f[0] = 1; 31 for(int i = 1; i < maxn; i++) { 32 f[i] = f[i-1] * 2; 33 } 34 } 35 36 int main() { 37 // freopen("in", "r", stdin); 38 int T, _ = 1; 39 init(); 40 scanf("%d", &T); 41 while(T--) { 42 scanf("%I64d %I64d", &n, &k); 43 memset(sub, 0, sizeof(sub)); 44 for(int i = 1; i <= k; i++) 45 ans[i] = f[i-1]; 46 ll remain = f[k] - n - 1; 47 if(n % 2 == 0) { 48 ans[k]++; 49 remain++; 50 } 51 remain >>= 1; 52 int cnt = 1; 53 while(remain) { 54 if(remain % 2 == 1) sub[cnt] = 1; 55 remain >>= 1; 56 cnt++; 57 } 58 printf("Case #%d:\n", _++); 59 for(int i = 1; i <= k; i++) { 60 printf("%I64d ", ans[i]); 61 sub[i] ? printf("-\n") : printf("+\n"); 62 } 63 } 64 return 0; 65 }

?

轉載于:https://www.cnblogs.com/kirai/p/5430063.html

總結

以上是生活随笔為你收集整理的[HDOJ5573]Binary Tree（找规律，贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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