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
26 using namespace std;
27 #define For(i, n) for (int i=0;i<int(n);++i)  
28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 LL n;
32 LL maxn;
33 vector<LL>ans;
34 
35 
36 void 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 }
70 int 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 }