大家都说去年的NOIP比较简单，Day1的3道题做下来，感觉确实挺水，不过必须要细心才能做对。
T1 生活大爆炸版石头剪刀布
一道水模拟，按照神犇们的话来说，就是考你会不会编程，所以就不多说了，弄张出拳情况的胜负表，O(n)模拟下去就行了。
代码在此。
T2 联合权值
乍一眼看不会做，等到看输入格式的时候才发现保证n-1条边（话说这和直接说给出一棵树有区别吗，绕来绕去有什么意思啊
）。发现是棵树以后，T2就变成大水题了。设Sum为要求的权值和，Max则为最大值。随便选一个节点作为根进行DFS，DFS到每个节点时，Sum加上其兄弟节点及祖父节点的权值和（因为是无序点对，祖父节点的权值和要加两遍，而兄弟节点的话会在DFS到兄弟节点时算进去）乘以该节点的权值，Max则用其兄弟节点和祖父节点的最大权值乘以该节点的权值来更新。
上面这些东西是可以做到O(n)实现的，只要DFS时计算每个节点的子节点和父节点的权值和、最大值、次大值就行了。
还有就是不要忘记对权值和取模。
代码在此。
T3 飞扬的小鸟
一看就知道要DP，这题应该说是完全背包的变形。
设$f_{i,j}$为小鸟到达第i列第j行的最少点击次数，$lb_i$，$ub_i$分别为小鸟在第i列可以到达的最低和最高高度，x和y的含义和题目描述相同。
首先赋初值：
$f_{i,j}=\inf\,\left( {1 \leq i \leq n ,1 \leq j \leq m} \right)$
$f_{0,j}=\inf\,\left( {1 \leq j \leq m} \right)$
然后更新上升的情况：
$f_{i,\min\left(j+x_{i-1}\ ,m\right)}=\min\left(f_{i,\min\left(j+x_{i-1}\ ,m\right)},f_{i-1,j}\right)$
$\left( {1 \leq i \leq n,lb_{i-1} \leq j \leq ub_{i-1}} \right)$
$f_{i,\min\left(j+x_{i-1}\ ,m\right)}=\min\left(f_{i,\min\left(j+x_{i-1}\ ,m\right)},f_{i,j}\right)\,\left( {1 \leq i \leq n,1 \leq j \leq m} \right)$
并更新下降的情况（注意一定要该列上升情况更新完了才能更新下降的，否则会把既上升又下降的情况算进去）：
$f_{i,j}=\min\left(f_{i,j},f_{i-1,j+y_{i-1}}\right)\,\left( {lb_i \leq j \leq ub_i,lb_{i-1} \leq j+y_{i-1} \leq ub_{i-1}} \right)$
这样就做完了。
代码在此。
评论 (0)
