TLE 90pts求助
查看原帖
TLE 90pts求助
356003
Moeebius楼主2022/5/8 18:36

RT,调了好久还是没能卡常成功

/*
* @ Author: Xiaohuba
* @ Usage: OI Problem
* @ Language: C++
*/
#include<bits/stdc++.h>
using namespace std;

/* ---File Head Begin--- */
namespace Xiaohuba_File_Head
{
	//def
	#define ll long long
	#define lll __int128
	#define pii pair<int,int>
	#define mkp make_pair
	#define vi vector<int>
	#define vs vector<string>
	#define viit vector<int>::iterator
	#define pb push_back
	#define il inline 
	#define pch putchar
	#define gch getchar
	#define Endl putchar('\n')
	#define Space putchar(' ')
	#define For(x,st,ed) for(register int x=(st),END=(ed);x<=END;++x)
	#define ForDown(x,st,ed) for(register int x=(st),END=(ed);x>=END;--x)
	#define sq(x) (x*x)
	#define Set(a,b) memset(a,b,sizeof(a))
	#define Cpy(a,b) memcpy(a,b,sizeof(a))
	#define PRIME_MOD 100000007ll
	#ifdef ONLINE_JUDGE
		#define log2 __lg
		#define gcd __gcd
	#endif
	//io
	template <typename T>
	il void read(T & tmp){ tmp=0;char c=getchar();bool flg=0;while(!isdigit(c)) flg=c=='-',c=getchar();while(isdigit(c)) tmp=(tmp<<3)+(tmp<<1)+c-'0',c=getchar();if(flg) tmp*=-1; }
	template <typename T, typename... Args>
	il void read(T &tmp, Args &...tmps){ read(tmp);read(tmps...); }
	template <typename T>
	il void __write(const T &x){ if(x==0) return;__write(x/10);putchar(x%10+'0'); }
	template <typename T>
	il void write(const T &x){ if(x==0) putchar('0');if(x<0) putchar('-');__write((x<0 ? -x : x)); }
	template <typename T>
	il void write_with_space(const T &x){ write(x);Space; }
	template <typename T>
	il void write_with_endl(const T &x){ write(x);Endl; }
	template <typename T, typename... Args>
	il void write_with_space(const T &x, const Args &...y){ write_with_space(x);write_with_space(y...); }
	il void __getline(istream & istr, string & str){ getline(istr,str);if(*(str.end()-1)=='\r') str.erase(str.end()-1); } 
	#define getline __getline
};
using namespace Xiaohuba_File_Head;
/* ---File Head End--- */

#undef lll
#define lll int
int gcd(lll x, lll y)
{
	return y==0 ? x : gcd(y,x%y);
}
il int lcm(lll x, lll y)
{
	return x/gcd(x,y)*y;
}
struct Frac
{
	int a,b;
	Frac() : a(0),b(1) {}
	Frac(lll __a, lll __b) : a(__a),b(__b) {check();}
	Frac(lll __a) : a(__a),b(1) {}
	il void check()
	{
		lll div=gcd(a,b);
		if(div) a/=div,b/=div;
	}
} ;
bool operator== (Frac  lhs, Frac  rhs)
{
	lhs.check(),rhs.check();
	return lhs.a==rhs.a && lhs.b==rhs.b;
}
bool operator< (Frac  lhs, Frac  rhs)
{
	lhs.check(),rhs.check();
	return lhs.a*rhs.b<lhs.b*rhs.a;
}
bool operator> (Frac lhs, Frac rhs)
{
	return !(lhs<rhs) && !(lhs==rhs);
}
void operator+= (Frac & lhs, const Frac & rhs)
{
	lll new_b=lcm(lhs.b,rhs.b);
	lhs.a*=new_b/lhs.b;
	lhs.b=new_b;
	lhs.a+=rhs.a*(new_b/rhs.b);
	lhs.check();
	//cout<<"hhh "<<lhs<<endl;
}
void operator-= (Frac & lhs, const Frac & rhs)
{
	lll new_b=lcm(lhs.b,rhs.b);
	lhs.a*=new_b/lhs.b;
	lhs.b=new_b;
	lhs.a-=rhs.a*(new_b/rhs.b);
	lhs.check();
	//cout<<"hhh "<<lhs<<endl;
}
Frac operator+ (const Frac & lhs, const Frac & rhs)
{
	Frac res=lhs;
	res+=rhs;
	res.check();
	return res;
}
Frac operator- (const Frac & lhs, const Frac & rhs)
{
	Frac res=lhs;
	res-=rhs;
	res.check();
	return res;
}
Frac operator/ (const Frac & lhs, const Frac & rhs)
{
	Frac res;
	res.a=lhs.a*rhs.b;
	res.b=lhs.b*rhs.a;
	res.check();
	return res;
}

Frac x;
int len=0,ans[1005],tmp[1005];
Frac sum;

il void dfs(const int & lim, const int & cnt, const int & pre)
{
	//cout<<cnt<<endl;
	if(cnt>lim || sum>x)
		return;
	if(cnt==lim)
	{
		//cout<<lim<<' '<<cnt<<' '<<sum.a<<' '<<sum.b<<' '<<(x-sum).a<<' '<<(x-sum).b<<endl;
		if((x-sum).a==1 && (x-sum).b<=1e7 && (x-sum).b>pre && (x-sum).b<ans[lim])
		{
				For(i,1,lim-1) ans[i]=tmp[i];
				ans[lim]=(x-sum).b;
		}
		return;
	}
	For(i,pre+1,min(ans[len],(int)1e7))
	{
		//cout<<lim<<' '<<cnt<<' '<<i<<endl;
		if(Frac(lim-cnt+1,i)<(x-sum)) return;
		tmp[cnt]=i;
		sum+=Frac(1,i);
		dfs(lim,cnt+1,i);
		sum-=Frac(1,i);
	}
}

signed main()
{
	int a,b;
	read(a,b);
	x=Frac(a,b);
	while(1)
	{
		ans[++len]=1e7+1;
		dfs(len,1,0);
		if(ans[len] != 1e7+1)
		{
			For(i,1,len) printf("%d ",ans[i]);
			break;
		}
	}
	return 0;
}
2022/5/8 18:36
加载中...