好久没做POJ了。依然跟随POJ题目分类表，这题属于”记忆化搜索”。
貌似是要求高精度，但稍微分析下便知道，由于k<=10,000，那么n最多改变4位数字便一定能被k整除的，因此这里还是使用int除法，递归修改n的每位数字时顺便求出当前模值即可。 搜索的思路很容易出，由条件3和4，易得到搜索的方向：（1）由改变较少位数开始；（2）从高位开始。但是剪枝还是稍微想了一下。最后发现，根据dfs的传入参数，若该次dfs失败，可以用数组标记该参数组合无法满足题意。后续的搜索中，每次根据参数检查数组中对应位置是否已有标记，若是则直接返回0。其实不算难的一题，做的人却不多。另外，也开始习惯用vim敲程序了，开着fedora，窗口A左面vim，右面terminal（编译+运行），窗口B开着chrome读题，很是顺手哈哈。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<stdio.h> #include<string.h> int nl,K,b[102][5][10000]; char n[102]; int dfs(int i,int m,int mod) { int j,k,l; char c,cc; if(i==nl) { if(!mod) { puts(n); return 1; } else return 0; } if(b[i][m][mod]) return 0; if(!m) { k=mod*10+n[i]-'0'; if(k>=K) k%=K; j=dfs(i+1,m,k); if(j) return 1; else { b[i+1][m][k]=1; return 0; } } if(i) { c='0'; cc=n[i]; n[i]=c; k=mod*10+n[i]-'0'; if(k>=K) k%=K; if(c==cc) j=dfs(i+1,m,k); else j=dfs(i+1,m-1,k); if(j) return 1; n[i]=cc; } for(c='1';c<='9';c++) { cc=n[i]; n[i]=c; k=mod*10+n[i]-'0'; if(k>=K) k%=K; if(c==cc) j=dfs(i+1,m,k); else j=dfs(i+1,m-1,k); if(j) return 1; n[i]=cc; } b[i][m][mod]=1; return 0; } int main() { int i,j; while(~scanf("%s%d",n,&K)) { nl=strlen(n); memset(b,0,sizeof b); if(nl==1) { if(n[0]=='0'+K) puts(n); else puts("0"); continue; } for(i=j=0;i<=nl&&!j;i++) j=dfs(0,i,0); } return 0; } |
这段时间有点迷茫，不知道接下来学什么好，能够交流的人也好少。 又买了Effective C++和APUE，还是希望能把C++和Linux学得扎实一点。
今天也去了下阿里巴巴组织的大学生课堂，好久没听过课了，加上坐得比较远，实际没听到多少内容。倒是见识到好多牛人，都能各种和讲师交流了。就目前自己了解到的信息，还是很想去阿里的，但现在还不太够格。
亲爱的妈妈，不是我不想追女生，只是现在只能一心追时间啊。