题解 P1851 【好朋友】

· · 题解

你将会看到

  1. 打表对吗？

  2. 本题的打表代码

  3. 如何打表

  4. AC代码

打表对吗？

打表，是一种正常的解题方法，跟暴力、模拟、贪心、动规、搜索······并无二异，既然不会其他写法，或者是其他写法太烦，那么——打表是我们光荣的选择（虽然用的不太多）

打表，指将题目中所要求的值自行算出，存到数组中，
输入后经过判断直接输出数组中的值，时间复杂度为O(1)。 
方便快捷而又简单高效，是OI中的不二之选。                  

                            ——frank·chee（沃兹·基朔德）

打表代码：

#include<iostream>
using namespace std;
int s,a[100007];//这里取的10 0000，可以取更大
//但即使对于打表来说，时间也够长的了
int main()
{
    for(int i=1;i<=100000;i++)
    {
        for(int j=1;j<=i;j++)
        if(i%j==0)//判断j是i的余数
        if(i!=j)//由题可得（仿佛是道数学题），约数没有本身
        a[i]+=j;//其约数和加上j
    }
    for(int i=1;i<=100000;i++)
    for(int j=1;j<=100000;j++)//双重循环判断
    if(a[i]==j&&a[j]==i&&i>=6&&i>j&&j>=6)cout<<i<<' '<<j<<endl;
        //i的约数和等于j，j的约数和等于i，两者都大于6
        //这里为了方便起见是i大于j
    return 0;
}

如何打表：

耐心等待······后 你会看见这个

这就是10 0000 以内所有的满足条件的数了

然后把代码删掉，开两个数组，分别存前一列和后一列

输入，判断，输出，就行了！

另：关于打表的用时

配置：Intel(R) Celeron(R) 2957u @ 1.40GHz 1.40GHz

RAM(没加装其他的)：4.00GB

系统类型：64位

本人测试，跑完用时97.485s，有图为证。而且运行时我还在耗资源，所以按照当今主流电脑，(i3及以上，6GB及以上)，60s内不成问题

AC代码：

#include<iostream>
using namespace std;
int a[17]={284,1210,2924,5564,6386,10856,14595,18416,66992,71145,76084,87633,88730};
int b[17]={220,1184,2620,5020,6232,10744,12285,17296,66928,67095,63020,69615,79750};
int s;
int main()
{
    cin>>s;
    for(int i=0;i<=15;i++)
    {
        if(b[i]>=s){cout<<b[i]<<' '<<a[i];return 0;}
            //小数大于s，输出小数，再大数
        if(a[i]>=s){cout<<a[i]<<' '<<b[i];return 0;}
            //大数大于s，输出大数，再小数
    }

    return 0;
}

写得真的很辛苦，不点个赞再走吗？

题外话：入门难度是这种题目？洛谷人果然都是神犇啊，本蒟蒻还要努力学习啊（无讽刺意）