BZOJ 1662: [Usaco2006 Nov]Round Numbers 圓環數（數位DP+惡心細節）

BZOJ 1662: [Usaco2006 Nov]Round Numbers 圓環數

Time Limit:?5 Sec??Memory Limit:?64 MB

Description

正如你所知，奶牛們沒有手指以至于不能玩“石頭剪刀布”來任意地決定例如誰先擠奶的順序。她們甚至也不能通過仍硬幣的方式。 所以她們通過"round number"競賽的方式。第一頭牛選取一個整數，小于20億。第二頭牛也這樣選取一個整數。如果這兩個數都是 "round numbers"，那么第一頭牛獲勝，否則第二頭牛獲勝。 如果一個正整數N的二進制表示中，0的個數大于或等于1的個數，那么N就被稱為 "round number" 。例如，整數9，二進制表示是1001，1001 有兩個'0'和兩個'1'; 因此，9是一個round number。26 的二進制表示是 11010 ; 由于它有2個'0'和 3個'1'，所以它不是round number。 很明顯，奶牛們會花費很大精力去轉換進制，從而確定誰是勝者。 Bessie 想要作弊，而且認為只要她能夠知道在一個指定區間范圍內的"round numbers"個數。 幫助她寫一個程序，能夠告訴她在一個閉區間中有多少round numbers。區間是 [start, finish]，包含這兩個數。 (1 <= Start < Finish <= 2,000,000,000)

Input

* Line 1: 兩個用空格分開的整數，分別表示Start 和 Finish。

Output

* Line 1: Start..Finish范圍內round numbers的個數

Sample Input

2 12

Sample Output

6

題解

其實我真的懶得動寫題解。。。

不過這題網上做法千奇百怪。3維~5維DP都有，還有用記憶化搜索的。我實在看不下去了。這題其實兩維DP+幾個循環就足夠了！

就是個惡心版數位DP！！！

我們設dp[i][j]為轉成二進制后?前導可以為0 的長度為i的串，其中零的個數為j的二進制串總個數。

很顯然得到狀態轉移方程：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]

dp數組可以預處理得到。。。

sum(i,j)函數可以累計DP數組求出長度為i且零比一至少多j個的二進制串總個數。

那么如何計算ST-ED范圍內的答案？

用1...ED的答案減去1...ST-1的答案即可。（solve函數傳入x即求1...二進制_x的答案）

比如計算1..110100的答案：

其中幾部分是1-1,10-11,100-111,...,10000-11111

最后一部分是求100000-110100的答案

可以拆成100000-101111和110000-110011分別求解，這樣就很好解決了，怎么求解還是很明顯的。

由此可見求100000-110100的答案之類最后一部分的基本思想是：

從左往右掃到第i位時 當前1比0多d個?如果是此位為0跳過 如果是1則累計ans+=sum(i-1,d-1)。

大體上就是這樣，不過細節惡心！

首先，若讀入的數為0直接跳過，不然會無限RE。。。

其次，若讀入的數轉成二進制，0的個數>=1的個數則最后ans++，說明這個數本身合法。

另外還有一些起始點，邊界等細節問題。

下面給出參考代碼：（其實還是很短的2333）

#include<bits/stdc++.h>
using namespace std;int n,m; 
int dp[35][35];int sum(int l,int x)
{int s=0;for(int i=0;i<=l;i++)if(2*i>=l+x)s+=dp[l][i];return s;
}int solve(int x)
{int len=0,ans=0,d=1,t=x,v[35];while(t){v[++len]=t&1;t>>=1;}for(int i=1;i<len;i++)ans+=sum(i-1,1);len--;while(len){if(v[len])ans+=sum(len-1,d-1),d++; else d--;len--;}if(d<=0)ans++;return ans; 
}int main()
{for(int i=1;i<=32;i++){dp[i-1][0]=1;for(int j=1;j<=i;j++)dp[i][j]+=dp[i-1][j]+dp[i-1][j-1];}scanf("%d%d",&n,&m);if(n>2)printf("%d\n",solve(m)-solve(n-1)); else printf("%d\n",solve(m));return 0;
}