20221106
题目
by George_Plover
NOIP模拟
| 题目 | 期望得分 | 实际得分 |
|---|---|---|
| 二叉树上的询问 | 100 | 20 |
| 追逐 | 100 | 0 |
| 荷塘月色 | 0 | 0 |
| 光华楼 | 0 | 40 |
二叉树上的询问
competing
因为起晚了 \(30\) 分钟，所以打得比较匆忙。第一眼看到这道题的时候其实并没有什么思路，然后就手玩了一下样例。然后就发现二叉树上每个节点的的前序遍历排名其实就是这个节点左边树的大小。很自然地就想到了一个 \(O(mlogn)\) 的做法。从询问的节点开始，不停地往它的父亲跳，每跳一次就统计一次。如果当前节点是其父亲节点的右儿子，就加上该节点父亲的左子树的大小，如果是左儿子，直接加 \(1\) 即可。但这样在遇到叶节点不满的那部分树时会出问题，所以就思考怎么处理这种情况。由于题目中给出的是一颗完全二叉树。所以我就想到从最后一个节点开始不停地往上找它的父亲，然后记录下它们的编号，如果遍历到的节点编号大于所处层被记录下来的编号，就让累加答案时少加一层的节点个数，这样就相当于直接将不满的那一层从统计答案的过程中挖去了，然后再特判最后一个节点是左儿子还是右儿子，是左儿子就使最终答案再减一。貌似就可以了，然后我就去做下一题了。
after
然而我并没有发现，这么做有一个致命的错误。
像这样的二叉树，查询 \(X\) 节点时就会导致计算错误。蓝色路径上的节点就是被打上标记的节点。在计算 \(X\) 节点到其父节点的答案时，会将左子树的大小计算成 \(3\) ，但实际上是 \(2\) 。这样就理所当然的 \(G\) 掉了。事后，和同机房巨佬Michalel·F·Chen讨论时才知道，其实只需要先将它当做满二叉树算，最后再减去多加的就可以了。:（果然我还是太蠢了qwq
追逐
competing
鉴定gcd
快乐地来到 \(T2\) 后，一看上来就是一个柿子，啊，数论不看，然后就看到了 \(gcd\) ，根据以往做题经验，题目中明确提到 \(gcd\) 的题都不用 \(gcd\) ，我毫不犹豫地就开始往质因数那方面思考。
尝试让gcd圆润地离开
首先思考那个 \(gcd\) 怎么转化，毕竟那玩意怎么看怎么不顺眼。将质因数结合进来，很容易就能想到两个数的 \(gcd\) 就是他们共有的质因子的幂次的最小值的乘积，这样我们就只需要维护 \(X,Y\) 的质因子的幂次即可。
处理次方
然后思考 \(X\) 的 \(i\) 次方与单单一个 \(X\) 有什么区别，这也很容易发现， \(X^i\) 中的质因子的幂次就是给 \(X\) 中所有的质因子的幂次乘上了 \(i\) 。
优化求积公式
两个求积公式，效率都达到了 \(O(n^2)\) 了，肯定过不了，考虑如何优化。因为这道题 \(O(nlogn)\) 的效率就是能过的了，所以是可以枚举一个求积公式的。那我们接着思考，怎么将第二个求积公式优化掉。对于每个枚举到的 \(X^i\) 来说。因为我们是在 \(X，Y\) 共有的质因子中取幂次最小的，那对于每个质因子 \(z\) 假设 \(z\) 在 \(X\) 中的幂次为 \(x\) ,在 \(Y\) 中的幂次为 \(y\) ，那对于每个 \(X^i\) 中， \(z\) 的幂次就是 \(x\times i\) 。因为我们是要在 \(X\) 与 \(Y\) 中取幂次更小的，那我们其实就只需要二分 \(c\) 到 \(d\) （然鹅其实根本不需要二分就可以 \(O(1)\) 地求出，后文会讲），在 \(c\) 到 \(d\) 中找到第一个能使 \(y\times j\ge x\times i\) 的 \(j\) ，这样我们实际上要的东西就是 \(j\) 之前的 \(X^i \times X^i \times ...\times X^i\) (共计 \(j\) 个)，和 \(j\) 之后的 \(Y^j \times Y^{j+1} \times ...Y^{d}\) 这个东西的幂次可以用求和公式快速求出，最后再将统计出的幂次乘出来输出即可。大概算下时间复杂度 \(O(\sqrt{n})\) 的质因数分解，可以忽略， \(O(n)\) 的枚举， \(O(logn)\) 的质因数个数再加上根本没必要的二分，整个算法的时间复杂度就是 \(O(nlog^2n)\) 的，卡卡常还是能过的。
然后就非常高兴地去打后面两题的暴力了，这个时候已经只剩不到一个小时了。
after
最后发现中途少乘上了一个东西，还少了个判断，还打挂了点东西，直接狂揽 \(10\) 个 \(RE\) 。
之后改题的时候又去和同机房巨佬Michalel·F·Chen讨论了一下，发现根本不需要二分，就可以 \(O(1)\) 地求出 \(j\) ，因为事实上，对于每个 \(X^i\) 来说，可以将 \(X^i\) 看成常数，然后将 \(z\) 在 \(Y\) 中的幂次看成斜率，要求的 \(j\) 看作 \(x\) 坐标，而我们最后要求的就是直线 \(y=kx\) 与直线 \(y=X^i\) 的交点。直接解方程即可。qwq
荷塘月色
competing
在被 \(T2\) \(AK\) 之后，草草地看了一眼 \(T3\) 感觉没什么思路，就先去打 \(T4\) 的暴力了。打完暴力回来，感觉这道题可以用二维前缀和骗点分下来，就打了一下，结果貌似打崩了一分没有。
after
没想到就一个暴力枚举加双指针。qwq
光华楼
competing
打了个模拟，再用 \(clock()\) 卡了下评测时间后就直接过了。
after
没想到我用时最少的题却拿了最高的分。果然我还是个蒟蒻qwq
结
代码实现能力太差，得多刷刷题提高一下。
时间分配还是有点问题，在 \(t1\) 和 \(t2\) 花了大把时间，导致 \(t3\) \(t4\) 都没什么时间去思考。