三个半小时五道题,CY说考的就是心理素质...
考试策略
做题顺序:T5->T3->T1->T2->T4
T5是哈希水题,花30分钟搞定,T3是一道搜索,花了30分钟,不过剪枝力度不够就挂了QAQ,T1考场花1h手打splay(QAQ),T2就花40分钟调对了那个set(QAQ),然后放弃了T4,花了半个小时检查。
经验和教训
1.考试时合理选择做的题目很重要,给每道题合理分配的时间也很重要。
2.要好好学习stl(QAQ)
3.学会检查与放弃,要学会考虑特殊情况

T1

期望得分:100 实际得分:80
错误原因:未知,两个数据有问题,但是改了数据后那两个还是TLE,或许是因为没有考虑负数。
题目描述
Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况:
该天的最小波动值
当最小波动值越大时,就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
数据范围:n小于等于32767,ai小于等于1000000,答案保证int存的下
题目分析
这是一道splay裸题。
这是一道treap裸题。
然而这题可以用set水过。
用set保存后二分查找即可,注意特判没有前驱和后继的情况。
然后用s.lower_bound(x)会比lower_bound(s.begin(),s.end(),x)快那么一些。
代码
splay版:

set版:

T2

期望得分:100 实际得分:100
题目描述
Great Bytelandish的超级市场网络请你编写一个程序模拟促销商品的成本费用(simulating costs of the promotion being prepared)。推销商品要遵守以下规则:
1. 想参与促销的顾客在自己的帐单上写下个人信息,然后将票据投入一个特制的投票箱中。
2. 促销期间,每天结束后,有2张票据将被取出——消费金额最大的和最小的两张账单。消费金额最大的那位顾客得到的奖品价值等于取出的2张账单的差额。
3. 为了避免多次得奖,所有取出的账单将不再放回箱中,其余的票继续参加促销活动。
由于商场的顾客特别多,所以每天投票箱中都至少有2张账单。你的任务是计算在促销期间,商家一共要送出多少前的礼品。
数据范围
第一行是一个整数n,1<=n<=5000,表示促销活动的持续时间。接下来有n行,每行有一系列的非负整数,每行的第一个数k,0<=k<=10^5,表示这天的新增的账单数目。
其后k个数表示各个消费金额(不大于10^6)。所有的投入箱中的账单数目不会超过10^6。
题目分析
本来也觉得是用splay的,结果发现要回收垃圾,然而我不会啊,于是我想了想,消费金额不大于10^6?那不就可以用set水了吗?10^6嘛,开个数组记录一下每个元素出现了多少次即可。
代码

T3

期望得分:30 实际得分:20
错误原因:没有想到良好的剪枝方法,所以TLE了。
题目描述
某地发行一套彩票。彩票上写有1到M这M个自然数。彩民可以在这M个数中任意选取N个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。
每次抽奖将抽出两个自然数X和Y。如果某人拿到的彩票上,所选N个自然数的倒数和,恰好等于X/Y,则他将获得一个纪念品。
已知抽奖结果X和Y。现在的问题是,必须准备多少纪念品,才能保证支付所有获奖者的奖品。
数据范围
1≤X, Y≤100,1≤N≤10,1≤M≤50。
解题思路
搜索+剪枝
一开始写的时候也是贪心剪枝,而且是通分比较而不是用double,可为什么TLE的那么惨呢?
我们来算一笔账:
$$2^{50}=1125899906842624$$
$$50^{10}=97656250000000000$$
好吧,我知道了。
比起枚举下一个选的数是什么(傻逼的我考场上打的),不如枚举每一个数选还是不选。
然后加剪枝:
1.剩下的可以取的数里面取尽可能小的,都小于了x/y,返回。
2.剩下的可以取的数里面取尽可能大的,都大于了x/y,返回。
3.剩下的数不够取了,返回。
就可以过了。
代码

T4

期望得分:10 实际得分:10
错误原因:感觉此题思维难度较高,没有时间做了,于是输出“0”
题目描述
CHRISTIANE和MATTHIAS正在玩一个新游戏---数字游戏,游戏规则是:CHRISTIANE和MATTHIAS轮流选择大于或等于2的正整数,所选择的整数必须满足下列规则:
一个整数被一个玩者选择后,那么这个整数及它的倍数不能被(以后的任何玩者)选择
已被选择的任何2个整数或这两个整数的倍数之和不能被(以后的任何玩者)选择
为了简化题目,要求玩者所选择的整数不大于20
第1个没有整数选择的玩者就是失败者,而另一个玩者就是赢家。
下面是一种玩法:MATTHIAS首先选择4,那么CHRISTIANE就不能选择4,8,12,16,20等整数,假设CHRISTIANE选择3,那么3,6,9,15,18又不能选择,同时7(=3+4),10(=2 *3+4),13(=3*3+4),19(=3*5+4),11(=3+2*4),14(=2*3+2*4),17(=3*3+2*4)等整数不能选择,那么就只留下2和5可以选择,现在MATTHIAS选择2,由于5=2+3,那么CHRISTIANE就没有整数可选择,从而MATTHIAS就是赢家。
现在他们已经玩了几轮了,给出游戏残局状态(保证合法),求必胜策略。
题目分析
只有20个数...状压如何?
对于每一个残局状态,先手只有两种情况:必胜和必败。如果对于某一种策略,可以使得后手必败,则先手必胜。如果找不到这种策略,则必败。
那么我们可以进行状压+记忆化搜索,对于选了某个数后就不可行的数,可以在20 * 20的时间复杂度里很快地搞出来(具体看代码)
代码

T5

期望得分:100 实际得分:100
题目描述
MICROWIN公司发布了新版本的操作系统——Windoors。虽然这个操作系统性能优越,运行稳定,价格低廉,简单易用,但是销售状况并不乐观。经过国际侦探秘密调查和取证,发现了一个人人都知道的问题。绝大部分用户选择了“性价比”更高的盗版软件……
MICROWIN公司为了夺回该操作系统的市场,通过网络秘密调用使用者信息,搜集了几乎所有Windoors使用者的安装密码。操作系统在安装过程中,应由用户输入唯一的安装密码才能被安装成功并且使用。正版用户都有自己唯一的一组安装密码,而盗版用户则使用了相同的安装密码。依据这一特征,请你帮助MICROWIN公司找到盗版用户使用的安装密码。这样,MICROWIN公司就可以终止所有使用这个密码的Windoors用户的使用权。
密码的规范:每组有效的密码是一行由二十五个字符组成的字符序列,且均由字母组成。如:I L O V E N K A C M I L O V E F R I E N D S H I P。注意:字母是大小写不敏感的,也就是说上面的密码也可以写成:I l o v e N k A c M i L o V e F r I E N d S h I p。
由于网络传输错误和其他不可预知的故障,任何不符合密码规范的字符序列均不能算做密码,并且该字符序列忽略不记。而盗版用户的密码则为出现次数最多的密码。
数据范围:1<= n <= 10000
题目分析:裸哈希。我用的SDBM_hash
代码