放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

POJ 2739 Sum of Consecutive Prime Numbers 题解 《挑战程序设计竞赛》

目录

POJ 2739 Sum of Consecutive Prime Numbers

连续素数和:将一个整数分解为连续的素数之和,有多少种分法?

3.2常用技巧精选(一)

尺取法

简单,一次就AC了。先艾氏筛法做一份素数表,然后在素数表上爬行一遍就行了。最近好多事,通宵吧,第二天吃不消,不通宵吧,事情多得睡不着……

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 10000 + 16

// 先生成MAX_PRIME内的素数表
#define MAX_PRIME MAX_N
vector<int> primes;
vector<bool> is_prime;
void init_primes()
{
	is_prime = vector<bool>(MAX_PRIME + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= MAX_PRIME; ++i)
	{
		if (is_prime[i])
		{
			primes.push_back(i);
			for (int j = i * 2; j <= MAX_PRIME; j += i)
			{
				is_prime[j] = false;
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	init_primes();
	const int size = primes.size();
	int n;
	while (cin >> n && n)
	{
		int l = 0, r = 0, sum = 0, result = 0;
		for (;;)
		{
			while (sum < n && r < size)
			{
				sum += primes[r++];
			}
			if (sum < n)
			{
				break;
			}
			else if (sum == n)
			{
				++result;
			}
			sum -= primes[l++];
		}
		cout << result << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

又看到了神奇的0毫秒:

12877923 hankcs 2739 Accepted 260K 0MS C++ 1226B 2014-05-15 00:05:01

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2739 Sum of Consecutive Prime Numbers 题解 《挑战程序设计竞赛》

评论 欢迎留言

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

我的作品

HanLP自然语言处理包《自然语言处理入门》