题意：给了一串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