题意:
求0到N范围内所有数中, 二进制形式中邻接"1"的对数.
思路:
数位DP.
1. 记住数位DP就是要按位, 如果再一个一个数地增就不是数位DP了...
2. 有明显层次性的, 一般要预处理.
3. 按照状态去设置每一维的意义, 要为"可接续性"服务.(最高位为xx, 最低位为xx, 以xx结尾, 以x但不以xx结尾...之类的)
这一题就是首先预处理出
dp[i][0] 长度为i的二进制数, 首位为0的数中邻接"1"的对数.
dp[i][1] ````````````````````````````, 首位为1的````````````````````````````.
再统计对于N的情况.
除了直接加, 还要注意新产生的邻接"1", 也要一起加上.
#include <cstdio>
using namespace std;
typedef long long ll;
ll dp[32][2],ans;
int n;
void pre()
{
for(int i=2;i<=32;i++)
{
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i][0] + (1<<(i-2));
}
}
int main()
{
pre();
int T,cas=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int i,cnt = 0;
ans = 0;
for(i=31;i>=0;i--)
if((1<<i)&n)
{
ans += dp[i+1][0];
ans += (ll)cnt*(1<<i);
if(i+1<=31 && (1<<(i+1))&n)
cnt++;
}
ans += cnt;
printf("Case %d: %lld\n",++cas,ans);
}
}