[模拟]ZOJ3485Identification Number

题意：给了一串15位或18位的身份证号码，求 在改变最少位数的情况下， 输出正确合法的身份证号

合法的身份证 是按照以下规则：

前6位以及“Order code”三位  一定合法

其中X是根据前17位的值计算出来的 按照如下公式  (a1就是最后一位，若为10就是X)

另外 题目还规定了“Date of Birth” 要在1900.1.1到2011.4.2之间

刚开始想这题的时候，觉得15位也就只需要 改变 年月日6位

　　　　　　　　　　　　18位也就只需要 改变 年月日加X位9位而已

但是打起来发现并非这么简单。。。

单单是改变年月日就还需要考虑每月有多少天、需要考虑是否为闰年、需要考虑是否超过1900.1.1到2011.4.2的范围...

对于18位的，改变了前面 还有影响到X的

这样打下来相当之麻烦... 而且很容易错

因此不能采用这种方法

我们来换一种思路：

假设， 我们已经知道了  “在改变最少位数之后的身份证号码”  那么来计算与输入的有几位不一样，那是一件很方便的事

那么如何来得到 “在改变最少位数之后的身份证号码” 呢？

我们只需要遍历1900.1.1到2011.4.1之间的每一天 (这样想之后， 发现给了一个范围真好啊！！)

比较每一天与输入的需要改变几位，记录最小的 改变的位数 的那一天就好了

 string s;

 int run[][]={{, , , , , , , , , , , },

                 {, , , , , , , , , , , }};

 int w[]={, , , , , , , , , , , , , , , , , };

 int a[], b[];

 int ans[];

 void copy(int y, int m, int d)

 {

     for(int i=; i<s.length(); i++)

         b[i]=a[i];

     if(s.length()==)

     {

         b[]=y%/, b[]=y%%;

         b[]=m/, b[]=m%;

         b[]=d/, b[]=d%;

     }

     else

     {

         b[]=y/, b[]=y/%, b[]=y%/, b[]=y%%;

         b[]=m/, b[]=m%;

         b[]=d/, b[]=d%;

     }

 }

 int y, m, d;

 bool cao()

 {

     if(y== && m== && d==)

         return true;

     int Y=y, M=m, D=d+;

     if(run[((Y%== && Y%) || Y%==)][M-]+==D)

         M++, D=;

     if(M==)

         Y++, M=;

     copy(Y, M, D);

     y=Y, m=M, d=D;

     return false;

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t--)

     {

         cin>>s;

         for(int i=;i<s.length();i++)

             a[i]=(s[i]=='X'? :s[i]-'');

         y=, m=, d=;

         int minn=;

         copy(y, m, d);

         while(true)

         {

             int num=;

             if(s.length()==)

             {

                 int sum=;

                 for(int i=; i<; i++)

                     sum+=b[i]*w[i];

                 b[]=(-sum%)%;

             }

             for(int i=; i<s.length(); i++)

                 if(b[i]!=a[i])

                     num++;

             if(num<minn)

             {

                 for(int i=; i<s.length(); i++)

                     ans[i]=b[i];

                 minn=num;

             }

             if(cao())

                 break;

         }

         for(int i=; i<s.length(); i++)

         {

             if(ans[i]!=)

                 printf("%d", ans[i]);

             else

                 putchar('X');

         }

         puts("");

     }

     return ;

 }

ZOJ 3485