首页 > 专题系列 > Java解POJ > POJ 3373 Changing Digits [解题报告] Java
2013
11-12

POJ 3373 Changing Digits [解题报告] Java

Changing Digits

问题描述 :

Given two positive integers n and k, you are asked to generate a new integer, say m, by changing some (maybe none) digits of n, such that the following properties holds:

  1. m contains no leading zeros and has the same length as n (We consider zero itself a one-digit integer without leading zeros.)
  2. m is divisible by k
  3. among all numbers satisfying properties 1 and 2, m would be the one with least number of digits different from n
  4. among all numbers satisfying properties 1, 2 and 3, m would be the smallest one

输入:

There are multiple test cases for the input. Each test case consists of two lines, which contains n(1≤n≤10100) and k(1≤k≤104, kn) for each line. Both n and k will not contain leading zeros.

输出:

Output one line for each test case containing the desired number m.

样例输入:

2
2
619103
3219

样例输出:

2
119103

解题代码:

import java.util.Scanner;  
      
    public class Main{  
      
        static int mod[][];  
        static int k;  
        static int flag[][];  
        static int m[],n[];  
        static int n_mod;  
        static int len;  
          
        public static void main(String[] args) {  
              
            Scanner scan = new Scanner(System.in);  
              
            while(scan.hasNext()){  
                char s[] = scan.next().toCharArray();  
                k = scan.nextInt();  
                  
                len = s.length;  
                mod = new int[len][10];  
                flag = new int[len][k];  
                m = new int[len];  
                n = new int[len];  
                n_mod = 0;  
                  
                playTable(len);  
                  
                for(int i=0;i< len;i++){  
                    m[i] = n[i] = s[len-i-1]-'0';  
                    n_mod = (n_mod+mod[i][n[i]])%k;  
                }  
                  
                int i;  
                for(i=1;i<=len;i++)          // 修改的长度  
                    if(dfs(len-1,i,n_mod))  
                        break;  
                  
                for(i=len-1;i>=0;i--)  
                    System.out.print(""+m[i]);  
                System.out.println();  
                  
            }  
        }  
      
        public static boolean dfs(int pos, int clen, int m_mod) {  
              
            if(m_mod == 0)  
                return true;  
            if(pos< 0||clen==0)  
                return false;  
              
            if(clen<=flag[pos][m_mod])          //剪枝  
                return false;  
              
            for(int i=pos;i>=0;i--){  
                for(int j=0;j< n[i];j++){  
                    if(i==len-1&&j==0)  
                        continue;  
                    int res = (m_mod-mod[i][m[i]]+mod[i][j]+k)%k;  // 同余模  
                    int temp = m[i];  
                    m[i] = j;  
                      
                    if(dfs(i-1,clen-1,res)){  
                        return true;  
                    }  
                    m[i] = temp;  
                }  
            }  
            for(int i=0;i<=pos;i++){  
                for(int j=n[i]+1;j<=9;j++){  
                    int res = (m_mod-mod[i][m[i]]+mod[i][j]+k)%k;  
                    int temp = m[i];  
                    m[i] = j;  
                    if(dfs(i-1,clen-1,res))  
                        return true;  
                    m[i] = temp;  
                }  
            }  
            flag[pos][m_mod] = clen;              // 剪枝  
              
            return false;  
        }  
      
        public static void playTable(int len) {  
              
            for(int i=0;i< 10;i++)  
                mod[0][i] = i%k;  
            for(int i=1;i< len;i++){  
                for(int j=0;j< 10;j++)  
                    mod[i][j] = (mod[i-1][j]*10)%k;  
            }  
              
        }  
      
    }

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的