题解P2907 农场周围的道路Roads Around The Farm

Posted by n0000000000o's Blog on April 18, 2018

题目 P2907

分析题意,只要分后两群奶牛的差为k 这群奶牛就可以分

假设总数q能被分为两部分,相差为k,那么设其中一部分为x,则这两群奶牛x1,x2可分别表示为

x1=x

x2=x+k

-> x+k + x=q

–> x=(q-k)/2

有为了满足实际条件,x1,x2都要为整数(不可能有半只奶牛吧。。。) 这便是主要思路。。

在此附上代码:

#include <bits/stdc++.h>
using namespace std;
int num=1;
int n,k;
void apart(int q)
{
    if(q-k<=0)//这时就不能再分了,因而要返回
        return;
    
    //恩。。见上方的说明
    //如果((q-k)/2)==((q-k)/2.0),即这个数是整数,也就是说,-----((q-k)/2)有整数解!!!
    if(((q-k)/2)==((q-k)/2.0))
    {
        num++;//奶牛多分了一列
        apart((q-k)/2);
        apart(k+(q-k)/2);//再分别递归x1和x2
    }
}
int main()
{
    cin>>n>>k;
    apart(n);
    cout<<num;//直接输出结果~~~
}