本文共 1636 字，大约阅读时间需要 5 分钟。

对于一个正整数X，如果把X化成二进制数后，如果X的二进制数至少有三个连续的1或者至少有3个连续的0（不能有前导0），那么X就是“好数”。例如8就是“好数”，因为8对应的二进制数是1000，有三个连续的0。整数15也是“好数”，因为15对应的二进制数是1111，也有三个连续的1。整数27就不是“好数”，因为27对应的二进制数是11011，既没有连续的三个1也没有连续三个0。
现在给出两个整数Low、UP，求Low和UP范围内有多少个“好数”。

Input

一行，两个整数Low、UP，其中0 <= Low <= UP <= 2147483647。

Output

一个整数。

Sample Input

0 16

Sample Output

5

是数位DP。之前有接触到，但是比赛的时候就是想不起来有这种玩意。。。
（最终还是k了一下别人的代码。。。lyftql）（没办法现在的我觉得那是最优打法）
我们可以知道，没有三个同样的数连在一起的数为“坏数”，那么“好数”=总数-“坏数”。
设f[i][x=0/1][y=0/1]为：第i位为x，第i-1位为y的坏数总数。
使三个数不同，得：

f[i][0][0]=f[i-1][0][1];f[i][0][1]=f[i-1][1][0]+f[i-1][1][1];f[i][1][0]=f[i-1][0][1]+f[i-1][0][0];f[i][1][1]=f[i-1][1][0];

这样就可以算出1-1,10-11,100-111,1000-1111…的“坏数”了。
然后从高位枚举1变成0，注意使它与前面的不形成3个0。然后如果它已经连成三个了，后面再变就没必要了，-1，退出。
然后以下代码推了一下90分，瓦不管了。。。。（心累，注释也暂时不想打了）

#include<cstdio>#include<cstring>using namespace std;int f[101][3][3],s[101],l,r,Kl,l1,l2,Ans,t;int C(int k){   	if(k<0) return 0;	int w=0,ll=k;	memset(s,0,sizeof(s));	while(k){   		s[++w]=k%2;		k/=2;    }    if(t==0) l2=w;    else l1=w;    t=1;    int ans=1;	for(int i=w-1;i;--i){   	 	if(s[i]==1)		 if(s[i+1]==1||s[i+2]==1||i==w-1)	 	  ans+=f[i+1][s[i+1]][0];	 	if(s[i]==s[i+1]&&s[i+1]==s[i+2]&&i!=w-1){   	 		ans--;			break;		 }	 } 	return ans;}int main(){   	freopen("d.in","r",stdin);	freopen("d.out","w",stdout);	scanf("%d%d",&l,&r);    f[1][1][0]=1;    f[1][0][1]=1;    for(int i=2;i<=35;++i){       	f[i][0][0]=f[i-1][0][1];    	f[i][0][1]=f[i-1][1][0]+f[i-1][1][1];    	f[i][1][0]=f[i-1][0][1]+f[i-1][0][0];    	f[i][1][1]=f[i-1][1][0];	}	Ans=r-l+1-C(r)+C(l-1);	for(int i=l1;i<l2;++i)	  Kl=Kl+f[i][1][0]+f[i][1][1];	Ans-=Kl;	printf("%d",Ans);	fclose(stdin);	fclose(stdout);}