主要思想:
本题可以抽象为一个二叉树模型,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')
'''