萌新初学 IDDFS,TLE 10pts 求助
查看原帖
萌新初学 IDDFS,TLE 10pts 求助
203008
山田リョウ楼主2022/7/15 20:54

srds,我好像 btd 了,我好像去年就会了诶,只是今天才意识到应该写一下(

目前想到的剪枝全加上了,不知道为什么假了

#include<stdio.h>
#include<stack>
typedef unsigned long long ll;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
struct frac{
	ll a{0},b{1};
	frac&update(){ll d=gcd(a,b);return a/=d,b/=d,*this;}
	frac(ll x,ll y):a(x),b(y){update();}
	frac&operator-=(const frac&o){
		ll d=gcd(b,o.b);
		return a=o.b/d*a-b/d*o.a,b=b/d*o.b,update();
	}
	bool operator<(const frac&o)const{ll d=gcd(b,o.b);return o.b/d*a<b/d*o.a;}
};
std::stack<int>res;
bool iddfs(frac x,int s,int limit){
	x-=frac(1,s);
	if(x.a==0)return 1;
	if(s==limit)return 0;
	int l=s+1,r=limit;
	if(x<frac(1,limit))return 0;
	for(;l<r;){
		int mid=l+r>>1;
		if(x<frac(1,mid))l=mid+1;
		else r=mid;
	}
	for(s=l;s<=limit;++s){
		if(frac(limit-s+1,s)<x)return 0;
		if(iddfs(x,s,limit))
			return res.push(s),1;
	}
	return 0;
}
bool IDDFS(frac x){
	for(int i=1;i<=10000000;++i)
		for(int j=1;j<=i;++j){
			if(frac(i-j+1,j)<x)break;
			if(iddfs(x,j,i))
				return res.push(j),1;
		}
	return 0;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	IDDFS(frac(a,b));
	for(;!res.empty();res.pop())printf("%d ",res.top());
	return 0;
}
2022/7/15 20:54
加载中...