|
CSP-S 2019第二轮第二试昨天上午正式结束了，赛后仔细拜读了DAY2的三个题目，难！但也是明年NOI选手不错的试炼机会，高分选手大概率也是明年NOI赛场上的选手。 第一题：Emiya 家今天的饭，比较难的动态规划 第二题：划分，动态规划，高精度，单调队列 第三题：树的重心，dfs序，线段树 以下代码均在oitiku测试，第一题Emiya 家今天的饭，O(n^2m)的算法仅得到84分，超时了4个点，理论上应该是可以通过的：）第二题划分，由于数据太大，写了高精度，写的不是太好，最后三个点在oitiku上MLE了，仅得到88分，之后再来改进：）第三题仅写了一下大致想法，往后再来补代码，终究还是已经老了。 CSP-S 2019 D2T1 Emiya 家今天的饭 思路：容斥，方案计数，对998, 244, 353取余数，已经在预示着这题是动态规划了。先考虑无限制情况下，显然是一个普及组难度的dp问题，然后考虑k/2的限制，我们可以从总的方案中减去不符合k/2限制的方案数即可。 代码如下： CSP-S 2019 D2T2 划分 思路：根据数据规模显然是要一个O(n)的算法，粗略的就是先贪心，然后典型的序列型动态规划。dp一下n^2，必须使用单调队列优化至O(n)。最后由于数据太大，需要用高精度或者别的取巧的方法优化一下，我们这里使用传统的高精度来写一下：）
CSP-S D2T3 树的重心
思考： https:///problemset/problem/686/D，恰好比赛前跟同学们也讨论过子树重心的问题。 树的问题的确可以深挖很多有趣的性质，这也是我比较喜欢树上的问题的一些原因。这可能也是为什么树的题目出那么多的原因之一吧。逆向思维一下，如果这点是树的重心，那么一定是删除size最大的子树里面的边。本质dfs序，然后用线段树维护即可。 2019赛季告一段落，高潮已过，停课冲刺的同学们该调整心情回归课堂了，冲刺明年NOI的同学，革命尚未成功，同志仍需努力！ 每一位同学都值得为这次CSP-J/S赛写一个总结，心得，感悟，亦或者是回顾自己的学习C++/算法竞赛、OI的历程。 灿烂的明天正在等着你们！
|
|
|
