糾結了很久.....原來是犯了SB錯誤.....ZMJ大牛眼光果然犀利....
Dscrption：http://acm.hdu.edu.cn/vip/contest_showproblem.php?pid=1007&cid=289
Method：
先做預處理，然后O（1）輸出答案..............
其實可以看出來年份的最高4為何月日一定是對稱的。。如果年份大于四位，那么除去高四位剩下的數字一定是對稱的。。
所以可以先枚舉所有月和日的情況（同時就可以可以確定年份的最高4位，然后枚舉依次枚舉插入1為數，兩位數的回文數）....
我的解法：
先考慮年份為四位數的情況，枚舉月和日的情況...然后按年份排序
然后就再從中間插入一位數，兩位數，三位數，枚舉每種情況的回文數。。
同時還要注意處理閏年（即2月29號）的情況，當枚舉到2。29的時候還要判斷是否為閏年.....................
再將結果存到res[]中.............
表達能力有限.....ms不是說的很清楚啊......只能這樣了.......
CODE:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef __int64 I;
struct st
{
int year;
int mmdd;
}q[400];
int top,n,num;
int res[4000005];
bool even[4000005];
int mouth[14]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int cmp(const st &a,const st &b)
{
return a.year<b.year;
}
void f()
{
int i,j;
top=0;
for(i=1;i<=12;i++)
for(j=1;j<=mouth[i];j++)
{
q[top].mmdd=100*i+j;
int tmp=q[top].mmdd;
q[top].year=0;
for(int k=0;k<4;k++)
{
q[top].year=q[top].year*10+tmp%10;
tmp/=10;
}
if(q[top].year>=1000)
top++;
}
sort(q,q+top,cmp);
}
bool check(I x)
{
return x%400==0||(x%4==0&&x%100!=0);
}
I mirror(int d, int t)
{
I ret = t;
if(d & 1) {t /= 10;d--;}
for(int i = 0; i < d; i++)
{
ret = ret*10 + t%10;
t/=10;
}
return ret;
}
void init()
{
int d=0,len,i,j,k;
num=top+1;
while(true)
{
++d;
len=d/2;
if(d&1) len++;
I sum=1, L=1;
for(i=0;i<len;i++)
sum*=10;
for(i=0;i<d;i++)
L*=10;
for(j=0;j<top;j++)
for(i=0;i<sum;i++)
{
I ans=mirror(len,i);
if(q[j].year==9220 && !check(9220*L+ans))
continue;
res[num]=q[j].year*sum+i;
if(d & 1) even[num] = false;
else even[num]=true;
num++;
if(num>4000000)
return ;
}
}
}
int main()
{
int i,j,k,m;
int ncase;
f();
init();
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d",&k);
if(k<=top)
printf("%d\n",q[k-1].year*10000 + q[k-1].mmdd);
else
{
int t = res[k];
printf("%d", t);
if(!even[k]) t/=10;
while(t)
{
printf("%d", t%10);
t /= 10;
}
printf("\n");
}
}
return 0;
}
閱讀全文
類別：默認分類 查看評論文章來源:
http://hi.baidu.com/%D2%EC%B6%C8%BF%D5%BC%E4%5F%B5%DA%CB%C4%CE%AC/blog/item/992799348ac0f73d0a55a98e.html
posted on 2010-05-01 23:34
ccyy 閱讀(138)
評論(0) 編輯 收藏 引用