今天模拟赛的第三题(又达成了原题考试的成就)。考场的时候由于 T2 调太久这题暴力都没写… 现在依然不会正解于是写了个随机化算法 AC 。

每次随机两个点,然后计算出他们的连线的斜率,每次 $O(n)$ 判断一下选取与这条直线平行的两条直接的答案,随机个次几万次w就过了…

这里可能有个细节问题,也就是说我们每次选出的两个点中可能有不合法的点,实际上影响不大,因为我们可以通过略倾斜直线来取到另一个合法的点。

20181208 - NOI模拟赛

最近准备学科营,平时考的模拟赛准备总结记录一下。这些题解会被分类到 Contest 目录下,可能只会讲笔者会的部分或笔者觉得有用的部分,思路可能会讲完整也可能不会,代码可能会放也可能不会,但题面和题意肯定是不会有的。大概就是这样(

Forest

考虑到每个节点出去只有一个父亲,所以要把修改都集中到自己和自己的父亲上去(而不是遍历自己的孩子)。为了方便维护,我们把原来的 $C_i$ 拆成

$$
C_i = E_{a_i} + (B_i - D_i \times E_i + E_i + \sum E_{ P_j } [ j 是 i 的孩子])
$$

通过简单的 trick 把括号内的东西(假设叫 $F_i$ )放到 $i$ 节点上维护,可以使得 1 、 2 操作的复杂度变为 $O(1)$ ,但 3 操作需要遍历所有节点,复杂度是 $O(n)$ 。考虑优化,把每个节点都开个 multiset (或可删堆),用来存自己的每个孩子的 $F_i$ ,当自己的 $E_i$ 改变时利用自己的 multiset 去更新答案,同时当自己的 $F_i$ 改变时更新父亲的 multiset ,并利用父亲的 multiset 更新答案

Bear

20 分简单爆枚,40 分简单状压。100 分以对角线进行插头 dp ,还没写过。

Juice

考场上用一个乱搞做法 AC 了这题(也依赖于 IOI 赛制)。先枚举答案,对于每个答案进行 check ,方法如下。

先根据答案计算出分出的每个桶的大小 $S$,把给定的每个 $a_i$ 丢进 multiset 里。每次取出一个最小的 $A$,如果 $A > S$ ,那么就把 $A - S$ 丢回去;如果 $A < S$ ,那么就在 set.lower_bound(A) 到 –set.end() 的范围内随机一个迭代器配对。利用合适的随机种子和合适的调参,成功 Accepted。

CF1059E - Split the Tree

一个永远只能在考完后调出 Codeforces 的题的菜鸡厚颜无耻得跑来写题解了。。。

本题要求把树分成的链必须是垂直路径,也就是说不能同时跨越一颗子树的两个根。也就是说每次选中的路径都是到根节点的一串。

所以我们可以通过树上倍增预处理出每个节点 $u$ 如果被选中那么最多可以向上形成长度为 $dp[u]$ 的链。接着跑一遍树上 DP 即可。

预处理时间复杂度 $O(n \log n)$ ,树上 DP 时间复杂度 $O(n)$ 。

貌似因为 D 题比较难调试,做这题的人比较少?反正我这种菜鸡就算考场有时间写了估计也调不出来吧。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×