网站建设推广公司范围,开设一个网站的费用,开发一个电商网站,对网站建设建议好数
jzoj 1521
题目大意#xff1a;
定义好数为转换为二进制后#xff0c;有至少三个连续的位相同的数#xff0c;现在要求一个范围内的好数个数
样例输入
0 16样例输出
5数据范围限制
0 Low UP 2147483647
提示 提示#xff1a;
对于50%测试
定义好数为转换为二进制后有至少三个连续的位相同的数现在要求一个范围内的好数个数
样例输入
0 16样例输出
5数据范围限制
0 Low UP 2147483647
提示 提示
对于50%测试0 Low UP 100000。
解题思路
我们可以用前缀和来求就把问题转换为了前n个数中好数的个数 它让我们求好数但因为好数特别难求所以我们可以求‘坏数’就是没有连续三个位是一样的数 我们先用数位DP求出多少位以什么开头的坏数总数 然后我们把他分位数小于n的位数的和等于n的位数的 小于的 我们就可以直接用已经求出来的坏数总数然后分为不同位数的直接加就行了 如1…1100100先分为1位2位3位4位5位6位的类型 等于的 就从大到小把1变成0这样就一定小于n了然后分别计算 最后还要计算n 然后用n减去坏数的个数就得到了好数的个数了
代码
#includecstdio
#includecstring
#includeiostream
#define ll long long
using namespace std;
ll a,b,s[40],f[40][5][5];
ll js(ll now)
{ll sum1;for (int inow-1;i0;--i)sumf[i][1][0]f[i][1][1];//小于的第一类for (int inow-1;i0;--i){if (s[i]1)if (s[i1]1||s[i2]1||inow-1)//把1改为0sumf[i1][s[i1]][0];相加if (s[i]s[i1]s[i1]s[i2]i!now-1)//判断是不是已经成为了好数了{sum--;break;}}return sum;
}
ll ans(ll dep)
{if (dep0) return 0;ll ldep,tot0;memset(s,0,sizeof(s));while (l) s[tot]l1,l1;//转二进制return dep-js(tot);//求好数
}
int main()
{f[1][1][0]1;f[1][0][1]1;for (int k2;k35;k){f[k][0][0]f[k-1][0][1];//数位DPf[k][0][1]f[k-1][1][1]f[k-1][1][0];f[k][1][0]f[k-1][0][0]f[k-1][0][1];f[k][1][1]f[k-1][1][0];}scanf(%lld %lld,a,b);printf(%lld,ans(b)-ans(a-1));//前缀和求职
}
