PROB Arithmetic Progressions

实践证明:剪枝是很能节约时间的!!!!!!!!

神哇~~~~~~~~~~~

(1)在判断 a+ i*b时候直接break内层循环,就一下次通过了test7 但是悲剧的是还是通不过test 8

(2)实在没辙了,只要看别人的答案,结果竟然是在判断是否符合条件的时候从后向前查看,也就将循环从是a到 a+(n-1)b从改为a + (n -1)b到a。结果竟然通过了!!!

网上的资料说这样子看的话,是因为后面的数据比较稀疏(为什么?还是不懂)

 

总而言之,题目不是很难,但是时间限制很给力,很折腾~

代码如下:

/*
ID: foryjus1
PROG: ariprog
LANG: C++
*/
//超时………………………………………………
#include <iostream>
#include <fstream>
using namespace std;

#define MAXMAP (2 * 251 * 251)

bool map[MAXMAP] = {false};//考虑取0的情况,建立映射表,用于n判断是否是p^2+q^2

int main()
{
    ifstream fin("ariprog.in");
    ofstream fout("ariprog.out");
    int n, m;//n:等差数列长度;m:p、q的最大值
    fin >> n >> m;

    //初始化map
    for(int i = 0; i <= m; ++i)
    {
        for(int j = 0; j <= i; ++j)
        {
            map[ (i * i) + (j * j) ] = true;
        }
    }
    int bound = m*m + m*m;//a + nb最大值
    int maxb = (m*m + m*m) / (n - 1);//等差数列可能的最大的差
    bool flag = true;
    bool fgnone = true;//结果集合是否为空
    int temp;//用于存放临时值
    int abound;//a的边界
    for(int b = 1; b <= maxb; ++b)
    {
        abound = bound - ( n - 1 ) * b;//计算a的最大值
        for(int a = 0; a <= abound; ++a)
        {
            flag = true;
            //连续n个等差数列值           
            //for(int i = 0; i < n; ++i)
            //从后面开始查看
            for(int i = n - 1; i >= 0; --i)
            {
                temp = a + i * b;
                if(!map[temp])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
            {
                //显示结果
                fgnone = false;
                fout << a << ' ' << b << endl;
            }
        }
    }
    //结果集为空,输出NONE
    if(fgnone)
    {
        fout << "NONE" << endl;
    }
    return 0;
}

原文链接: https://www.cnblogs.com/growup/archive/2011/03/20/1989665.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    PROB Arithmetic Progressions

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/22575

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月8日 上午12:33
下一篇 2023年2月8日 上午12:34

相关推荐