【jzoj2402】【分治】【2012.02.25普及組】探索的奶牛（search）

題目描述

FJ的奶牛喜歡探索農場周圍的地形。一開始，所有N(1<=N<=1,000,000,000)隻奶牛一起出發，但當碰到路口時，這一群牛可能會分成兩部分(不能為空)，每一部分都繼續前進，當碰到另一個路口時，再分成兩部分，如此反複下去。假設路上到處都是新的岔口，計算最終被分成多少支隊伍。

輸入

第1行: 兩個用空格隔開的整數：N，K，其中K表示分裂時兩個隊伍的奶牛數目差。

輸出

1行: 輸出一個整數表示最終的隊伍數。

樣例輸入

6 2
           

樣例輸出

3
           

提示

輸入說明：有6隻奶牛，分裂時兩個小組的奶牛差為2.

輸出說明：最終有3支隊伍分别為

數量分别為2,1,3。

解題思路

分治： d f s ( s ) dfs(s) dfs(s)表示目前隊伍的奶牛數為 s s s

兩條隊伍可以了解為 x + y = s x+y=s x+y=s且 x − y = m x-y=m x−y=m（假設 x > y x>y x>y）

那麼按照顯而易見的公式 x = ( s + m ) / 2 、 y = ( s − m ) / 2 x=(s+m)/2、y=(s-m)/2 x=(s+m)/2、y=(s−m)/2

當不能繼續分開隊伍時，就對答案貢獻1

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,Gun;
void dfs(int s){
	if(s<=m+1||s%2!=m%2){//不可能繼續分的情況
		++Gun;
		return;
	}
	int x=(s-m)/2,y=(s+m)/2;
	if(x+y!=s){
		++Gun;
		return;
	}
	dfs(x);
	dfs(y);
}
int main(){
	freopen("search.in","r",stdin);
	freopen("search.out","w",stdout);
	scanf("%d%d",&n,&m);
	dfs(n);
	printf("%d",Gun);
}