Changing Digits（dfs）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Changing Digits（dfs），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2714字，纯文字阅读大概需要4分钟。
内容图文
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
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, k≤n) for each line. Both n and k will not contain leading zeros.
Output one line for each test case containing the desired number m.
【题意】
给出n和k，求一个数m，m是满足所有以下4个条件的数：（1）与n位数相同 （2）能被k整除（3）与n相同位的数不相同最少（4）满足以上3个条件的最小值。其中 1≤n≤10100 ， 1≤k≤104, k≤n
***************************************************************************************************************************
1 #inc;ude<iostream>
2 #include<cstdio>
3 #include<cstring>
4usingnamespace std;
5int mod[110][10],test[110],nu[110],f[110][12000];
6char str[110];
7int k,len;
8void init()
9{
10int i,j;
11for(i=0;i<10;i++)mod[0][i]=i%k;
12for(i=1;i<len;i++)
13 {
14for(j=0;j<10;j++)
15 {
16 mod[i][j]=(mod[i-1][j]*10)%k;
17 }
18 }
19 memset(f,0,sizeof(f));
20}
21bool DFS(int pos,int num,int m )
22{
2324int i,j;
25if(m==0)
26 {
27for(i=len-1;i>=0;i--)printf("%d",test[i]);
28 printf("\n");
29returntrue;
30 }
31if(pos<0||num<=f[pos][m]||num==0)returnfalse;
32for(i=pos;i>=0;i--)
33 {
34for(j=0;j<nu[i];j++)//从后想前求小值35 {
36if(i==len-1&&j==0)continue;
37 test[i]=j;
38int a=(m-(mod[i][nu[i]]-mod[i][j])+k)%k;
3940if(DFS(i-1,num-1,a))returntrue;
4142 }
43 test[i]=nu[i];
44 }
45for(i=0;i<=pos;i++)//从尾向高位求小值46 {
47for(j=nu[i]+1;j<10;j++)
48 {
49if(i==len-1&&j==0)continue;
50 test[i]=j;
51int a=(m+(mod[i][j]-mod[i][nu[i]]))%k;
52if(DFS(i-1,num-1,a))returntrue;
5354 }
55 test[i]=nu[i];
56 }
57 f[pos][m]=num;//记录改变后的值58returnfalse;
5960}
61void solve()
62{
63int i;
64int m=0;
65for(i=0;i<len;i++)
66 {
67 test[i]=nu[i]=str[len-i-1]-‘0‘;
68 m+=mod[i][nu[i]];
69 m%=k;
70 }
71for(i=1;i<=len;i++)
72 {
73if(DFS(len-1,i,m))return;
74 }
75}
76int main()
77{
78while(scanf("%s",str)!=EOF)
79 {
80 scanf("%d",&k);
81 len=strlen(str);
82 init();
83 solve();
84 }
85 }
原文：http://www.cnblogs.com/sdau--codeants/p/3536504.html
内容总结
以上是互联网集市为您收集整理的Changing Digits（dfs）全部内容，希望文章能够帮你解决Changing Digits（dfs）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。