ccyy's coding zone
往前走,不要留恋路边的风景.
posts - 25,comments - 9,trackbacks - 0
纠结了很久.....原来是犯了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:

C++语言: HDU 3403
#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 阅读(133) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理