萌新求助,迭代加深dfs 70 WA#4#7#8
查看原帖
萌新求助,迭代加深dfs 70 WA#4#7#8
421265
eastcloud楼主2022/5/4 17:26
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
ll ans=0,len,lim=2,flag,an[101][100001],sum[100001];
ll gcd(ll x,ll y){
	if(x%y==0) return y;
	else return gcd(y,x%y);
}
bool check(ll x,ll a,ll b,ll ti){
	double tmp=1.0/x*1.0*ti,tmp2=a*1.0/b;
	if(tmp<tmp2) return false;
	return true;
}
void dfs(ll a,ll b,ll step,ll last){
	if(flag && last>an[1][lim]) return;
	if(step==lim && a==0){
		if(!len || an[1][lim]>last){
			len=1;
			for(int i=1;i<=lim;i++)an[len][i]=sum[i];
		}
		else if(len && an[1][lim]==last){
			len++;
			for(int i=1;i<=lim;i++)an[len][i]=sum[i];
		}
		flag=1;
		return;
	}
	else if(step==lim) return;
	ll s=last+1;
	if(b%a==0) s=max(s,b/a);
	else s=max(s,b/a+1);
	for(ll i=s;1;i++){
		if(!check(i,a,b,lim-step))break;
		sum[step+1]=i;
		ll ta=a,tb=b;
		tb*=i;
		ta=(ta*i)-b;
		if(ta==0){
			dfs(0,i,step+1,i);
			continue;
		}
		ll tmp=gcd(ta,tb);
		ta/=tmp;tb/=tmp;
		dfs(ta,tb,step+1,i);
	}
}
int main(){
	ll a,b,tmp;
	cin>>a>>b;
	tmp=gcd(a,b);
	a=a/tmp;b=b/tmp;
	while(!flag){
		dfs(a,b,0,0);
		lim++;
	}
	for(ll i=1;i<=len;i++){
		for(ll j=1;j<=lim-1;j++)cout<<an[i][j]<<' ';
		cout<<endl;
	}
}

实在是看不出来有哪里错了..

2022/5/4 17:26
加载中...