山东网站推广营销设计,做网站需要下什么软件,怎样做游戏网站,用凡科做的网站要钱吗正题
题目链接:https://www.luogu.org/problemnew/show/P2657 题目大意
求A∼BA\sim BA∼B中不含前导零且没两个相邻的位数相差至少为222的数字个数。 解题思路
考虑记忆化搜索#xff0c;用fi,jf_{i,j}fi,j表示到第iii位数字为jjj时的方案数。
然后用1∼B1\sim B1∼B中…正题
题目链接:https://www.luogu.org/problemnew/show/P2657 题目大意
求A∼BA\sim BA∼B中不含前导零且没两个相邻的位数相差至少为222的数字个数。 解题思路
考虑记忆化搜索用fi,jf_{i,j}fi,j表示到第iii位数字为jjj时的方案数。
然后用1∼B1\sim B1∼B中的个数减去1∼A−11\sim A-11∼A−1中的个数
然后fi,j∑k1nfi1,k∗(∣j−k∣≥2)f_{i,j}\sum_{k1}^n f_{i1,k}*(|j-k|\geq 2)fi,jk1∑nfi1,k∗(∣j−k∣≥2)
但是有些限制要不能超过kkk所以我们用两个布尔变量zerozerozero表示是否处于前导零limstlimstlimst表示前面的位数是否都处于最大位(因为这样的话本位就不能超过最大位)。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int A,B,f[15][15],num[15];
int dfs(int l,int last,int limst,int zero)
{if(!l) return 1;if(!limst!zerof[l][last]!-1)return f[l][last];int p,sum0,maxnlimst?num[l]:9;for(int i0;imaxn;i){if(abs(i-last)2) continue;pi;if(zerop0) p-2;sumdfs(l-1,p,limst(imaxn),(p-2));}if(!limst!zero) f[l][last]sum;return sum;
}
int count(int x)
{int k0;while(x){num[k]x%10;x/10;}memset(f,-1,sizeof(f));return dfs(k,-2,1,1);
}
int main()
{scanf(%d%d,A,B);printf(%d,count(B)-count(A-1));
}
