hdu 3555
题意: 求1到n中有多少个数字包含了串49
解法一：
长度 L 的数字中不包含 49 且最高位不是 9 的个数 dp[L][0]
长度 L 的数字中不包含 49 串中最高位是 9 的个数 dp[L][1]
长度 L 的数字中包含 49 串的个数 dp[L][2]
预处理数位
初始化dp[0][0] = 1
dp[L][0] = 9 * dp[L-1][0] + 8 * dp[L-1][1]
dp[L][1] = dp[L-1][1] + dp[L-1][0]
dp[L][2] = 10 * dp[L-1][2] + dp[L-1][1]
然后逐位统计答案即可
LL dp[20][3];
int digit[20];
void init(){
dp[0][0] = 1;
for(int i = 1;i <= 18;i++){
dp[i][0] = 9 * dp[i-1][0] + 8 * dp[i-1][1];
dp[i][1] = dp[i-1][1] + dp[i-1][0];
dp[i][2] = 10 * dp[i-1][2] + dp[i-1][1];
}
}
LL cal(LL n){///注意这种做法是0到n-1的 所以n++
n++;
int pos = 0;
while(n){
digit[++pos] = n % 10;
n /= 10;
}
LL ans = 0;
int last = 0;
bool flag = false;
for(int i = pos;i;i--){
for(int j = 0;j < digit[i];j++){
ans += dp[i-1][2];
if(flag) ans += dp[i-1][0] + dp[i-1][1];///前缀已经包含了49
else if(j == 4) ans += dp[i-1][1];///当前位为4
}
if(last == 4 && digit[i] == 9) flag = true;
last = digit[i];
}
return ans;
}
int main(){
init();
int T;
for(scanf("%d",&T); T; T--){
LL n;
scanf("%lld",&n);
printf("%lld
",cal(n));
}
return 0;
}
- 但是这种做法很麻烦，在计算答案的时候需要分类讨论，要是情况比较复杂就爆炸了
通用解法 dfs(pos,state,bounded)
/*求出0到n有多少个包含49的数字
将数字分为两段，前缀和后缀
state = 0 前缀不包含49 最后一个数字不为4
state = 1 前缀不包含49 最后一个数字为4
state = 2 前缀包含49
dp[pos][state] 则表示在前缀状态为state的情况下，后缀长度为pos，前后缀拼起来包含49的数字的个数*/
LL dp[20][3];
int digit[20];
int next_state(int cur_state,int in){
if(cur_state == 0 && in == 4)
cur_state = 1;
else if(cur_state == 1 && in == 9)
cur_state = 2;
else if(cur_state == 1 && in != 4)
cur_state = 0;
return cur_state;
}
LL dfs(int pos,int state,bool bounded){
if(pos == 0)
return state == 2;
if(!bounded && dp[pos][state]!=-1)
return dp[pos][state];
LL ans = 0;
int ed = bounded?digit[pos]:9;
for(int i = 0;i <= ed;i++)
ans += dfs(pos - 1, next_state(state,i), bounded && i == ed);
if(!bounded){ ///不取上界时，可以取满
dp[pos][state] = ans;
}
return ans;
}
LL cal(LL x){
int pos = 0;
while(x){
digit[++pos]= x % 10;
x /= 10;
}
return dfs(pos, 0, true);
}
int main()
{
memset(dp, -1, sizeof(dp));
int T;
for(scanf("%d",&T); T; T--){
LL n;
scanf("%lld",&n);
printf("%lld
",cal(n));
}
return 0;
}
hdu 3652
求[1,n]内有多少个数字，该数字有13，且能被13整除 n<=10^9
上一题的加强版 需要修改的就是state的状态定义
分成两个子状态
remainder 前缀对13取余
have 前缀不包含13 前缀不包含13且最后一位数字是1 前缀包含13 0 1 2表示
int dp[20][13][3];
int digit[20];
int next_have(int cur_have,int in){
if(cur_have == 0 && in == 1)
cur_have = 1;
else if(cur_have == 1 && in == 3)
cur_have = 2;
else if(cur_have == 1 && in != 1)
cur_have = 0;
return cur_have;
}
int dfs(int pos, int remainder, int have, bool bounded){
if(pos == 0)
return have == 2 && remainder == 0;
if(!bounded && dp[pos][remainder][have]!=-1)
return dp[pos][remainder][have];
int ans = 0;
int ed = bounded?digit[pos]:9;
for(int i = 0;i <= ed;i++)
ans += dfs(pos - 1, (remainder * 10 + i)%13, next_have(have,i), bounded && i == ed);
if(!bounded){ ///不取上界时，可以取满
dp[pos][remainder][have] = ans;
}
return ans;
}
int cal(int x){
int pos = 0;
while(x){
digit[++pos]= x % 10;
x /= 10;
}
return dfs(pos, 0, 0, true);
}
int main()
{
memset(dp, -1, sizeof(dp));
int n;
while(scanf("%d",&n)==1){
printf("%d
",cal(n));
}
return 0;
}
hdu 4352
(题意： 求出L,R之间有多少个数字 满足 其最长严格递增子序列的长度为K(1<=K<=10), 0<L<=R<=2^{63}-1)
思路：按照最长上升子序列nlogn的解法，如果子序列的长度相同，那么最末尾的元素较小的有望
形成更长的子序列，可以用dp[i]表示长度为i的最长上升子序列的末尾元素的最小值，每次二分去做替换。
由于这里K很小，所以可以状压表示这个dp数组，于是这道题的状态定义就是dp[pos][state][K]
前缀能够构成的上升子序列状态为state,后缀pos位，组合起来拼成的最长上升子序列长度为K的答案,直接枚举位置更新状态即可
LL dp[20][1<<10][11];
int cnt[1<<10];
int digit[20];
int K;
int cur_state(int state,int in){
for(int i = in;i < 10;i++){
if(state & (1<<i)){
state ^= (1<<i);
break;
}
}
state |= (1<<in);
return state;
}
LL dfs(int pos, int state, bool leading_zero, bool bounded){
if(pos == 0) return cnt[state] == K;
if(!leading_zero && !bounded && dp[pos][state][K]!=-1)
return dp[pos][state][K];
LL ans = 0;
int ed = bounded?digit[pos]:9;
for(int i = 0;i <= ed;i++){
if(leading_zero){
if(i == 0) ans += dfs(pos - 1, state, true, bounded && i == ed);
else ans += dfs(pos - 1, cur_state(state, i), false, bounded && i == ed);
}else{
ans += dfs(pos - 1,cur_state(state,i),false,bounded && i == ed);
}
}
if(!leading_zero && !bounded){ ///不取上界时，可以取满
dp[pos][state][K] = ans;
}
return ans;
}
LL cal(LL x){
int pos = 0;
while(x){
digit[++pos]= x % 10;
x /= 10;
}
return dfs(pos, 0, true, true);
}
int main()
{
for(int s = 0;s < (1<<10);s++){
cnt[s] = 0;
for(int i = 0;i <10;i++) if(s & (1<<i)) cnt[s]++;
}
memset(dp, -1, sizeof(dp));
int T, cas = 1;
LL L, R;
cin>>T;
while(T--){
scanf("%lld%lld%d",&L,&R,&K);
printf("Case #%d: %lld
",cas++,cal(R) - cal(L-1));
}
return 0;
}
/*
5
123 345 2
12 123411 5
12 123411 2
12 123411 3
12 123411 4
*/
SPOJ Balanced numbers
题意： 定义balanced numbers为每个数出现的数字中 每个奇数出现的次数为偶数次，偶数出现的次数为奇数次，
求区间L,R有多少个这样的数字
思路： 一开始直接用状压 0，1 表示每个数字出现的次数的奇偶，敲完后发现样例不对，想了想发现我这样不能判断偶数是否出现过，所以要用三进制来状压
LL dp[20][60000]; /// 3^10 = 59049 0代表没出现 1代表出现过奇数次 2代表出现过为偶数次
int digit[20];
int base[10];
int cur_state(int state,int in){
int tmp = state;
for(int i = 0;i < in;i++) tmp /= 3;
if(tmp % 3 != 2) state += base[in];
else state -= base[in];
return state;
}
LL dfs(int pos, int state, int leading_zero, bool bounded){
if(pos == 0) {
for(int i = 0;i < 10;i++){
if(state % 3 == 1 && i % 2) return 0;
if(state % 3 == 2 && !(i % 2)) return 0;
state /= 3;
}
return 1;
}
if(!leading_zero && !bounded && dp[pos][state]!=-1)
return dp[pos][state];
LL ans = 0;
int ed = bounded?digit[pos]:9;
for(int i = 0;i <= ed;i++){
if(leading_zero){
if(i == 0) ans += dfs(pos - 1, state ,true, bounded && i == ed);
else ans += dfs(pos - 1,cur_state(state, i), false, bounded && i == ed);
}else ans += dfs(pos - 1,cur_state(state, i), false, bounded && i == ed);
}
if(!leading_zero && !bounded){ ///不取上界时，可以取满
dp[pos][state] = ans;
}
return ans;
}
LL cal(ULL x){
int pos = 0;
while(x){
digit[++pos] = x % 10;
x /= 10;
}
return dfs(pos, 0, true, true);
}
int main()
{
base[0] = 1;
for(int i = 1;i < 10;i++) base[i] = base[i-1] * 3;
memset(dp, -1, sizeof(dp));
int T;
ULL L, R;
cin>>T;
while(T--){
scanf("%llu%llu",&L,&R);
printf("%llu
",cal(R) - cal(L-1));
}
return 0;
}
/*
*/
codeforces 55D Beautiful numbers
(题意：求区间[L,R]中有多少数字能整除本身所有非零位的数字 1<=L<=R<=9*10^{18})
题解：
- 一个数能整除一些数，即这个数能整除这些数的lcm
- X % a = X % (a * b) % a
有什么用么？
我们需要保存前缀的有关状态，当然不可能直接把数字存下来，所以要缩小范围但是要不影响其作用
很容易想到的就是取余了
MOD = lcm(1,2,....9) = 2520
假设数为X，其所有非零位数字的lcm为lcmx
MOD % lcmx = 0 是显然的
于是X % lcmx = X % MOD % lcm，这样就把X的范围缩小了
这样就很清楚了，保存前缀的两个状态
- 1 对MOD 取余
- 2 数字的lcm
但是dp[20][2520][2520]爆内存了，打表会发现1到9的lcm组合只有48种，离散化处理一下就好了
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define P pair<int,int>
using namespace std;
int id[2521];
LL dp[20][2521][49];///pos, remainder, lcm
int digit[20];
int Gcd(int x,int y){
return y == 0?x:Gcd(y,x%y);
}
int Lcm(int x,int y){
return x / Gcd(x, y) * y;
}
void init(){
int ix = 0;
for(int s = 2;s < (1<<10);s++){
int tmp = 1;
for(int i = 1;i < 10;i++){
if(s & (1<<i)) tmp = Lcm(tmp,i);
}
if(!id[tmp]) id[tmp] = ++ix;
}
memset(dp, -1, sizeof(dp));
}
LL dfs(int pos, int remainder, int lcm, bool leading_zero, bool bounded){
if(pos == 0) {
return remainder % lcm == 0;
}
if(!leading_zero && !bounded && dp[pos][remainder][id[lcm]]!=-1)
return dp[pos][remainder][id[lcm]];
LL ans = 0;
int ed = bounded?digit[pos]:9;
for(int i = 0;i <= ed;i++){
if(i) ans += dfs(pos - 1, (remainder * 10 + i)%2520, Lcm(lcm,i), false, bounded && i == ed);
else if(leading_zero) ans += dfs(pos - 1, remainder, lcm, true, bounded && i == ed);
else ans += dfs(pos - 1, remainder * 10 % 2520, lcm, false, bounded && i == ed);
}
if(!leading_zero && !bounded){ ///不取上界时，可以取满
dp[pos][remainder][id[lcm]] = ans;
}
return ans;
}
LL cal(LL x){
int pos = 0;
while(x){
digit[++pos] = x % 10;
x /= 10;
}
return dfs(pos, 0, 1, true, true);
}
int main()
{
init();
int T;
cin>>T;
while(T--){
LL L, R;
cin>>L>>R;
cout<<cal(R) - cal(L - 1)<<endl;
}
return 0;
}
/*
*/