之前做数位统计时,一般是先初始化,然后再逐位统计。 前几天在codeforces遇到一种用记忆化搜索写的数位统计,挺神奇的。用它改写之前写过的几道数位统计,发现代码更短,速度也更快,有一定通用性. 这种写法一般用于初始化跟逐位统计是一样过程的。 codeforces 55D http://www.cppblog.com/Yuan/archive/2011/01/24/139201.html 我是从这题了解到这种写法 用这种方法写,一个流程是,列出式子(pre*10^pos + next) pre是确定的,next是变量 所以参数就为pre,pos加上一些其他的,还有一个标记doing,表示是计算有上界限制的还是没有上界限制(所有情况,即end=9) dfs(pos-1 , npre , doing && i ==end) 2010成都赛区A题 zoj 3416 之前的写法 http://www.cppblog.com/Yuan/archive/2010/11/14/133608.html 改写后
 /**//*
题目描述见另外一份
平衡,即∑a[i]*(i-o) = 0 o为支点
对于一个数,支点o是唯一的,所以不会有重复计数的情况(但有一种特殊的,就是0,00,000等都是一样的,会计算多次,
最后减去即可)
假设检查到pos处,对于上面的式子∑a[i]*(i-o) = 0,这里确定了支点为o
之前的数其∑a[i]*(i-o)的结果为pre
所以参数需要为pos , o , pre

当检查到pos=-1时,return pre == 0
否则,看当前是计算所有情况还是具体情况(doing)
如果是所有情况且dp值!=-1,直接return
否则就枚举0到end

而支点o需要在最外层枚举出来
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

long long dp[19][19][2000];
int digit[19];

void init()
  {
memset(dp,-1,sizeof(dp));
}

long long dfs(int pos , int o , int pre , bool doing)
  {
if(pos == -1)
return pre == 0;

if(!doing && dp[pos][o][pre] != -1)
return dp[pos][o][pre];

long long ans = 0;
int end = doing ? digit[pos] : 9;
for(int i = 0 ; i <= end ; i ++)
 {
int npre = pre;
npre += (pos-o)*i;
ans += dfs(pos-1 , o , npre , doing && i == end);
}

if(!doing)
dp[pos][o][pre] = ans;
return ans;
}

long long cal(long long x)
  {
int pos = 0;
while(x)
 {
digit[pos++] = x % 10;
x /= 10;
}
long long ans = 0;
for(int o = 0 ; o < pos ; o ++)
 {
ans += dfs(pos-1 , o , 0 , 1);
}
return ans - (pos-1);//duplicate 0
}

int main()
  {
init();
int T;
for(scanf("%d",&T) ; T--; )
 {
long long left , right;
scanf("%lld%lld",&left , &right);
printf("%lld\n",cal(right) - cal(left - 1));
}
return 0;
}
2010 成都网络赛 B hdu 3652 之前的代码 http://www.cppblog.com/Yuan/archive/2010/09/23/127454.html
 /**//*
求[1,n]内有多少个数字,该数字有13,且能被13整除 n<=10^9
x % 13 = 0
(pre*10^pos + next) % 13 = 0 pre是之前确定的部分
需要的参数为pre , pos , 状态have
have记录pre拥有"13",pos+1位为"1",没有"13" 分别用have = 2,1,0表示
然后记忆化搜索

*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int dp[10][13][3];
int digit[10];

__int64 dfs(int pos , int pre , int have , bool doing)
  {
if(pos == -1)
return have == 2 && pre == 0;

if(!doing && dp[pos][pre][have] != -1)
return dp[pos][pre][have];

int ans = 0;
int end = doing ? digit[pos] : 9;
for(int i = 0 ; i <= end ; i ++)
 {
int npre = (pre*10 + i) % 13;
int nhave = have;
if(have == 0 && i == 1)
nhave = 1;
else if(have == 1 && i != 1)
nhave = 0;
if(have == 1 && i == 3)
nhave = 2;
ans += dfs(pos-1 , npre , nhave , doing && i == end );
}

if(!doing)
dp[pos][pre][have] = ans;
return ans;
}


int cal(int x)
  {
int pos = 0;
while(x)
 {
digit[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1 , 0 , 0 , 1);
}

int main()
  {
memset(dp,-1,sizeof(dp));
int n;
while(~scanf("%d",&n))
printf("%d\n",cal(n));
return 0;
}
参数跟条件有关,就像hdu3555就不需要pre
hdu 3555 之前写法 http://www.cppblog.com/Yuan/archive/2010/10/24/131057.html
 /**//*
问[1,n]内有多少个数字包含"49"
这里用记忆化搜索
更加好写,而且快

hdu 3652 是加强版
*/
#include<cstdio>
#include<algorithm>

using namespace std;


__int64 dp[20][3];
int digit[20];

__int64 dfs(int pos , int have , bool doing)
  {
if(pos == -1)
return have == 2;

if(!doing && dp[pos][have] !=-1)
return dp[pos][have];

__int64 ans = 0;
int end = doing ? digit[pos] : 9;
for(int i = 0 ; i <= end; i++)
 {
int nhave = have;
if(have == 1 && i != 4)
nhave = 0;
if(have == 0 && i == 4)
nhave = 1;
if(have == 1 && i == 9)
nhave = 2;
ans += dfs(pos-1 , nhave , doing && i == end);
}
if(!doing)
 {
dp[pos][have] = ans;
}

return ans;
}

__int64 cal(__int64 x)
  {
int pos = 0;
while(x)
 {
digit[pos++] = x % 10;
x /= 10;
}
return dfs(pos - 1 , 0 , 1);
}

int main()
  {
memset(dp,-1,sizeof(dp));
int T;
for(scanf("%d",&T) ; T-- ;)
 {
__int64 n;
scanf("%I64d",&n);
printf("%I64d\n",cal(n));
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|