时间Vs杀手

牛客Wannafly挑战赛29--A.御坂美琴
题目链接:https://ac.nowcoder.com/acm/contest/271/A思路:相当于一根竹竿,...
扫描右侧二维码阅读全文
24
2018/11

牛客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:

#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");
}
Last modification:November 24th, 2018 at 11:22 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment