poj 2100 Graveyard Design (two pointers ，尺取法)

 1/*************************************************************************
 2	> File Name: code/poj/2100.cpp
 3	> Author: 111qqz
 4	> Email: rkz2013@126.com 
 5	> Created Time: 2015年09月25日 星期五 00时42分49秒
 6 ************************************************************************/
 7
 8#include<iostream>
 9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)  
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31LL n;
32LL maxn;
33vector<LL>ans;
34
35
36void solve()
37{
38    LL head = 1,tail = 1;
39    LL sum = 0 ;
40
41    while (tail<=maxn)
42    {
43	sum = sum + tail*tail;
44
45	if (sum>=n)
46	{
47	    while (sum>n)//主要是while，因为可能要减掉多个才能小于n
48	    {
49		sum -= head*head;
50		head++;
51	    }
52	    if (sum==n)
53	    {//因为要先输出答案个数...所以必须存起来延迟输出...
54		ans.push_back(head);
55		ans.push_back(tail);
56	    }
57	}
58	tail++;
59    }
60    LL sz = ans.size();
61    printf("%lld\n",sz/2);
62    for (LL i = 0 ; i<ans.size() ; i = i +2)
63    {
64	printf("%lld",ans[i+1]-ans[i]+1);
65	for ( LL j = ans[i] ; j <=ans[i+1] ; j++) printf(" %lld",j);
66	printf("\n");
67    }
68
69}
70int main()
71{
72  #ifndef  ONLINE_JUDGE 
73   freopen("in.txt","r",stdin);
74  #endif
75    scanf("%lld",&n);  
76    maxn = ceil(sqrt(n));
77    solve();
78
79 #ifndef ONLINE_JUDGE  
80  fclose(stdin);
81  #endif
82	return 0;
83}