BZOJ 1224 [HNOI2002] 彩票

发布于 2017-05-03  215 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1224

题意:人话:求从 1~m 中选 n 个数使得它们的倒数和恰为\(\frac{x}{y}\) 的方案数...


这道题的标签是前缀和真是意义不明啊...... 爆搜是复杂度是\(2^m\).... 不能接受,然而剪枝后可以卡过...

代码中的 mx 表示目前状态能达到的最大值 (即剩下全选尽可能大的),mn 表示目前状态能达到的最小值 (全选尽可能小的),然后判断一下即可...

代码如下:

 


一个非常弱的准退役OIER