HDU 2089 不要62
DESC: 问l, r范围内的没有4和相邻62的数有多少个。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std; int dp[][]; /*
3种状态：
0：前i位不含有不吉利数字 的数 的个数
1：前i位不含有不吉利数字且第i+1位数字是6 的数 的个数
2：前i位含有不吉利数字 的数 的个数
*/ //int dfs(int i, int s, bool e) {
// if (i==-1) return s==target_s;
// if (!e && ~dp[i][s]) return dp[i][s];
// int res = 0;
// int u = e?num[i]:9;
// for (int d = first?1:0; d <= u; ++d)
// res += dfs(i-1, new_s(s, d), e&&d==u);
// return e?res:f[i][s]=res;
//} int num[];
int len; int dfs(int pos, int s, bool e) {
if (pos == ) return s != ; //遍历完之后 判断当前数字是否是不吉利数
if (!e && dp[pos][s]) return dp[pos][s];
int sum = ;
int maxm = e?num[pos]:; for (int d = ; d <= maxm; ++d) {
if (s == ) {
if (d == ) sum += dfs(pos-, , e&&(maxm == d));
else if (d == ) sum += dfs(pos-, , e&&(maxm == d));
else sum += dfs(pos-, , e&&(maxm == d));
}
else if (s == ) {
if (d == || d == ) sum += dfs(pos-, , e&&(maxm == d));
else if (d == ) sum += dfs(pos-, , e&&(maxm == d));
else sum += dfs(pos-, , e&&(maxm == d));
}
else if (s == ) sum += dfs(pos-, , e&&(maxm == d));
}
return e?sum:dp[pos][s]=sum;
} int solve(int x) {
len = ;
while(x) {
num[len++] = x%;
x /= ;
}
len -= ;
return dfs(len, , );
} int main() {
int n, m;
// cout << solve(100) << endl;
memset(dp, , sizeof(dp));
while(~scanf("%d%d", &n, &m)) {
if (n == && m == ) break;
int l = solve(n-);
int r = solve(m);
int ans = r - l;
printf("%d\n", ans);
}
return ;
}
CF 55D Beautiful numbers 数位DP+离散化
DESC：如果一个数能整除它每一位上的数字，那么这个数叫做美丽数。问 l, r范围内的美丽数有多少个。
状态：dp[20][2600][55]; // dp[i][j][k] = x表示前i位mod2520的值为j 且最小公倍数是lcms[k] 的美丽数有多少个。
lcms[]是1~9的所有可能产生的最小公倍数的映射数组。
因为1~9能产生的最大公倍数是2520，又x%y==0 等价于x%y%z == 0在z是y的因子时成立。所以我们只需要维护前i个数mod2520的值，就可以知道前i个数mod1~9的值。
即第二维压缩到2520。
判断当前数字是否是beautiful number等价于判断当前数是否mod (前i位的最小公倍数==0)。
所以我们需要维护前i位的最小公倍数。
而1~9能产生的最小公倍数位最大值位2520，小于55个。所以可以离散化，即第三维压缩到55。
开始设计的状态是：dp[20][2]表示前i位是或不是beautiful number。中间用一个num数组标记当前值mod(1~9)的值，最后判断是否是beautiful number。
但是这样前i位的值就受后面的值的影响，不能记忆化了。遂超时。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std; const int maxn = ; LL dp[][][]; // dp[i][j][k] = x表示前i位mod2520的值为j 且最小公倍数是lcms[k] 的美丽数有多少个。
int num[];
int lcms[]; int gcd(int a, int b) {
return (b>?gcd(b, a%b):a);
} int ggcd(int a, int b) {
if (a == ) return b;
else if (b == ) return a;
return (a*b)/gcd(a, b);
} void getLcms() { //初始化lcms[]
memset(lcms, -, sizeof(lcms));
int num = ;
for (int i=; i*i<=maxn; ++i) {
if (maxn%i== && lcms[i] == -) { //能整除i
lcms[i] = num++;
int temp = maxn / i;
if (lcms[temp] == -)
lcms[temp] = num++;
}
}
} LL dfs(int pos, int pre, int lcm, bool lim) { // 当前位 前面i位mod2520的值 前面i-1位的lcm 当前位是否到最后一个数
if (pos == -) return (pre%lcm==); // 搜索到最后一位
if (!lim && dp[pos][pre][lcms[lcm]] != -) return dp[pos][pre][lcms[lcm]]; // 记忆化搜索
int mnum = (lim==?:num[pos]);
LL sum = ;
for (int i=; i<=mnum; ++i) {
int npre = (pre * + i) % maxn;
int nlcm = ggcd(lcm, i);
sum += dfs(pos-, npre, nlcm, lim&&(i==mnum));
}
return (lim==?dp[pos][pre][lcms[lcm]]=sum:sum);
} LL solve(LL x) {
int len = ;
while(x) {
num[len++] = x % ;
x /= ;
}
return dfs(len-, , , ); //
} int main() {
// freopen("in.cpp", "r", stdin);
memset(dp, -, sizeof(dp));
getLcms();
int t;
scanf("%d", &t);
while(t--) {
LL l, r;
scanf("%I64d%I64d", &l, &r);
LL ans = solve(r) - solve(l-);
printf("%I64d\n", ans);
}
return ;
}
附上大腿的代码，虽然加了两个z和zz数组这两个智障产物，有碍观瞻。但是，被有爱的注释感动了。有木有。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define LL long long
using namespace std; /*首先，个位数最大的公倍数是5*7*8*9=2520 ，所以，我们第二维通过取余可以压缩到2520；打表可知，0-9组成的不同的公倍数不超过55个，所以第三压缩至55*/
long long state[][][];/*state[a][b][c] a:第几位 b:前a位数字代表的数对2520取余的值 c:前a位数字的公倍数，在id数组中的映射的值 */
int num[];/*都懂*/
int id[];/*所有可能出现的公倍数的映射，比如，9是可能出现的公倍数，就让id[9]=1;依次类推*/
int z[][];/*z[a][b] 存储的是 a与b的公倍数的值，在程序中，a指第i位的取值，b指前i-1位的公倍数，即dfs中传入的变量lcm*/
int zz[][];/*zz[a][b] 存储的是 前i-1位为b 新一位为 a 得到的新的数为多少，这个和上面那个其实没什么用，只是当时没找到正确超时的点，所以加上的*/
int _index=,num2=;/*num2为上面id那个数组的计数*/ long long gcd(long long a,long long b)
{
return (b>?gcd(b,a%b):a);
}/*求公倍数*/ void init()/*初始化*/
{
for(int i=;i*i<=;i++)
{
if(%i==)
{
id[i]=num2++;
if(i*i!=)id[/i]=num2++;
}
}/*初始化id，原理是，2520必定是其他可能公倍数的倍数，因为2520=9*8*7*5，1，2,3,4,6，都是5 7 8 9的因数*/
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
z[i][j]=(i==?j:j*i/gcd(j,i));
}
for(int j=;j<=;j++)
{
zz[i][j]=(j*+i)%;
}
}/*z zz数组初始化*/
// cout<<1<<endl;
} void getnum(long long x)
{
memset(num,,sizeof(num));
_index=;
while(x>)
{
num[_index++]=x%;
x=x/;
}
// cout<<num[0]<<endl;
} long long dfs(int i,long long st,long long lcm,int limit)/*st 前i位代表的数 lcm 前i位数的公倍数*/
{
if(i==-)return st%lcm==;
if(!limit&&state[i][st][id[lcm]]!=-)return state[i][st][id[lcm]];
int maxn=limit?num[i]:;
//cout<<lcm<<endl;
long long ans=;
for(int j=;j<=maxn;j++)
{
ans+=dfs(i-,i?zz[j][st]:st*+j,z[j][lcm],limit&&j==maxn);
}
return limit?ans:state[i][st][id[lcm]]=ans;
} long long solve(long long x)
{
getnum(x);
return dfs(_index-,,,);
} int main()
{
freopen("codeforces55D.in.cpp","r",stdin);
int t;
long long l,r;
init();
memset(state,-,sizeof(state));/*这是当时超时的点，第一次写数位dp，不知道只需初始化一次，然后放到了solve里，就。。。翻车了*/
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",solve(r)-solve(l-));
}
}
return ;
}
HDU 4352 XHXJ's LIS
DESC：把一个数看做字符串，那么它的最长上升子序列的长度就是这个数的power value。
问，在l 到r的区间内，power value等于k的数有多少个。
(0<L<=R<2^63-1 and 1<=K<=10)
思路：
开始我是这样的：
2^63大概是10^18，k<=10，dp[20][1200][10] //1024
dp[i][j][k]=num 表示前i位的最长递增子序列为j长度为k的数的个数为num个。
dfs(pos, stu, num, lim)时。对当前位pos尝试放1~mnum的数字d时，
比较stu和nstu = stu | (1<<d)的大小..如果nstu>stu，dfs(pos-1, nstu, num+1, newlim);
否则的话。说明新加的数使得当前序列分成了两个。进行2次dfs。
1：原来的dfs(pos-1, stu, num, newlim).
2：包括新的数的LIS序列：dfs(pos-1, newstu, newnum, newlim)；
此时的newstu:对原来的stu进行一次num[pos]+1~9的与运算，和num[pos]或运算。同时计算出newnum.
bug1：1253这样搜索到的结果是2，125 和 123，所以单纯的这样记录状态也是不行的。所以第二维的状态改为：100101表示长度为x的LIS最后一位是y，
这样的话，125遇见3就会变成123了。
bug2：本来觉得len记录下当前的LIS长度会省一些重复计算，然而，状态和len相同时，k不同时返回的结果也应该是不同的，所以这个记忆化是错的。
于是就变成了这样：
int dp[20][1200][20]; //dp[i][j][k] = x 表示前i位 LIS状态为j 长度为k的 数字个数为 x
对当前的d，检查stu如果后面没有大于d的数,就直接newstu= stu | (1<<d)。否则，找出第一个大于d的数，删掉，然后或操作（1<<d），得到newstu。
前导0：检查当前d是前导0的时候，stu不变，继续搜索。
如果当前的数字出现过了，stu也不变，继续搜索。
【因为这次大腿也间歇性老年痴呆，两个人一起卡了两天晚上的几个点。最后一个bug：dp不是long long大腿找了一个点... ...感觉这个题A的也很感人，
青岛赛站结束是不是就不会这样写题了呢。有点舍不得。】
//HDU 4352 #include <stdio.h>
#include <string.h>
#include <iostream>
#define LL long long
using namespace std; int num[];
LL dp[][][]; //dp[i][j][k] = x 表示前i位 LIS状态为j 长度为k的 数字个数为 x LL dfs(int pos, int stu, int k, int lim) { //lim==1 表示当前位有限制
if (pos == -) {
int cnt = ;
for (int i=; i<=; ++i) {
if (stu & (<<i)) {
cnt++;
}
}
return (cnt == k);
}
if (!lim && dp[pos][stu][k] != -) return dp[pos][stu][k];
int mnum = (lim == ? : num[pos]);
LL sum = ;
for (int d=; d<=mnum; ++d) {
bool aft = false;
int tstu = stu;
bool pre = true;
if (d == ) {
for (int i=; i<=; ++i) {
if (tstu & (<<i)) pre = false;
}
if (pre) {
sum += dfs(pos-, stu, k, lim&&(d==mnum));
continue;
}
}
if (tstu & (<<d)) {
sum += dfs(pos-, stu, k, lim&&(d==mnum));
continue;
}
for (int i=d+; i<=; ++i) {
if (tstu & (<<i)) {
tstu = (stu ^ (<<i));
tstu |= (<<d);
aft = true;
break;
}
}
if (aft==false) { // 后面没有比他大的 可以直接加上
tstu = (stu | (<<d));
sum += dfs(pos-, tstu, k, lim&&(d==mnum));
}else sum += dfs(pos-, tstu, k, lim&&(d==mnum));
}
return (lim == ? dp[pos][stu][k] = sum : sum);
} LL solve(LL x, int k) {
if (x == ) return ;
int len = ;
while(x) {
num[len++] = x % ;
x /= ;
}
return dfs(len-, , k, );
} int main() {
// freopen("in.cpp", "r", stdin);
memset(dp, -, sizeof(dp));
int t;
scanf("%d", &t);
int cas = ;
while(t--) {
LL l, r;
int k;
scanf("%lld%lld%d", &l, &r, &k);
LL ans = solve(r, k) - solve(l-, k);
printf("Case #%d: %lld\n", cas++, ans);
}
return ;
}