はやし屋

競技プログラミングのメモ きたない

pku : 3252 Round Numbers

pkuかpojかどっちなんですかね...
http://poj.org/problem?id=3252

問題は

整数S,F(1 ≤ S < F ≤ 2,000,000,000)が与えられて

S以上F以下の Round Number の個数を求める問題です。

Round Numberというものは、
整数を二進数に直したときに、

"たっているビット数" <= "たっていないビット数"

であるような数です。

具体的には
1001 とか 10001 とか 100101 とか 100011001 です。


解法はZigZagと同じように桁でやりました。もっと簡単で効率的な解法が多分ある。

少しバグらせたけどデバッグうまくできてよかったです!

int dp[64][64][64][2][2];

int solve(const vector <int>&v,int idx,int n0,int n1,bool free,bool begin){

  if(idx == -1)return n0>=n1;

  if(~dp[idx][n0][n1][free][begin])return dp[idx][n0][n1][free][begin];

  int r = !free?v[idx]:1;
  int ret = 0 ;
  for(int i = 0 ; i <= r ; ++i){
    bool ch = !(r==i);
    if(begin){
      if(i==0){
	ret += solve(v,idx-1,0,0,free|ch,true); 
      } else {
	ret += solve(v,idx-1,n0,n1+1,free|ch,false);
      }
    } else {
      ret += solve(v,idx-1,n0+(i==0),n1+(i==1),free|ch,false);
    }
  }

  return dp[idx][n0][n1][free][begin] = ret;
}

int getNum(int x){
  vector < int > v;
  while(x){
    v.pb(x&1);
    x >>= 1;
  }
  return solve(v,v.size()-1,0,0,false,true);
}

int main(){
  memset(dp,-1,sizeof(dp));
  int a , b;
  cin >> a >> b;
  cout << (getNum(b)-getNum(a-1)) << endl;
  return 0;
}