首页 > 试题广场 >

御坂美琴

[编程题]御坂美琴
misaka是呱太爷爷的小粉丝,呱太爷爷有一句话说的好:"一尺之棰,日取其半,万世不竭"。

misaka现在有 n 个呱太玩偶放在一堆,每一次操作,misaka会选择当前个数 > 1 的一堆呱太玩偶。并将这一堆呱太玩偶分成 两堆,x 是当前这一堆玩偶的个数。现在 misaka 想将玩偶分成 m 堆,其中第 i 堆呱太玩偶的个数是 ai ,你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆。如果可以输出 ,否则输出

输入描述:
第一行两个数 n, m 。
接下来一行 m 个数 ai


输出描述:
输出共一个字符串 ,表示 misaka 能否将玩偶分成指定的 m 堆。
示例1

输入

4 1
5

输出

ham

备注:
1 ≤ n ≤ 1018, 1 ≤ m ≤ 105, 1 ≤ ai ≤ 1018
头像 狗都不学py算法
发表于 2022-01-25 17:39:58
主要思想: 本题可以抽象为一个二叉树模型,n为根节点,则其分配的所有玩偶堆与所有的叶子节点一一对应。 因此可以用dfs搜索所有的答案。 总体思路 先用map统计出a中出现的所有数,再带入dfs中边搜索边清空,如果成功搜索并且map已为空(tot==n此时已经满足),则成功分堆,反之失败 代码讲解: 展开全文