放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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会快不少。

12882502 hankcs 2100 Accepted 248K 3032MS C++ 1104B 2014-05-16 01:55:11

附上我优雅的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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机