T1.turnover(营业额统计)

题意:自行百度,省选题
分析:这种只需要找前驱后继的数据结构题,实在犯不着手写Splay,SegmentTree之类的玩意,一个set搞定,开了O2跑得飞起,不开依旧稳稳的。


T2.Promotion(商品推销)

题意:不停给你一些数,找到当前最大和最小的数,“答案”加上他们的差,然后删除他们。最后输出“答案“即可。
分析:这种只需要找最大最小的数据结构题,实在犯不着手写Splay,SegmentTree之类的玩意,一个map搞定,开了O2跑得飞起,不开好像很危险,但不会超时。


T3.money(彩票问题)

题意:给定1-M的数字,求其中选出不同的N个使他们的倒数和为(X/Y)的方案有几种。(M<=50;N<=10;X,Y<=100)
分析:很显然的搜索,但是需要强效的剪枝:
首先,我们从倒数大的数往小的数搜索。
设:当前正在决策x是否选择,已经选择了k个数字,倒数和为s,sum[i]表示第i到m的倒数和。
1.$ X/Y-s>(sum[x]+sum[x+(n-k)])$时剪枝,意思是如果以后全选最大数都不能达到X/Y时剪枝
2.$ X/Y-s<(sum[m-(n-k)+1]) $时剪枝,意思是如果以后全选最小数都会比X/Y大时剪枝
有了这两个剪枝,再使用long double,并将eps设为1e-10~1e-12就可以AC了(1e-9会WA)。


T4.game(数字游戏)

题意:给你几个数字(2~20),两个人轮流选。每选择一个数x,会出现以下效果:x和之前任何一个被选的数y组成的ax+by不可被选(0<=x,y)
求当前局面先手选哪个才可以100%使对方最后无数可选。
分析:注意到状态数十分的少,(2^19),所以使用状态压缩Dp.
我们需要先预处理出每个状态中1的个数(lowbit),然后预处理每种状态去掉一个1后转移到哪种状态(去掉一个1后有些数不能选,故相当于去掉很多数)


T5.windoors(windoors安装密码)

题意:给定一些字符串,忽略掉其中长度不为25,出现了非字母的字符串。然后求其中出现最多的是哪一个。如果有多个一样多输出0。
分析:把字符串都hash一下就太棒了。