| Time Limit: 10000MS | Memory Limit: 64000K | |
| Total Submissions: 6597 | Accepted: 1588 | |
| Case Time Limit: 2000MS | ||
Description
Input
Output
Sample Input
2030
Sample Output
2 4 21 22 23 24 3 25 26 27
题意:国王要建造墓地，墓地可以分n块区域(n=1,2...),且区域是线性排列的，区域从前到后依次分配连续自然数的平方块墓碑。现在给你需要放置的墓碑的总数，让你给出所有可能的分配情况。
思路：尺取法。
AC代码：
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef unsigned long long ll; const int N_MAX = 100000; bool what; ll num; vector<pair<ll, ll>>answer; int main() { ll n; while (scanf("%lld", &n) != EOF) { num = 0; ll l = 1, r = 1, sum = 0; while (1) { for (;;) { while ( r*r<=n&&sum < n) { sum += r*r; r++; } if (sum < n) { what = 0; break; } if (sum == n) { /////记录数据 answer.push_back(make_pair(l,r-1)); ///// what = 1; num++; break; } sum -= l*l; l++; } if (what) { l++; r = l; sum = 0; } else break; } /////// printf("%lld\n",num); for (vector<pair<ll, ll>>::iterator it = answer.begin(); it != answer.end(); it++) { printf("%lld",it->second-it->first+1); for (ll j =it->first; j <= it->second; j++) printf("% lld", j); printf("\n"); } /////////// } return 0; }
原文：http://www.cnblogs.com/ZefengYao/p/6480190.html