1.机器猫与猫粮
题目大意
给定n，输入数组a[n]，求一共有多少个子集使该子集的和位于[l,r]之间
数据分析
测试点 n 1-5 1<=n<=5 6-10 1<=n<=10 11-15 1<=n<=20 16-25 1<=n<=40 容易想到，当n<=20时，直接枚举子集即可，也就是60分做法 那n<=40时呢？ 其实本题正解是dp 不过没学也没关系qwq
思路
可以通过将数组分成两半来枚举
把前一半的每个子集之和存在sum1数组中，后一半存在sum2中
然后sort(sum1)，sort(sum2)(升序)再扫一遍sum1，用upper_bound-1找到最大的不大于r的数据的下标存在id中
再for(int i=1;i<=id;i++)
用lower_bound和upper_bound找到sum2数组中>（l-sum1[i]） && <(r-sum1[i])的数据的下标范围
左下标存在id1中，右下标存在id2中
if(id2>=id1){
ans+=id2-id1+1;
}
然后再特判一下如果sum1[i]本身就大于l,ans++;
100分代码
2.制定新的税法
题目大意
从数组a[n]和b[n]中，找出x1,x2,x3.......xk
使(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])的值最大
有special judge(误差应小于1e-4)
数据分析
对于100%的数据，1<=n<=1e5
也就是说本题的时间复杂度应该优化到O(n*sqrt(n))或O(nlogn);
也就容易想到二分答案；
思路分析
关键在于check函数怎么写……
观察一下这个式子(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])
让它=mid
则如果check成功：(a[x1]+a[x2]+.......+a[xk])/(b[x1]+b[x2]+......b[xk])>=mid;
移项得a[x1]+a[x2]+a[x3]+……+a[xk]>=mid(b[x1]+b[x2]+……+b[xk])
展开得a[x1]+a[x2]+a[x3]+……+a[xk]>=midb[x1]+midb[x2]+……midb[xk];
也就是a[x1]-midb[x1]+a[x2]-midb[x2]+……+a[xk]-midb[xk]>=0;
那就很简单了，只要二分mid,再把1-n扫一遍，把每一个a[i]-mid*b[i]存入c[i]中
然后sort一下(升序)，取c[]数组中的前k项
看这个式子a[x1]-midb[x1]+a[x2]-midb[x2]+……+a[xk]-mid*b[xk]>=0是否成立即可
注：由于是小数二分，所以要注意二分的写法
100昏代码
3.德州扑克
对于本题，最直接的方法就是模拟算牌力的过程
牌力由大到小依次判断，如果符合要求直接break
数据分析
测试点 扑克牌情况 手牌组合情况 [1,5] 扑克牌只包含一种花色,且不包含 A 保证不使用手牌最强 [6,10] 扑克牌只包含一种花色 保证不使用手牌最强 [11,15] 扑克牌不包含 A ,且不包含 「顺子」 无限制 [16,20] 随机生成，等概率选取 无限制 [[21,25] 无限制 无限制 可见，拿到部分分数还是比较容易的，只要判断几次即可 对于前10个数据点，直接扫一遍牌河即可 对于10-15数据点，我们无需考虑a的情况 对于16-20数据点，因为是等概率选取，所以不会有特别阴间的数据，正常写也可以拿分 但是本题想要拿到全部分数非常考验代码能力
思路整理
可以想到，对于所有的扑克牌，我们应该统计他们的花色和点数。
然后对点数进p[]进行排序
花色存入c[]数组里H，S，C，D 表示为 0,1,2,3
判断是否有的c[x]==5即可
参考代码
4.青蛙跳荷叶
这个题目不太好解释，建议先读完题再看
数据
对于1-5数据点，y1,y2在x不同两边
则直接扫一遍(y1-y2)的所有数据的差值每次更新最大值即可（假设y1<y2），20分
对于1-20数据点，1<=n<=1e5
又看到最大值最小，想到二分答案，80分
但是对于21-25数据点，n<=5*1e6
那O(nlogn)肯定是过不了的
只能是O(n);
是的，正解是贪心思想，只要想到怎么贪就简单了
思路
对于y1,y2在x同边的情况，假设y1离x更近
首先直接忽略比y2还远的点 和 x另一侧的点，因为对答案没有贡献
y1-y2中间的点肯定是交给y2比较好
扫完之后让y2离y1差1,（比y1远）
通过简单推导可得，一定是隔一个跳一下最好
因为如果离一个落脚点较近的青蛙跳了，
则另一个青蛙下一次就要隔2个跳一下，这个值一定是比隔一个跳一下大的
就会使最大值更大
详细的证明过程还请读者自行思考
还是不懂的看代码注释
最后贴上AC代码
