题解 | #[NOIP1999]回文数#

public class Program {
    public static void Main() {
        /*
        1.难点是在于进行一次N进制的加法,这里我们不用转成十进制加完后再转回来
        2.不管题目输入的是几进制,我们都先转为数字存进数组里,然后把数组翻转,两个数组对应的位数相加
        3.相加后判断是否有进位,有进位就进位,然后取余数
        4.由于进制数M在100位以内,因此数组要考虑溢出的情况
        5.这里用数组而不用字符串的原因是假如输入的是十六进制,以字母A为例,字母A对应的数是10
        我们要把这个10存起来,如果用字符串再转成字符数组就会把10拆分成1和0,这样加起来的结果就不对

        示例1:N = 9,M = 87
        int [10000000]a = {8,7,0...0};
        int [10000000]b = {7,8,0...0};
        循环过程:
        a[1] + = b[1] = 15;   用15除以进制N判断是否有进位
        a[2] + = a[1] / N;       结果为1,即进位1
        a[1] % = N;           进位后原来的数取余数
        第一轮循环过后得出来的数为 671 step = 1;
        第二轮循环过后得出来的数为 758 step = 2
        第三轮循环过后得出来的数为 6271 step = 3;
        第四轮循环过后得出来的数为 7018 step = 4;
        第五轮循环过后得出来的数为 62161 step = 5;
        第六轮循环过后得出来的数为 78287 step = 6;
        */

        int N = int.Parse(System.Console.ReadLine());

        char[] M = System.Console.ReadLine().ToCharArray();
        int[] copy_M = new int[1000000];

        //有效数组长度,比如6710,则有效长度为4,下面循环时不用循环完整个数组长度
        int Len = M.Length;
        int copy_Len = Len;

        //把输入的字符转成数字存进数组
        for (int i = 0; i < M.Length; i++) {
            //如果是数字
            if (M[i] >= '0' && M[i] <= '9')
                copy_M[i] = M[i] - '0';
            //如果是字母
            else
                copy_M[i] = M[i] - 'A' + 10;
        }

        int STEP = 0;
        while (STEP < 30) {
            copy_Len = Len;
            //翻转数组copy_M
            int[] R_copy_M = new int[1000000];
            int tail = copy_Len - 1;
            for (int start = 0; start < copy_Len; start++) {
                R_copy_M[start] = copy_M[tail];
                tail--;
            }

            //翻转后将两个数组的对应位数相加
            Len = 0;
            int i;
            for ( i = 0; i < copy_Len; i++) {
                copy_M[i] += R_copy_M[i];
                //有进位就进位
                copy_M[i + 1] += copy_M[i] / N;
                //取余数
                copy_M[i] %= N;
                //记录有效长度
                Len += 1;
            }
            //循环完判断i位置是否为0,不为0说明进位了,则有效长度加1
            if (copy_M[i] != 0) {
                Len += 1;
            }
            STEP++;

            //判断是否为回文数
            int tail_Len = Len - 1;
            bool isNum = true;
            for (int j = 0; j < Len; j++) {
                if (copy_M[j] != copy_M[tail_Len]) {
                    isNum = false;
                    break;
                }
                if (tail_Len < Len / 2)
                    break;
                tail_Len--;
            }
            //是回文数退出循环
            if (isNum)
                break;
        }
        if (STEP < 30)
            System.Console.WriteLine("STEP=" + STEP);
        else
            System.Console.WriteLine("Impossible!");
    }
}