题解 P2907 【[USACO08OPEN]农场周围的道路Roads Around The Farm】

HHH恢 · 2018-05-23 23:29:10 · 题解

我也是第一次发题解......选了个简单的题

------------华丽丽的分割线------------

1. 假设牛群有n头牛
2. 假设分成两部分的牛数恰好相差k

即:

牛多的部分:(n+k)/2头

牛少的部分:(n-k)/2头

那么牛群要可分,需要满足:

1. (n-k)>0 //没牛分什么.....
2. (n-k)为偶数//没个两双牛还敢除二??

由此可得代码(递归):

#include<iostream>
using namespace std;

int k;
int f(int a){       //请别吐槽这个函数名-_-||
    if(a-k>0&&(a-k)%2==0)return f((a+k)/2)+f((a-k)/2);//终于散伙咯
    else return 1;  //想分手!没门
}

int main(){
    int n;
    cin>>n>>k;
    cout<<f(n);
    return 0;
}