本文主要是介绍Wannafly挑战赛29-御坂美琴(递归模拟)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://ac.nowcoder.com/acm/contest/271/A
来源：牛客网
题目描述
misaka是呱太爷爷的小粉丝，呱太爷爷有一句话说的好："一尺之棰，日取其半，万世不竭"。
misaka现在有 n 个呱太玩偶放在一堆，每一次操作，misaka会选择当前个数 > 1 的一堆呱太玩偶。并将这一堆呱太玩偶分成 和
两堆，x 是当前这一堆玩偶的个数。现在 misaka 想将玩偶分成 m 堆，其中第 i 堆呱太玩偶的个数是 ai ，你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆。如果可以输出
，否则输出
。
输入描述:
第一行两个数 n, m 。 接下来一行 m 个数 ai 。
输出描述:
输出共一个字符串 ，表示 misaka 能否将玩偶分成指定的 m 堆。
示例1
输入
复制
4 1 5
输出
复制
ham
思路：递归对n 个呱太玩偶进行题述操作，直到不能拆为止，对操作得到的数字，用map标记一下(1表示可以得到，0表示得不到)，最后再跑一遍，不符合就输出"ham"。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
map<ll, int>mp;
ll n,m,a[maxn];
void DFS(ll n)
{if (mp[n]) return;mp[n] = 1;if (n <= 1) return;DFS(n/2);DFS(n-n/2);
}
int main()
{scanf("%lld%lld",&n,&m);ll sum = 0;for(int i = 1; i <= m; i++){scanf("%lld",&a[i]);sum += a[i];}if(sum != n){ puts("ham"); return 0; }DFS(n);int k = 0;for(int i = 1; i <= m; i++)if (!mp[a[i]]){ puts("ham"); return 0; }puts("misaka");
}
这篇关于Wannafly挑战赛29-御坂美琴(递归模拟)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
