首页 > 代码库 > 洛谷P1214 [USACO1.4]等差数列 Arithmetic Progressions
洛谷P1214 [USACO1.4]等差数列 Arithmetic Progressions
P1214 [USACO1.4]等差数列 Arithmetic Progressions
•
o 156通过
o 463提交
• 题目提供者该用户不存在
• 标签USACO
• 难度普及+/提高
提交 讨论 题解
最新讨论
• 这道题有问题
• 怎么进一步优化时间效率啊 …
题目描述
一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。
在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。
输入输出格式
输入格式：
第一行: N(3<= N<=25),要找的等差数列的长度。
第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。
输出格式：
如果没有找到数列,输出`NONE‘。
如果找到了，输出一行或多行, 每行由二个整数组成:a,b。
这些行应该先按b排序再按a排序。
所求的等差数列将不会多于10,000个。
输入输出样例
输入样例#1：
5
7
输出样例#1：
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
说明
题目翻译来自NOCOW。
USACO Training Section 1.4
分析：可以想到如果双平方数是要经常使用到的，每次计算会显得不方便，所以先把双平方数预处理出来，然后想到枚举，那么是怎样枚举呢？难道是每次枚举到一个双平方数再去找下一个平方数吗？效率太低了，可以想到题目要求a,b,那么枚举a,b即可，每次看有没有符合要求的双平方数，之前已经预处理过了，如果有n个，那么就添加到答案中.还要注意限制，双平方数不能超过2 * m * m!注意数组大小不能开太小，否则最后几个点就疯狂RE(在洛谷上是WA......)
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n, m,vis[200010],sizee,squaree[200010],ans,num;struct node{ int a, b;}s[200010];bool cmp(node x, node y){ if (x.b != y.b) return x.b < y.b; else return x.a < y.a;}int main(){ scanf("%d%d", &n, &m); for (int i = 0; i <= m; i++) for (int j = i; j <= m; j++) if (!vis[i * i + j * j]) { vis[i * i + j * j] = 1; squaree[++sizee] = i * i + j * j; } for (int i = 1; i <= sizee; i++) for (int j = 1; j <= 2 * m * m; j++) { if (squaree[i] + (n - 1) * j > 2 * m * m) break; ans = 1; for (int k = 1; ans < n; k++) if (vis[squaree[i] + k * j]) ans++; else break; if (ans == n) { num++; s[num].a = squaree[i]; s[num].b = j; } } if (num == 0) { printf("NONE\n"); return 0; } sort(s + 1, s + 1 + num, cmp); for (int i = 1; i <= num; i++) printf("%d %d\n", s[i].a, s[i].b); return 0;}
洛谷P1214 [USACO1.4]等差数列 Arithmetic Progressions