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

靠,WHY WA?我跟纯暴力程序对答案都没问题

Posted by CydorniaKnight at 2008-11-07 15:32:59 on Problem 3252
In Reply To:Re:看看为什么wa,跟ac程序对拍都没问题 Posted by:polor at 2008-11-07 15:30:15
#include<iostream>
using namespace std;

int l,r,ans,c[40][40]={0},b[40]={0},bl[40],br[40],bll,brl;

void getcc()
{
	int i,j,k;
	for(i=0;i<33;++i)
		c[i][0]=1;
	c[1][1]=1;
	for(i=2;i<33;++i)
		for(j=1;j<=i;++j)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	for(i=2;i<32;++i)
	{
		k=i-1;
		j=(i&1)+(i>>1);
		b[i]=b[k];
		for(;j<=k;++j)
			b[i]+=c[k][j];
	}
}

int solve(int m[],int ml)
{
	int answer=b[ml-1],i,j=ml-2,a;
	a=(ml&1)+(ml>>1);//at least 'a' 0s
//	cout<<a<<'!'<<endl;
	while(j>=0){
		if(m[j]){
			if(a>0) i=a-1;
			else i=a;
			for(;i<=j;++i){
				answer+=c[j][i];
//				cout<<j<<':'<<i<<endl;
			}
		}else --a;
		--j;
	}
	return answer;
}

int main()
{
	int i;
	getcc();
	while(cin>>l>>r){
		ans=bll=brl=i=0;
		while(l){
			if(l&1)
				bl[bll++]=1;
			else
				bl[bll++]=0;
			l>>=1;
		}
		while(r){
			if(r&1)
				br[brl++]=1;
			else{
				br[brl++]=0;
				++i;
			}
			r>>=1;
		}
		if(i>=brl-i)
			++ans;
		ans+=solve(br,brl)-solve(bl,bll);
		cout<<ans<<endl;
	}
	return 0;
}

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