网络公司除了做网站,商丘网,联盟网站做任务,wordpress远程保存图片大小题意
题目就是说让我们在l到r的数字中求得有多少个连续k为不相同的数
1≤L≤R≤1e18
2≤K≤5
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)分析
直接枚举必然超时 考虑数位dp
由于k最大到5 所以我们可以记录前四位的大小 通过一个c…题意
题目就是说让我们在l到r的数字中求得有多少个连续k为不相同的数
1≤L≤R≤1e18
2≤K≤5
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)分析
直接枚举必然超时 考虑数位dp
由于k最大到5 所以我们可以记录前四位的大小 通过一个check函数去判断是否存在相同的数
也就是说 状态转移发生在前四位对应的数字大小的情况下
我们开一个dp[pos][p1][p2][p3][p4]记录在pos下前四位分别是p1,p2,p3,p4的符合条件的数的个数
然后每次搞完后记录下来没有限制 我们的dp数组中只记录没有限制的数 如果有限制就不记录只是求和
如何判断前四位是否与本位相同 我们可以把前导0用10表示 如果前面的位数是10表示前面的数是0code
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll ans,l,r,k,dp[20][11][11][11][11],d[20],dig;
bool check(int p4,int p3,int p2,int p1,int x){if(k2p1!10)return x!p1;else if(k3)return (x!p1x!p2);else if(k4)return (x!p1x!p2x!p3);else return (x!p1x!p2x!p3x!p4);
}
ll DP(int pos,int p4,int p3,int p2,int p1,bool limit){if(pos0){return p1!10;}//3 这里的意义在于如果这个数是个0 就不记录他//每次走到了pos0的时候 因为走到这里的数 只可能是1个确切的数 px都已经确定if(!limit~dp[pos][p4][p3][p2][p1])return dp[pos][p4][p3][p2][p1];//如果没有限制 且已经记录过 直接返回结果int up limit?d[pos]:9;//确认上界ll a0;for(int i0;iup;i){//pos位置下 从小到大数位枚举 把每一位下的分结果计算出来if(p110i0)//前导零情况aDP(pos-1,10,10,10,10,limitiup);//2 根据条件变化 如果前面是前导0并且本位也是0 那么传递下去的就是limit并且是否到达上界 两个条件决定 因为 如果前面没有限制 i没到达上界 可以把下一位的递归上界设为9的else if(check(p4,p3,p2,p1,i))aDP(pos-1,p3,p2,p1,i,limitiup);//每当我前面有限制和当前位是记录位大小时限制传递}if(!limit)dp[pos][p4][p3][p2][p1]a;//1每当把一种p组合的数遍历结束后 就把他们记录下来return a;
}
ll solve(ll x)
{dig0;while(x){d[dig]x%10;x/10;}return DP(dig,10,10,10,10,1);//传入时需要有限制 由于不能让最高位的up到9 需要到d[pos]
}
int main()
{while(~scanf(%lld%lld%lld,l,r,k)){memset(dp,-1,sizeof(dp));printf(%lld\n,solve(r)-solve(l-1));}return 0;
}
