题解 P1207 【[USACO1.2]双重回文数 Dual Palindromes】

· · 题解

咱不谈什么高级算法，什么高深模拟，甚至转化进制都不需要。

并且，算法复杂度最高仅为O(n+300)

更加NB的是，main里的代码仅仅4行！

那么你可能要问我是什么代码这么NB。

答案就是：打表无敌！！！！

#include<bits/stdc++.h>
using namespace std;
int num[300]={0,1,2,3,4,5,6,7,8,9,10,15,16,
17,18,20,21,24,26,27,28,31,
33,36,40,45,46,50,51,52,55,
57,63,65,67,73,78,80,82,85,
88,91,92,93,98,99,100,104,105,107,
109,111,114,119,121,127,129,130,135,141,
142,150,151,154,160,164,170,171,173,178,
182,185,186,191,195,200,203,209,212,215,
219,227,235,242,246,252,255,257,264,273,
282,292,300,313,316,325,328,333,341,342,
343,357,364,365,373,381,393,400,414,427,
434,438,446,455,464,471,484,495,511,513,
546,555,560,564,585,624,626,644,646,651,
656,666,676,692,693,701,717,728,730,757,
771,777,787,819,820,856,868,910,939,975,
1023,1025,1066,1105,1221,1285,1312,1365,1432,1441,
1460,1539,1550,1640,1667,1755,1885,2000,2188,2268,
2293,2550,2565,2709,2730,2910,2920,2925,2997,3069,
3074,3075,3280,3315,3550,3591,3640,3663,3735,3740,
3855,3951,3999,4095,4097,4161,4225,4257,4289,4369,
4433,4593,4617,4681,5001,5049,5125,5189,5397,5461,
5740,5840,5854,6148,6200,6560,6562,6643,6697,6724,
6761,6825,6886,6889,6953,7300,7373,7381,7409,7447,
7462,7517,7667,7703,7777,7801,7997,8038,8119,8194,
8200,8258,8281,8322,8386,8578,8778,8802,9009,9103,
9201,9222,9490,9958,10252,10308,10658,10794,10858,10922,
10986,11253,11314,11757,11898,11950,12291,12355,12419,12483, 
12547,12654,12691,13107,13124,13131,13205,13286,13299,13331};
int n,s,g;
int main()
{
    cin>>n>>s;
    for(g=1;num[g]<=s;g++);
    for(int i=0;i<n;i++)cout<<num[g+i]<<endl;
    return 0;
}

你要是看这个代码还不会，算我输。

当然，你可能会问，这个表是从哪里来的？

答：我会手算！

答：我会写代码！

那么怎么写这个代码呢？

注意：下面要开始介绍打表的技巧，这些技巧可能会在比赛中用到

这些技巧仅适用于较难题以及懒得写代码。实乃骗分好法。

看题目，我们要求的是满足至少两个进制的回文数对吧。

那么我们先新开一个源码求每个进制下的回文数。

稍微思考一下，我们可以把回文数看做一个数正着输一遍，在倒着输一遍。（如果是奇数位中间的数只输1次） 那么我们的第一份源码就出来了。

我们可以用for套for套for....这个代码求每个进制下的回文数，听起来不难是吧？>.<

由于是不同进制，所以我们要加上限制条件。即每一位枚举不能大于k，k为进制数。然后我们就可以愉快的输出。（记得用freopen！）

下面展示了一个求4进制7，8位回文数的过程。当然这个代码可以运行9次。只需要把限制条件4改为2-10中的另一个数再运行就可以了。要求其他位数的回文数只需要增减for循环个数以及cout个数就可以了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    for(int a=1;a<4;a++)
        for(int b=1;b<4;b++)
            for(int c=1;c<4;c++)
                for(int d=1;d<4;d++)//你要是够莽，可以开更多for
                {
                    cout<<a<<b<<c<<d<<c<<b<<a;
                    cout<<a<<b<<c<<d<<d<<c<<b<<a;
                }   
}

当然听起来好像是很麻烦，但是做起来的效率其实蛮高了。如果你还是嫌麻烦，你可以写个递归，用改变量的方式替代改for于cout。

好了，我们得到了各个进制下的回文数。

（什么！你把数据丢了？我叫过你用freopen吧？）

我们现在需要把你得到各个进制下的回文数全部转化为10进制。

这个实现很简单吧。那就直接上代码了！

记住要加freopen！别看我没加！我懒

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;//其中,k代表进制。可以自行修改
int main()
{
    while(cin>>n)
    {
        for(int i=0;n;i++)//其中i为进制位数，为累乘服务
        {
            int tmp=n%10;//取最后一位
            else for(int j=1;j<=i;j++)tmp*=k;
            ans+=tmp;
            n/=10;//丢最后一位
        }
        cout<<ans<<" ";
    }
}

现在你得到的回文数全是10进制了。但是题目要求必须同时满足两种进制的回文数才算。

我们怎么做呢？

非常简单！你刚刚得到了9个文件对吧？他们记录了各个进制的回文数，并且全部转化为了10进制。

那么就上黑科技：Ctrl+C and Ctrl+V

简而言之，就是把所有的数据贴在一个文件里。

然后你就可以很快乐的用一个判重代码来输出那些出现次数多余2的数字。

记住要freopen！！（话说这是第几回提醒了...）

到此为止！你就得到了一个表!

是不是被我的骗分方法感动了

总结

虽说打表暴力无情，但是其实打表也有他独特的方法。如果你能在适当时间进行打表，那么你总能占到一些便宜。上面那个题不是很难，可能还没到打一个表的地步。但是我这里着重展示了打表的方法。希望对各位OIer有帮助！