[HDOJ5573]Binary Tree（找规律，贪心）

时间：2023-03-09 09:17:30
[HDOJ5573]Binary Tree（找规律，贪心）

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

这个题……规律暂时还找不到，先贡献两发TLE的代码吧，一个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 = ;

 ll n, k;

 ll path[maxn][];

 int pcnt;

 //1 + 0 -

 bool exflag;

 void dfs(ll cur, ll lv, ll id) {

     if(exflag) return;

     if(cur == n && lv == k) {

         for(ll i = ; i < pcnt; i++) {

             printf("%I64d %c\n", path[i][], path[i][] ==  ? '+' : '-');

         }

         exflag = ;

         return;

     }

     if(cur != n && lv == k) return;

     path[pcnt][] = id;

     path[pcnt++][] = ;

     dfs(cur+id ,lv+, id*);

     pcnt--;

     path[pcnt][] = id;

     path[pcnt++][] = ;

     dfs(cur+id ,lv+, id*+);

     pcnt--;

     path[pcnt][] = id;

     path[pcnt++][] = ;

     dfs(cur-id ,lv+, id*);

     pcnt--;

     path[pcnt][] = id;

     path[pcnt++][] = ;

     dfs(cur-id ,lv+, id*+);

     pcnt--;

 }

 int main() {

     // freopen("in", "r", stdin);

     int T, _ = ;

     scanf("%d", &T);

     while(T--) {

         scanf("%I64d %I64d", &n, &k);

         pcnt = ; exflag = ;

         printf("Case #%d:\n", _++);

         dfs(, , );

     }

     return ;

 }

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 = ;

ll n, k;

ll f[maxn];

ll ans[maxn];

bool sub[maxn];

void init() {

    f[] = ;

    for(int i = ; i < maxn; i++) {

        f[i] = f[i-] * ;

    }

}

int main() {

    // freopen("in", "r", stdin);

    int T, _ = ;

    init();

    scanf("%d", &T);

    while(T--) {

        scanf("%I64d %I64d", &n, &k);

        for(int i = ; i <= k; i++)

            ans[i] = f[i-];

        if(n %  == ) ans[k]++;

        ll nn =  << k;

        bool exflag = ;

        for(ll i = ; i < nn; i++) {

            if(exflag) break;

            ll cur = ;

            memset(sub, , sizeof(sub));

            for(ll j = ; j <= k; j++) {

                if(( << j) & i) {

                    sub[j] = ;

                    cur -= ans[j];

                }

                else cur += ans[j];

            }

            if(cur == n) exflag = ;

        }

        printf("Case #%d:\n", _++);

        for(ll i = ; i <= k; i++) {

            printf("%I64d ", ans[i]);

            if(sub[i]) printf("-\n");

            else printf("+\n");

        }

    }

    return ;

}

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的二进制数的位置，把它们标记为'-'即可。

 #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 = ;

 ll n, k;

 ll f[maxn];

 ll ans[maxn];

 bool sub[maxn];

 void init() {

     f[] = ;

     for(int i = ; i < maxn; i++) {

         f[i] = f[i-] * ;

     }

 }

 int main() {

     // freopen("in", "r", stdin);

     int T, _ = ;

     init();

     scanf("%d", &T);

     while(T--) {

         scanf("%I64d %I64d", &n, &k);

         memset(sub, , sizeof(sub));

         for(int i = ; i <= k; i++)

             ans[i] = f[i-];

         ll remain = f[k] - n - ;

         if(n %  == ) {

             ans[k]++;

             remain++;

         }

         remain >>= ;

         int cnt = ;

         while(remain) {

             if(remain %  == ) sub[cnt] = ;

             remain >>= ;

             cnt++;

         }

         printf("Case #%d:\n", _++);

         for(int i = ; i <= k; i++) {

             printf("%I64d ", ans[i]);

             sub[i] ? printf("-\n") : printf("+\n");

         }

     }

     return ;

 }

相关文章