当前位置: 代码迷 >> 综合 >> 集训2020.01.18【NOIP提高组】模拟B 组分析反思(【东莞市选2009】9数字 原子核研究 探险者拉罗 【NOIP2014八校联考第3场第1试10.4】选择困难症)
  详细解决方案

集训2020.01.18【NOIP提高组】模拟B 组分析反思(【东莞市选2009】9数字 原子核研究 探险者拉罗 【NOIP2014八校联考第3场第1试10.4】选择困难症)

热度:22   发布时间:2024-01-25 21:04:58.0

这次比赛打炸了,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方法我可能出现了理解性偏差,会出现重复的情况。正在解决中……