20181211 - NOI模拟赛

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分,最多有 4320 种状态,我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分,相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上,计算割的价值就是一边的点的权值的异或和。考虑贪心,把点按照权值从大到小排序,利用线性基维护会不会产生 $0$ ,不会就加上价值,否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列,这样每次操作最多影响十棵树。树套树(树状数组套权值线段树)维护一个后缀高度大于指定值的 dp 值的最大值,每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

20181210 - NOI模拟赛

T3 难度并不大,但是由于时间分配问题 + 出题人数据有锅必须输出行末空格否则 WA 导致本来会做的 T3 没有 AC 。

迷路

对于每一个点,建出最短路树,对于每一条非树边,如果他的两个节点在根节点的不同子树内,那么可以对答案产生贡献。

宝藏

类欧优化的数学题,不会。

蛋糕

THUPC 原题的强化版,由 $4$ 维变成 $n$ 维。每一维变成一个多项式分治 NTT 即可。

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。

Your browser is out-of-date!

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

×