首页 > ACM题库 > HDU-杭电 > HDU 3403-Palindrome day-枚举-[解题报告]HOJ
2014
03-23

HDU 3403-Palindrome day-枚举-[解题报告]HOJ

Palindrome day

问题描述 :

A palindrome integer is a number that we can get the same value when read from left to right or from right to left. For example, 1221,20100102.
We can define a palindrome day as follow: its standard form is a palindrome integer, and, it must be a valid day. 20100102 is OK, but 23200232 is not for it is not a valid day.
Which day is the Kth palindrome day from 10000101?

输入:

The first line is an integer T indicating the case number.
For each case, there is an integer K(1<=K<=4000000).

输出:

The first line is an integer T indicating the case number.
For each case, there is an integer K(1<=K<=4000000).

样例输入:

2
1
45

样例输出:

10011001
20100102


PS :注意溢出问题,整型强制转换为64位的
会出错 C语言中没有bool
#include <stdio.h>
#include <math.h>
int a[4000001];
bool flag[4000001];
inline bool leapyear(int year)
//判断某年是否闰年闰年返回1,平年返回0
{
   return
year%400==0||(year%4==0&&year%100!=0);
}
int main()
{
    int
i,j,k,h,e,f,tmp;
    int
count=0;
    bool
flag1=true;
for(i=1;i<=9;i++)
    {
for(j=0;j<=3;j++)
{
tmp=i*10+j;
if(i==1&&tmp==13)
{
count++;
a[count]=1301;flag[count]=0;
count++;
a[count]=1310;flag[count]=0;
count++;
a[count]=1321;flag[count]=0;
count++;
a[count]=1330;flag[count]=0;
count++;
a[count]=1350;flag[count]=0;
count++;
a[count]=1370;flag[count]=0;
count++;
a[count]=1380;flag[count]=0;
}
if(j<3)
{
int t=tmp/10;
int s=tmp%10;
t=s*10+t;
count++;
a[count]=tmp*100+1;flag[count]=0;
count++;
a[count]=tmp*100+10;flag[count]=0;
count++;
a[count]=tmp*100+11;flag[count]=0;
if(t<=28)
{
count++;               
a[count]=tmp*100+20;flag[count]=0;
}
if(flag1&&tmp==92)
{
flag1=false;
count++;
a[count]=9220;flag[count]=0;
}
count++;
a[count]=tmp*100+21;flag[count]=0;
count++;
a[count]=tmp*100+30;flag[count]=0;
count++;
a[count]=tmp*100+40;flag[count]=0;
count++;
a[count]=tmp*100+50;flag[count]=0;
count++;
a[count]=tmp*100+60;flag[count]=0;
count++;
a[count]=tmp*100+70;flag[count]=0;
count++;
a[count]=tmp*100+80;flag[count]=0;
count++;
a[count]=tmp*100+90;flag[count]=0;
}
}
    }
    int
m=count;
for(i=1;i<=7;i++)
{
for(h=1;h<=m;h++)
{                           
if(i==1)
{                   
for(k=0;k<=9;k++)       
{   
if(a[h]==9220)                           
{
if(leapyear(a[h]*10+k))
{                                                   
count++;                       
a[count]=a[h]*10+k;flag[count]=1;
}
}
else
{
count++;                       
a[count]=a[h]*10+k;flag[count]=1;
}
}
}
else if(i==2){
for(k=0;k<=9;k++)       
{   
if(a[h]==9220)                           
{
if(leapyear(a[h]*100+k*10+k))
{
count++;                       
a[count]=a[h]*10+k;flag[count]=0;
}
}
else
{
count++;                       
a[count]=a[h]*10+k;flag[count]=0;
}
}
}
else if(i==3)
{
for(k=0;k<=9;k++)       
{   
for(j=0;j<=9;j++)
{
if(a[h]==9220)                           
{
if(leapyear(a[h]*1000+k*100+j*10+k))
{
count++;                       
a[count]=a[h]*100+k*10+j;flag[count]=1;
}
}
else
{
count++;                       
a[count]=a[h]*100+k*10+j;flag[count]=1;
}
}
}
}
else if(i==4)
{
for(k=0;k<=9;k++)
for(j=0;j<=9;j++)
{
if(a[h]==9220)
{
if(leapyear(a[h]*10000+k*1000+j*100+j*10+k))
{
count++;
a[count]=a[h]*100+k*10+j;flag[count]=0;
}                               
}
else
{
count++;
a[count]=a[h]*100+k*10+j;flag[count]=0;
}
}
}
else if(i==5)
{
for(k=0;k<=9;k++)
for(j=0;j<=9;j++)
for(e=0;e<=9;e++)
{
if(a[h]==9220)
{
if(leapyear(k*10000+j*1000+e*100+j*10+k))
{
count++;
a[count]=a[h]*1000+k*100+j*10+e;flag[count]=1;
}
}
else
{
count++;
a[count]=a[h]*1000+k*100+j*10+e;flag[count]=1;
}
}
}
else if(i==6)
{
for(k=0;k<=9;k++)
for(j=0;j<=9;j++)
for(e=0;e<=9;e++)
{
if(a[h]==9220)
{       
if(leapyear(k*100000+j*10000+e*1000+e*100+j*10+k))
{
count++;
a[count]=a[h]*1000+k*100+j*10+e;flag[count]=0;
}
}
else
{
count++;
a[count]=a[h]*1000+k*100+j*10+e;flag[count]=0;
}
}
}
else if(i==7)
{
for( k=0;k<=9;k++)
for(j=0;j<=9;j++)
for(e=0;e<=9;e++)
for( f=0;f<=9;f++)
{
if(a[h]==9220)
{   
if(leapyear(k*1000000+j*100000+e*10000+f*1000+e*100+j*10+k))
{
count++;if(count>4000000)goto loop1;
a[count]=a[h]*10000+k*1000+j*100+e*10+f;flag[count]=1;
}
}
else
{
count++;if(count>4000000)goto loop2;
a[count]=a[h]*10000+k*1000+j*100+e*10+f;flag[count]=1;
}
}
}
}
    }
loop1:;
loop2:;   
    int t;
scanf(“%d”,&t);
    while
(t–)
    {
scanf(“%d”,&k);
{
printf(“%d”,a[k]);
if(flag[k]==0){
tmp=a[k];
for(i=1;tmp!=0;i++)
{
printf(“%d”,tmp%10);
tmp/=10;
}
printf(“\n”);
}
else
{
tmp=a[k]/10;
for(i=1;tmp!=0;i++)
{
printf(“%d”,tmp%10);
tmp/=10;
}
printf(“\n”);
}
}
    }
    return
0;
}
参考:http://blog.sina.com.cn/s/blog_61d8e41201013lkr.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3