牛客Wannafly挑战赛29--A.御坂美琴

题目链接:https://ac.nowcoder.com/acm/contest/271/A

思路:
相当于一根竹竿,每次选择长度大于1的竹竿,将其从中间折断,如果竹竿的长度为偶数,则分成的两根竹竿长度相等,如果竹竿的长度为奇数,则分成的两根竹竿长度分别为x/2,x-x/2,x是竹竿的长度。
题目中给出了最后一共有m根竹竿,和每根竹竿的长度ai,问是否有可能经过若干次操作,使长度为n的竹竿最后变成m根竹竿,每根竹竿长度为ai。
使用递归的方法,对折断竹竿的操作进行模拟,并在递归的过程中把生成的竹竿的长度保存在map中,为了剪枝优化,如果该长度的竹竿已经存在了,则return,如果竹竿的长度为1,return。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#include<map>
#define LL long long
using namespace std;



LL a[100005];
LL n,m;
LL ans;
map<int,int> ok;

void dfs(LL x){
if(ok[x])return;
ok[x] = 1;
if(x==1)return;
dfs(x>>1);
dfs(x-x/2);
}

int main(){
cin>>n>>m;
ans = 0;
for(int i=0;i<m;i++){
cin>>a[i];
ans+=a[i];
if(ans>n)return puts("ham"),0;
}
if(ans!=n)return puts("ham"),0;
dfs(n);
for(int i=0;i<m;i++){
if(!ok[a[i]])return puts("ham"),0;
}
puts("misaka");
}