Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课:《ACM/ICPC竞赛训练》面向全球招生

表示这题DP 30行搞定,不会排列组合也能做。

Posted by lydliyudong at 2011-07-23 17:26:23 on Problem 3252 and last updated at 2011-07-23 17:27:32
f[i,j]表示二进制下一共i位,有j位是0的数的个数。
d[i,j]表示二进制下一共i位,有>=j位是0的数的个数。
求区间[s,e]的RoundNumber可以转化[1,e+1)-[1,s)
设某数s在二进制下有a位,则1~a-1位的数很容易计算:
∑d[i-1,(i+1)/2](1<=i<=a-1),其中第一位必须是1。
下面就是计算a位中比s小的符合要求的数:
若s上某一位是1(除了第一位),这一位前面已经有k个0,后边还有j位,
可以把这一位变成0,这样前面有k+1个0,
后边需要的0的个数至少为temp=max(0,(a+1)/2-k-1),所以inc(ans,d[j,temp])。
至此,该题用DP完美解决。

var
 f,d:array[0..32,0..32]of int64;
 s,e,a,b,i,j,k,ans:longint;
function calc(s,a:longint):longint;
 begin
  calc:=0;
  for i:=1 to a-1 do inc(calc,d[i-1,(i+1)>>1]);
  k:=0;
  for i:=a-2 downto 0 do
   if (s>>i)and 1=1 then
    begin
     j:=(a+1)>>1-k-1;
     if j<0 then j:=0;
     inc(calc,d[i,j]);
    end
   else inc(k);
 end;
begin
 for i:=0 to 31 do f[i,0]:=1;
 for i:=1 to 31 do
  for j:=1 to i do
   f[i,j]:=f[i-1,j]+f[i-1,j-1];
 d[0,0]:=1;
 for i:=1 to 31 do
  for j:=i downto 0 do
   d[i,j]:=d[i,j+1]+f[i,j];
 readln(s,e);
 inc(e);
 while s>>a<>0 do inc(a);
 while e>>b<>0 do inc(b);
 writeln(calc(e,b)-calc(s,a));
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator