链接：https://ac.nowcoder.com/acm/contest/271/A
来源：牛客网
第一行两个数 n, m 。i
接下来一行 m 个数 a
。
输出共一个字符串
，表示 misaka 能否将玩偶分成指定的 m 堆。
1 ≤ n ≤ 1018
, 1 ≤ m ≤ 105
, 1 ≤ ai
≤ 1018
。
思路：用dfs找出所有能分出堆玩偶数目的情况，并用map标记为1，然后每输入一个数进行判断是否可以map是否为1，如果不为1，表示无法分出该结果。再判断一下m堆玩偶的总数是否n，可否分为m堆即可。
注意需要剪枝一下，否则会超时。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const ll mod=1e9+7; ll n,m,a[100005]; map<ll,int> mp; void init(ll x) { if(mp[x]==1) //说明x已经标记过了，不用再递归下去了，不能去除，否则超时。 return; mp[x]=1; if(x==1) return; ll u=x/2,v=x-x/2; init(u); init(v); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; init(n); ll sum=0,flag=0; for(int i=1;i<=m;i++) { cin>>a[i]; if(sum<=n) sum+=a[i]; if(sum>n) flag=1; if(mp[a[i]]==0) flag=1; } if(flag||m>n||sum!=n) { cout<<"ham"<<endl; return 0; } else cout<<"misaka"<<endl; return 0; }
原文：https://www.cnblogs.com/zjl192628928/p/10013596.html