首页 > 代码库 > (UVA)11361 - Investigating Div-Sum Property
(UVA)11361 - Investigating Div-Sum Property
(UVA)11361 - Investigating Div-Sum Property
思路：记忆化搜索；
因为所有位置上的数字加起来和不会超过99的，所以k的有效值<100，所以当k>=100时,答案为0，
然后dp[i][j][k][s],表示在状i下，前j位上数表示的数对mod取模为k，前j位各个数的和对mod取模为s下的方案数。
i的状态一共只有两种，如果i为0则表示当前j-1位就为原数的前j-1为，那么当前位分两种情况，如果选原来的，那么i值不变就为0，如果选比原来小的，那么i在下一层变为1，那么剩下的所有位置上的数就可以选0--9的所有状态了，具体转移看代码。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<queue> 6 #include<string.h> 7 using namespace std; 8 typedef long long LL; 9 int dp[2][12][105][105];10 int ans[15];11 int N[10];12 int slove(int n,int k);13 int dfs(int pos,int flag,int k,int sum,int mod);14 int t = 0;15 int main(void)16 {17 int T;18 scanf("%d",&T);19 int A,B,K;20 N[0] = 1;21 int i ;22 N[1] = 10;23 for(i = 2; i <= 9; i++)24 {25 N[i] = N[i-1]*10;26 }27 while(T--)28 {29 scanf("%d %d %d",&A,&B,&K);30 memset(dp,0,sizeof(dp));31 if(K >= 100)32 {33 printf("0\n");34 }35 else36 {37 printf("%d\n",slove(B,K)-slove(A-1,K));38 }39 }40 return 0;41 }42 int slove(int n,int k)43 {44 int cn = 0;45 while(n)46 {47 ans[++cn] = n%10;48 n /= 10;49 }50 t = 0;51 memset(dp,-1,sizeof(dp));52 return dfs(cn,0,0,0,k);53 }54 int dfs(int pos,int flag,int k,int sum,int mod)55 {56 if(pos == 0)57 {58 if(sum== 0&&k==0)59 {60 return 1;61 }62 else return 0;63 }64 if(dp[flag][pos][k][sum]!=-1)65 {66 return dp[flag][pos][k][sum];67 }68 int ak = 0;69 if(flag)70 {71 int i,j;72 for(i = 0; i <= 9; i++)73 {74 int ss = dfs(pos-1,flag,(((k-N[pos-1]*i)%mod+mod)%mod),((sum-i)%mod+mod)%mod,mod);75 if(ss>0)ak+=ss;76 }77 }78 else if(!flag)79 {80 int i;81 for(i = 0; i < ans[pos]; i++)82 {83 int dd= dfs(pos-1,flag^1,(((k-N[pos-1]*i)%mod+mod)%mod),((sum-i)%mod+mod)%mod,mod);84 if(dd>0)ak+=dd;85 }86 int ss = dfs(pos-1,flag,(((k-N[pos-1]*ans[pos])%mod+mod)%mod),((sum-ans[pos])%mod+mod)%mod,mod);87 if(ss>0)ak+=ss;88 }89 return dp[flag][pos][k][sum] = ak;90 }
(UVA)11361 - Investigating Div-Sum Property
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。