PKU 3252 Round Numbers
問題概要
[Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ
桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった)
dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限できてるか、lはずっと0か
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define pb push_back vector<int> v; const int geta = 40; int dp[40][100][2][2]; int rec(int x,int d,bool f,bool f2) { if(x==v.size()) { if(d>=0&&!f2)return 1; else return 0; } if(dp[x][d+geta][f][f2]!=-1)return dp[x][d+geta][f][f2]; int res = 0; if(f) { for(int i=0;i<=v[x];i++) { int nd = d; bool nf,nf2; if(!f2&&i==0)nd++; else if(i!=0)nd--; if(i==v[x])nf=true; else nf = false; if(f2&&i==0)nf2=true; else nf2=false; res += rec(x+1,nd,nf,nf2); } } else { for(int i=0;i<=1;i++) { int nd = d; bool nf2; if(!f2&&i==0)nd++; else if(i!=0)nd--; if(f2&&i==0)nf2=true; else nf2=false; res += rec(x+1,nd,false,nf2); } } return dp[x][d+geta][f][f2]=res; } int solve(int x) { v.clear(); while(x) { v.pb(x%2); x/=2; } memset(dp,-1,sizeof(dp)); reverse(v.begin(),v.end()); return rec(0,0,true,true); } int main() { int a,b; scanf("%d %d",&a,&b); printf("%d\n",solve(b)-solve(a-1)); return 0; }