M_sea

洛谷1214 等差数列Arithmetic Progressions
Luogu算法这题不需要很高端的知识,枚举即可。但是普通的枚举会超时,所以要加上一个剪枝:最后一个数超出上限就br...
扫描右侧二维码阅读全文
30
2017/09

洛谷1214 等差数列Arithmetic Progressions

Luogu

算法

这题不需要很高端的知识,枚举即可。
但是普通的枚举会超时,所以要加上一个剪枝:最后一个数超出上限就break。
而且要从大到小枚举。

枚举等差数列的后两项,然后计算出公差,然后减到第一项。
答案即第一项(减的剩余值)和公差。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
bool f[200010];
int a[200010];
inline bool cmp(const int& x,const int& y) { return x>y; } //从大到小排序
struct stAns //答案
{
    int a,b;
    bool operator < (const stAns& x) const { //重载<
        return (b<x.b)||((b==x.b)&&(a<x.a));
    }
}ans[10010];
int main()
{
    int n,m,num=0,ansnum=0; scanf("%d%d",&n,&m); //输入
    for (re int i=0;i<=m;i++)
        for (re int j=0;j<=m;j++) { //计算双平方数,从0开始
            int now=i*i+j*j;
            if (!f[now]) { num++; a[num]=now; f[now]=true; } //记得判是否出现
        }
    sort(a+1,a+num+1,cmp); //排序
    for (re int i=1;i<=num-n+1;i++) //最后一项
        for (re int j=i+1;j<=num-n+2;j++) { //倒数第二项
            int p=a[i]-a[j],find_ans=true,t=a[j]; //公差、有答案的标记、当前项
            if (a[j]-(n-2)*p<0) break; //剪枝
            for (re int k=1;k<=n-2;k++) { //循环n-2次,计算前面
                t-=p; //算出前一项
                if (t<0) { find_ans=false; break; } //<0,不成立
                if (f[t]==0) { find_ans=false; break; } //不是双平方数,不成立
            }
            if (find_ans) { //有答案就存
                ansnum++;
                ans[ansnum].a=t;
                ans[ansnum].b=p;
            }
        }
    if (ansnum==0) printf("NONE\n"); //无答案就输出"NONE"
    else {
        sort(ans+1,ans+ansnum+1); //排序答案
        for (re int i=1;i<=ansnum;i++) printf("%d %d\n",ans[i].a,ans[i].b); //输出
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 13 PM

发表评论