获得一手自招信息，竞赛动向

Day1

2016-A     玩具谜题

类型: 模拟     综合难度: 2     考场目标: 100 分

直接模拟即可,想到记录方向就ok.纯粹的送分题,字符串的读入可能是这题唯一难点.

2016-B     天天爱跑步

类型: 图论     综合难度: 6     考场目标: 45 - 100 分     需要掌握:LCA,树上差分

NOIP2016最难的一道题,不少思路继承了NOIP2015年DAY第3题运输计划.

n个点的树m个玩家,对于每个玩家,如果顺着他的路径,记录走到点的时间,总时间复杂度O(nm),而n, m <= 300000,超时严重,也就是说我们不能随着玩家更新每个走过的路径点,最好只记录起点与终点就能完成统计.想到如果不是随动的0,1,2而是固定某个值i,则可以通过差分数组标记整个路径的+i.直线上差分可以参考NOIP2012借教室,树上差分可以参考NOIP2015运输计划.

考虑从u->v路径怎么走,这是最近公共祖先(LCA)问题,路径转化为u向上走到LCA(u,v)再向下走到v.如果i点在路径u->LCA(u,v)上,观察员在w[i]的时刻看到u点出发的玩家,则需w[i] = dep[u] - dep[i],dep[i]表示i点在树种的深度.不妨将上述等式移项变为w[i] + dep[i] = dep[u],那么就把路径上的点每点值增加转化为了记录一个固定值.差分即可处理.同理,如果i点在路径u->LCA(u,v)上,观察员在w[i]的时刻看到u点出发的玩家,则需w[i] + dep[i] = dep[u] - 2 * dep[LCA(u,v)].

求LCA需要掌握模板,树上差分==>每点求子树和==>dfs序分别记录,所以本题不仅思考难度大,而且实现难度也大,已经达到省选标准.

2016-C     换教室

类型: 动态规划     综合难度: 3 - 4     考场目标: 100 分

分析:课是有顺序的,无后效性,可以考虑动态规划

考虑二维DP,f[i][j]表示调整完前i节课,申请j门调整耗费体力的最小期望值.考虑到转移计算耗费体力值时,需了解上节课在哪间教室,所以需要存储第i节课是否申请调整.

故f[i][j][0]表示调整完前i节课,第i节课不申请调整,目前申请了j门调整耗费体力的最小期望值.

f[i][j][1]表示调整完前i节课,第i节课申请调整,目前申请了j门调整耗费体力的最小期望值.

答案就是min(f[n][j][0],f[n][j][1])

转移就比较简单了,期望就是加权平均而已:f[i][j][0] = min(f[i-1][j][0] + w[a0][a1],

f[i][j][0] = min(f[i-1][j][0] + w[a0][a1],       

f[i-1][j][1] + p0 * w[b0][a1] + q0 * w[a0][a1]);

f[i][j][1] = min(f[i-1][j-1][0] + p1 * w[a0][b1] + q1 * w[a0][a1],            

f[i-1][j-1][1] + p0 * p1 * w[b0][b1]          

+ p0 * q1 * w[b0][a1]         

+ p1 * q0 * w[a0][b1]             

+ q0 * q1 * w[a0][a1]);

其中p0表示第i - 1节课换成功的概率,q0表示第i - 1节课没换成功的概率,p1表示第i节课换成功的概率,q1表示第i节课没换成功的概率,w[i][j]表示从第i个教室移动到第j个教室所需要花费的最小体力,所以最开始还需要floyd进行预处理.

初始值:f[i][0][1] = INF,其余值为0.因为循环最开始用到初值f[i][0][0]与f[i][0][1]而f[i][0][1]这个状态不合理所以设为无限大即可.

整体来看,这就是一道加了个期望表达的DP,应该是自NOIP2011年改革以来最简单的第三题.

Day2

2016-D     组合数问题

类型: 递推      综合难度: 2     考场目标: 100 分

每次通过组合数的计算式计算组合式的值耗费时间太多,所以考虑组合数递推公式(杨辉三角)求解每一项,c[i][j] = (c[i-1][j-1] + c[i-1][j]) % k

那如何处理多组查询呢?显然O(tnm)的时间复杂度不足以处理10^4 * 2 * 10^3 * 2 * 10^3这个数据点,思考能否预处理,直接得出指定范围内的解的个数,此时可以通过递推式计算二维前缀和ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + (c[i][j] == 0)

如果做过一定量的题目,这两个递推式一般是见过的,但对于没处理过类似问题的同学来说,作为第一题还是很有挑战的

2016-E     蚯蚓

类型: 单调队列     综合难度: 3     考场目标: 70 - 100 分

本题需要3个关键操作:

1.从蚯蚓群中找到最大的蚯蚓

2.删掉最大蚯蚓,分割为2个新蚯蚓

3.其余蚯蚓都增加q

而这种操作需要做m次,m <= 7*10^6,所以每个操作需要在O(1)或O(logn)的时间完成

最容易解决的是操作3,其余蚯蚓增加q等价于记录增量q,修改这两个蚯蚓的长度为l-q.如果是数组储存蚯蚓,操作1需要O(n)遍历一遍才能得出,操作2只用O(1)的时间,易知如果数组具有单调性,即可在O(1)的时间得到最大值,而加入2个新蚯蚓需要O(logn)的时间维护原本的单调性,也就是说需要加个数据结构维护这种单调性,用STL中的堆或优先队列维护即可,此时可得到80 - 85分.

更进一步,如果原始蚯蚓一定按大小顺序被切,则切完的2段蚯蚓头与尾两个新数列也一定是单调不增的,所以可以维护3个数组,比较3个数组的最大值即为被切的蚯蚓.不再需要维护单调性O(1)即可完成每一次操作.

这道题模拟预计得分40分,加堆优化预计得分80分,而满分算法考察的是学生对问题的分析,能否找准问题的关键点.

2016-F     愤怒的小鸟

类型: 动态规划     综合难度: 4     考场目标: 60 - 100 分

本题实质就是:发射最少的小鸟把所有猪都打掉

n <= 18,非常显然的状态压缩,以二进制01记录状态每个猪有没有被打掉的状态.下文用到位运算的地方较多,不理解的同学首先需要恶补下位运算的知识.

比如如果总共有5只猪,则13应对二进制01101表示第1,3,4只猪被打掉2,5没被打掉的状态.我们可以要求最优的打法中优先把序号靠前的猪打掉,只调换打鸟顺序明显不影响最优解.无后效性,可以动态规划.

f[st]表示打掉小猪状态为st时的最少小鸟数,答案就是f[2^n - 1],即状态st的二进制每一位都是1的情况.

转移方程:如果状态st中第i头猪没被打掉,则

方式一:单独一个小鸟打掉第i头猪

f[st | (1 << i)] = min(f[st | (1 << i)], f[st] + 1);

方式二:一个小鸟同时打掉第i与第j头猪,需要预处理c[i][j]数组,以二进制的形式表示同时打掉第i与第j头猪的小鸟打到的所有小猪状态,1位能打到,0为打不到.

f[st |  c[i][j]] = min(f[st |  c[i][j]], f[st] + 1);

本题如果学过状态压缩并不难想,但结合了二次方程求系数及带入的预处理,位运算和浮点数精度等问题使得编码难度比较高.

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com