NOIP2016 DAY1 简要思路

简单看了看NOIP2016的题. 口糊一下自己的想法吧.

描述好乱. 反正就是一群人围成圈, 若干次左走右走问最后到哪.

加加减减取模就好了.

水水水水过.

一棵n个点的树, m条路径, 问对于每个点, 经过本点且起点距离本点为本点点权的路径条数.

\( n, m \leq 3*10^5 \)

我感觉这个题有点难呀. 很有可能是我想复杂了.

把每条路径从lca处拆成两段.

考虑对于每个点的询问.

对于起点到lca这段, 询问就是询问子树里lca深度小于等于当前深度的深度刚好为某个值的路径起点个数.

对于lca到终点这段, 询问就是询问子树里lca深度小于等于当前深度的 (长度-深度) 刚好为某个值的路径终点个数.

然后就成了一个比较简明的数据结构问题.

一种思路是平衡树启发式合并, 但是时间可能会炸.

另一种思路是用dfs序式树链剖分, 每条路径会被拆分为不超过lg个dfs序上的子段. 在路径的每个子段的起点和终点处分别打上标记. 然后对dfs序进行一次扫描即可得出答案. 复杂度比较优.

n节课, v间教室. 每节课有两种教室位置选择, 其中一种是已定的. 你有m次机会申请换掉其中一节课的教室位置, 每个请求有独立的p的概率成功. 教室在一张图上, 求最小总奔波路期望.

\( n, m \leq 10^3, v \leq 3*10^2 \)

个人认为这题比上一题水.

先用floyd处理出任意两间教室间的最短路.

然后用dp.

\( f_{i,j,k} \) 表示前i间教室, 用了j次交换机会, k表示上一次有没有换. 存答案.

转移就是一个概率的算式, 较为简单. 略.

八年来第一次没有在赛场上考noip. 今年题目描述好长好长好长.

题目难度比去年高.

%%%Laekov

Comments