主要思想:

本题可以抽象为一个二叉树模型,n为根节点,则其分配的所有玩偶堆与所有的叶子节点一一对应。 因此可以用dfs搜索所有的答案。

总体思路

先用map统计出a中出现的所有数,再带入dfs中边搜索边清空,如果成功搜索并且map已为空(tot==n此时已经满足),则成功分堆,反之失败

代码讲解:

下面贴出c++与python的代码,其中c++代码有讲解

(同时py中鞭尸一个错误但是ac的部分代码)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,tot;
map<ll,int>cnt;
bool dfs(ll n)
{
    /*如果搜到这个数,则其子节点都不必再搜索,因为它就是叶子节点,返回true
      这里想不明白可以用反证法:如果它的子节点存在,也就是它已经被分解,那就搜不到它
    */
    if(cnt.find(n)!=cnt.end())
    {
        --cnt[n];
        if(cnt[n]<1) cnt.erase(n);
        return true;
    }
    //如果到小于2,也就是n的值是1,但是还没有被匹配,那么说明搜索失败
    if(n<2) return false;
    //递归两个子节点
    return dfs(n/2)&&dfs(n-n/2);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        ll x;
        scanf("%lld",&x);
        cnt[x]++;
        tot+=x;
    }
    // 这里tot==n不写也可以
    if(tot==n && dfs(n) && cnt.size()==0)
        puts("misaka\n");
    else
        puts("ham\n");
    return 0;
}
}
import sys 

def dfs(n):
    if n in cnt:
        cnt[n]-=1
        if cnt[n]==0:
            cnt.pop(n)
        return True
    if n<1:
        return False
    return dfs(n//2) and dfs(n-n//2)

if __name__=="__main__":
    n,m=map(int,input().split())
    cnt=dict()
    a=list(map(int,input().split()))
    tot=0
    for i in range(m):
        if a[i] in cnt:
            cnt[a[i]]+=1 
        else:
            cnt[a[i]]=1
        tot+=a[i]
    if tot==n and dfs(n) and len(cnt)==0:
        print("misaka")
    else:
        print("ham")

'''错误做法 但是ac。。
6 3 
2 2 2
样例错误
def dfs(n):
    if n in ma:
        return 
    ma[n]=1 
    dfs(n//2)
    dfs(n-n//2)

if __name__=="__main__":
    n,m=map(int,input().split())
    a=[0]*m
    su=0
    ma=dict() 
    a=list(map(int,input().split()))
    for i in range(m):
        su+=a[i] 
    if su!=n:
        print('ham')
        sys.exit() 
    dfs(n)
    ok=1 
    for i in range(m):
        if a[i] not in ma:
            ok=0
            break 
    if ok:
        print("misaka")
    else: print('ham')

'''