想说这个题要是想做出来就必须不干一件事情，那就是不要点开标签。。点开标签看到那些平衡树什么的。。。。
首先，我们要理解这个题的题意。买彩票是什么大家都应该知道吧，一般来说，就是从很多数里面选出来几个，然后系统，额……就是那个有一堆球的机器，弹出来几个球球上的数字就是中奖数字。
对于这个题，我们要是选择的n个数的倒数的和等于一开始的X/Y，不妨设它为t，然后我们进行搜索，这里事先说一下，在进行了常数优化后，AC代码最慢的点要650+。怎么搜索呢，对于这个题，很明显就有了两种思路，一种是朴素的一个个枚举情况，这个应该也是能过，但是剪枝的时候不是很好处理。然后就是从前到后暴力搜索，不是枚举情况，而是根据当前的情况，对搜到的数进行选或不选的抉择。
然后程序应该很容易打出来，而且，很短。。。。但是显而易见，前面说了，常数优化后还要650+，这么一个剪枝没有肯定会T，然后，我们加入一个很常见的可行性剪枝，如果最终减选的数字的最大值还是要大于，额，那个误差。就return，同理，如果减得最小要小于那个误差，也要return。这样以后可以减掉部分搜索。
P.S.误差是因为浮点数计算会有一个非常微小的误差。。。所以必须计算在内，而且，必须非常小。。10e-9与10e-10差了40分。。。
#include#include #include #include #include #define re register#define wc 0.0000000001using namespace std;int n,m;double x,y,s[100001],ans,f[1000001],t;inline void dfs(int st,int to,double tot){ double maxx=tot+s[to+n-st]-s[to]; double minn=tot+s[m]-s[m-n+st]; if(t-maxx>wc||t-minn<-wc) return; if(st>=n) { ans++; return; } dfs(st,to+1,tot); dfs(st+1,to+1,tot+1.0/(to+1)); return;}int main(){ cin>>n>>m>>x>>y; t=x/y; for(re int i=1;i<=m;i++) s[i]=s[i-1]+1.0/i; dfs(0,0,0); cout<