首页 > USACO题解 > USACO Arithmetic Progressions

USACO Arithmetic Progressions

Arithmetic Progressions题目大概意思:一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2+q^2的数的集合)S中长度为n的等差数列。

这个题目拿到手感觉只能暴力搜索,事实便是如此。而且题目给了5秒钟的时限,于是我就开始写搜索了。提交之后在中间某一组数据果断超时了。实在想不到该怎么优化。后来看了别人的解题报告,说是可以剪枝。

本题的一大关键剪枝在于:首先你选择一个a,然后你会一个一个的枚举b,这个时候,你可以先判断一下a+(n-1)*b是否比2*m*m还要大,也就是说,如果都超出了最大的可能范围,那么就不必测试这个等差数列了。于是,我就continue了。再次提交时又TLE了。想想自己真笨,为什么要continue,break岂不是更好?是的。既然当前的b都不行,接下来的b肯定会更大(事先要给产生的双平方数从小到大排序:)),改成break之后就可以过了,下面是鄙人代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
	ID:stackex1
	LANG:C++
	PROG:ariprog
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
#define MAX_NUM 65536
#define RES_NUM 10100
 
typedef struct TagNode
{
	int a;
	int b;
}Node;
 
int e[MAX_NUM], el;
bool flag[MAX_NUM] = {0};
Node res[RES_NUM];
int idx;
int n, m;
 
void init()
{
	int i, j, k, tmp;
	k = idx = 0;
	for(i = 0; i <= m; ++i)
		for(j = i; j <= m; ++j)
		{
			tmp = i*i + j*j;
			if(!flag[tmp])
			{
				e[k] = tmp;
				++k;
				flag[tmp] = true;
			}
		}
	el = k;
	sort(e, e + el);
}
 
template<class T>
struct cmp
{
public:
	bool operator()(const T& x, const T& y) const
	{
		if(x.b != y.b)
			return x.b < y.b;
		return x.a < y.a;
	}
};
 
void work()
{
	int i, j;
	int d, l;
	int maxe = 2*m*m;
	for(i = 0; i < el; ++i)
	{
		for(j = i + 1; j < el; ++j)
		{
			d = e[j] - e[i];
			l = 2;
			//关键剪枝注意是break而不是continue
			if(e[i] + (n-1)*d > maxe)break;
			while(l < n && binary_search(e, e + el, e[i]+l*d))
			{
				++l;
			}
			if(l == n)
			{
				res[idx].a = e[i];
				res[idx].b = d;
				++idx;
			}
		}
	}
	sort(res, res+idx, cmp<Node>());
}
 
inline void get_input()
{
	FILE *fin = fopen("ariprog.in", "r");
	fscanf(fin, "%d %d", &n, &m);
	fclose(fin);
}
 
void get_output()
{
	FILE *fout = fopen("ariprog.out", "w");
	int i;
	if(idx == 0)
	{
		fprintf(fout, "NONE\n");
		return ;
	}
	for(i = 0; i < idx; ++i)
	{
		fprintf(fout, "%d %d\n", res[i].a, res[i].b);
	}
	fclose(fout);
}
 
int main(int argc, char **argv)
{
	get_input();
	init();
	work();
	get_output();
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Arithmetic Progressions
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: , , ,
  1. freeboy1015
    2012年10月10日15:29 | #1

    双平方数集合是所有能表示成p2+q2的数的集合。

    题目中给的例子:
    输入:5 7(即n、m)
    输出:
    1 4
    37 4
    2 8
    29 8
    1 12
    5 12
    13 12
    17 12
    5 20
    2 24

    先看第一行的结果:1 4(对应a和b)
    得到的等差数列为: 5 9 13 16 21,其中21并不能分解为两个数的平方和啊。

    再看最后一列:2 24
    2+24*5 > 7*7+7*7 啊

    这是怎么回事,难道是我对题目的理解有问题?

    [回复]

    金大仙 回复:

    @freeboy1015, 应该是2+24*(5-1)=7*7+7*7

    [回复]

  2. 2014年9月5日14:40 | #2

    代码提交上去过不了啊~ 本机跑跟交上去测验结果不一致

    [回复]

  3. rango
    2015年7月13日19:12 | #3

    二分查找那里还可以优化吧,直接用flag数组的哈希就能做判断了

    [回复]