这次比赛打炸了,67.5分,36名,垫底~~~最近我变水了,突然智商下降,再也找不到以前的感觉,陷入小低谷……
T1:【东莞市选2009】9数字,很简单的一道搜索题目。没想到比赛时居然打崩了,把枚举的范围打小了,答案错误37.5。比赛时没来得及检查,也促成了这一事故。总结:以后比赛无论题打没打完,最后15分钟一定要耐心检查。
T2:【东莞市选2009】原子核研究,比赛时,越看越像数据结构,这题的最关键之处在于最小的质量差怎么解决,如果换作是最小值最大值那么人人都能切,打个线段树就解决的问题,于是比赛时想质量不大于100000的正整数,可以每一个质量的原子核都开一个点,那关键就在于怎么维护最小差值了,但是脑子却又卡死了,并没有结果,果断放弃,最后匆匆忙忙打了个最暴力的暴力,那了37.5分。正解:事实证明,我比赛时那很快就被我kill掉的思想没错。
对于每一个质量原子核,维护三个值——max,min,mxf(表示最小差值),那么对于每一个质量为x的点的最小差值,可以由
一、l~x-1的点中存在的最大的质量与x+1~r的点中存在的最小的质量的差值
二、1~x-1的点中存在的最大的质量与当前点的质量(如果存在)的差值
三、x+1~r的点中存在的最大的质量与当前点的质量(如果存在)的差值
更新。
总结:对于某些题,我们可以将之转换(对于这题可以转换为求最大/小值),然后通过转换后的出的结果得到我们最终要求的结果。
T3:【东莞市选2009】探险者拉罗 ,这题,比赛时第一眼看上去想一道BFS水题,但仔细一想,却又显得有点艰难——状态太多了,比赛时想到的记录状态F[1..100 n][1..100 m][0..16 g][0..200],但是如果采用这种,会出现错误,一个藏金点被多次经过只算一个,那么,我就尝试加一维状压来解决,但显然会空超,于是放弃,比赛时状压DP在我脑子里一闪而过。正解:被我kill掉的状压DP,f[s][i][t],s表示当前经过了哪些点,t表示潜行的时间,当前在i这个点,f表示藏金点数。首先用某算法(如dijk求出两两点之间的最短距离),然后就是状压DP了。总结:对于一些较复杂的看起来想BFS的“迷宫”题目,可以对其中的某个状态用状压DP解决,特别是特别小的情况。
T4:【NOIP2014八校联考第3场第1试10.4】选择困难症 比赛时以为这题要用什么数据结构,于是果断放弃,打了个排序暴力。正解:题解给出了两个AC方法——1、堆heap 2、第k短路,同学们还有一种做法3、二分+搜索(剪枝)但是比赛完实现的过程发现1方法我可能出现了理解性偏差,会出现重复的情况。正在解决中……