POJ 2100 Graveyard Design 题解 《挑战程序设计竞赛》

POJ 2100 Graveyard Design

盗墓：将一个整数分解为连续数平方之和，有多少种分法？

3.2常用技巧精选（一）

尺取法

本身简单，IO蛋疼。今天心情特好，也就不计较了。输出格式要先统计有多少个答案，所以饶了些弯弯，那种算法完美，IO超时的滋味，啧啧，真是美妙。

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ULL;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ULL n;
	vector<pair<ULL, ULL> > answer;
	while (cin >> n)
	{
		ULL l = 1, r = 1, sum = 0, sq = 0;
		for (;;)
		{
			while (sum < n)
			{
				sq = r * r;
				sum += sq;
				++r;
			}
			if (sq > n)
			{
				break;
			}
			if (sum == n)
			{
				answer.push_back(make_pair(l, r));
			}
			sum -= l * l;
			++l;
		}
		cout << answer.size() << endl;
		for (vector<pair<ULL, ULL> >::const_iterator it = answer.begin(); it != answer.end(); ++it)
		{
			int b = it->first, e = it->second;
			cout << e - b << ' ';
			for (int i = b; i < e; ++i)
			{
				cout << i << ' ';
			}
			cout << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

在IO上慢了些，用printf会快不少。

附上我优雅的stream与该死的IO苦苦斗争一个小时的成果：

#include <iostream>
#include <queue>
#include <sstream>
using namespace std;
typedef unsigned long long ULL;

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ULL n;
	queue<ULL> que;
	vector<string> answer;
	while (cin >> n)
	{
		ULL l = 1, r = 1, sum = 0, sq = 0;
		for (;;)
		{
			while (sum < n)
			{
				sq = r * r;
				sum += sq;
				que.push(r);
				++r;
			}
			if (sq > n)
			{
				break;
			}
			if (sum == n)
			{
				stringstream sstream;
				queue<ULL> temp(que);
				sstream << temp.size() << ' ';
				while (temp.size())
				{
					sstream << temp.front() << ' ';
					temp.pop();
				}
				answer.push_back(sstream.str());
			}
			sum -= l * l;
			++l;
			que.pop();
		}
		cout << answer.size() << endl;
		copy(answer.begin(), answer.end(), ostream_iterator<string>(cout, "\n"));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2100 Graveyard Design 题解 《挑战程序设计竞赛》