poj-2140

//132K	110MS	C++
#include <cstring>
#include <cstdio>

using namespace std;

int N;

long long cnt;


void solve(int N) {
	int begin = 1;
	int end = 1;
	long long sum = 1;

	while(1) {
		if (begin > N) {
			break;			
		}

		// if (begin == N) {
		// 	if (sum == N) {
		// 		cnt++;
		// 	}
		// 	break;
		// }

		if (sum == N) {
			cnt++;
			sum -= begin;
			begin++;
		} else if (sum > N) {
			sum -= begin;
			begin++;
		} else if (sum < N) {
			if (end == N) {
				break;
			} else {			
				end++;
				sum += end;
			}
		}
	}
	printf("%lld\n", cnt);
}

int main()
{
	while(scanf("%d", &N) != EOF) {
		cnt = 0;
		solve(N);
	}
	return 0;
}

类似于一个伸缩数组，begin 和 end代表当前被选取的数的范围， 同时维护一个sum来标示当前选择的数的大小，

如果对于某个数N：

如果 N== sum， 那么就是一种组合方案，先将beign+1，并从sum中减去 begin，

如果 N >  sum， 那么也是 begin前进一位， sum减去 begin

如果 N < sum, 那么 end前进一位， sum加上  end+1,

两种情况结束：

<1> sum < N. 但是 end已经到了 N（其实这种情况不可能出现）

<2> begin > N.