poj 3373 Changing Digits

Description

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:

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

Input

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

Output

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

Sample Input

Sample Output

2
119103

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <string>
  5 using namespace std;
  6 char str[101];
  7 int num1[101],num2[101];
  8 int flag[101][10005];
  9 int k;
 10 int len;
 11 int getY(int num[])
 12 {
 13     int j;
 14     int m=0;
 15     for(j=len-1;j>=0;j--)
 16     {
 17         m=(m*10+num[j])%k;
 18     }
 19     return m;
 20 }
 21 
 22 void init()
 23 {
 24     int i;
 25     for(i=0;i<len;i++)
 26     {
 27         num1[i] = num2[i] = str[len-1-i]-'0';
 28     }
 29     memset(flag,0,sizeof(flag));
 30 }
 31 bool dfs(int pos,int num,int m)
 32 {
 33     int i,j;
 34     if(m==0)
 35     {
 36         for(i=len-1;i>=0;i--)printf("%d",num1[i]);
 37         printf("
");
 38         return true;
 39     }
 40 
 41     if(pos<0 || num<=flag[pos][m] || num==0)
 42     {
 43         return false;
 44     }
 45     for(i=pos;i>=0;i--)
 46     {
 47         for(j=0;j<num2[i];j++)
 48         {
 49             if(i==len-1 && j==0)
 50             {
 51                 continue;//±ÜÃâÇ°µ¼0;
 52             }
 53             num1[i]=j;
 54             int a=getY(num1);
 55             if(dfs(i-1,num-1,a))
 56             {
 57                 return true;
 58             }
 59         }
 60         num1[i]=num2[i];
 61     }
 62     for(i=0;i<=pos;i++)
 63     {
 64         for(j=num2[i]+1;j<=9;j++)
 65         {
 66             if(j==0 && i==len-1)
 67             {
 68                 continue;
 69             }
 70             num1[i]=j;
 71             int a=getY(num1);
 72             if(dfs(i-1,num-1,a))
 73             {
 74                 return true;
 75             }
 76         }
 77         num1[i]=num2[i];
 78     }
 79     flag[pos][m]=num;
 80     return false;
 81 }
 82 void solve()
 83 {
 84     int i;
 85     int m=getY(num1);
 86     for(i=1;i<=5;i++)
 87     {
 88         if(dfs(len-1,i,m))return;
 89     }
 90 }
 91 int main()
 92 {
 93     while(~scanf("%s%d",str,&k))
 94     {
 95         len = strlen(str);
 96         init();
 97         solve();
 98 
 99     }
100 }

View Code

此题属于记忆化深搜，再加点技巧。

题目大意：

给出2个整数n（n<10^100）和k（k<10000），求满足以下条件的整数m

1、m与n位数相同
2、m能被k整除
3、满足以上两点时，m和n在相同位置的地方，数字不同的个数最少

4、满足以上三点时，m值最小

解题步骤：
一、解决条件1很简单；
二、判断能否被k整除，使用同余模公式，解决大数能否被整除问题；
三、尽可能改变少的数字来满足条件

bool DFS(int pos,int num,int m);

传参有3个：pos，num，m

pos：当前搜索区间为[0,pos]

num：在区间[0,pos]中剩余允许改变的数字的个数，个数从1个到len(n)个枚举，保证搜索到解时，n与m在相同位置处不同数字的个数是最少的（条件3）。

m：当前数字串m对k求模的值，初始化为a。

（1）搜索时先搜索比n小的数字，此时为了搜索到的解m是最小的，应该从区间[0,pos]的第pos位开始向第0位搜索，因为在相同num情况下，把高位数字变小所得到的m值更小。

（2）当（1）无解时，搜索比n大的数字，此时为了搜索到的解m是最小的，应该从区间[0,pos]的第0位开始向第pos位搜索，因为在相同num情况下，把低位数字变大所得到的m值更小。



具体看代码。