poj3252

发表于 | 分类于 ， | 阅读数 次

链接:poj3252

Description

  • The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also
  • known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary
  • decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using
  • hooves.
  • They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The
  • second cow does the same. If the numbers are both “round numbers”, the first cow wins,
  • otherwise the second cow wins.
  • A positive integer N is said to be a “round number” if the binary representation of N has as many or more
  • zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two
  • zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes
  • and three ones, it is not a round number.
  • Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine.
  • Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.
  • Help her by writing a program that tells how many round numbers appear in the inclusive range given by the
  • input (1 ≤ Start < Finish ≤ 2,000,000,000).

    Input

  • Line 1: Two space-separated integers, respectively Start and Finish.

    Output

  • Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish

    Sample Input

    2 12

    Sample Output

    6

    题解

  • 模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,l,n) for(register int i=l;i<n;++i)
const int N=66;
int a[N],dp[N][N];//当前第i位，零的个数为j共有多少种情况 
int dfs(int pos,int sta,int limit,int lead){
    if(pos==-1)return sta>=32;;
    if(!limit&&!lead&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=limit?a[pos]:1;
    int tmp=0;
    rep(i,0,up+1){
        if(i==0&&lead)tmp+=dfs(pos-1,sta,limit&&i==a[pos],lead);
        else tmp+=dfs(pos-1,sta+(i==0?1:-1),i==a[pos]&&limit,lead&&i==0);
    }
    if(!limit&&!lead)dp[pos][sta]=tmp;
    return tmp;
}

int solve(int x){
    int cnt=0;
    while(x){
        a[cnt++]=x&1;
        x>>=1;
    }
    return dfs(cnt-1,32,1,1);
}

int main(){
    int l,r;
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&l,&r);
    printf("%d",solve(r)-solve(l-1));
    return 0;
}