2020-2021:teams:farmer_john:2020牛客暑期多校第一场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第一场 [2020/07/17 17:12] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第一场 [2020/08/07 17:41] (当前版本) jjleo [E.] |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 原题题目和题解：[[.JJLeo:codeforces_round_614_div._2_virtual_participation|F题]]，本题数据范围从$5000$变到$100000$。 | 原题题目和题解：[[.JJLeo:codeforces_round_614_div._2_virtual_participation|F题]]，本题数据范围从$5000$变到$100000$。 | ||
| ====题解==== | ====题解==== | ||
| - | 原题复杂度太高过不了，本题需要把虚树建出来，按$1!,2!, \cdots ,n!$的顺序考虑每个点和上一个点的$\text{LCA}$的位置，用树状数组维护每个质因子的出现个数，$\text{LCA}$对应点就是两个数字将质因子从小到大写出来排列好后的最长公共后缀，可以发现其实就是$(i-1)!$中**$i$的最大质因子**及其后面的部分。距离$i$的长度就是去掉这个后缀剩下的质因子个数，可以用树状数组快速求出，一直向上跳，如果正好跳到某个节点则直接用即可，否则需要新创一个节点，可以发现每出现一个质数就会跳到根节点，因此虚树的树高也是$O(\log n)$的，暴力跳并不会超时，之后再把$i!$对应的节点接到$\text{LCA}$下面即可。总复杂度$O(n \log ^2 n)$，两个$\log$分别是树状数组和分解质因数，强行卡过$1$秒。 | + | 原题复杂度太高过不了，本题需要把虚树建出来，按$1!,2!, \cdots ,n!$的顺序考虑每个点和上一个点的$\text{LCA}$的位置，用树状数组维护每个质因子的出现个数，$\text{LCA}$对应点就是两个数字将质因子从小到大写出来排列好后的最长公共后缀所对应的数字，可以发现其实就是$(i-1)!$中**$i$的最大质因子**及其后面的部分。距离$i$的长度就是去掉这个后缀剩下的质因子个数，可以用树状数组快速求出，一直向上跳，如果正好跳到某个节点则直接用即可，否则需要新创一个节点，可以发现每出现一个质数就会跳到根节点，因此虚树的树高也是$O(\log n)$的，暴力跳并不会超时，之后再把$i!$对应的节点接到$\text{LCA}$下面即可。总复杂度$O(n \log ^2 n)$，两个$\log$分别是树状数组和分解质因数，强行卡过$1$秒。 |
| 这题总节点个数$m$是$10^6$，但是本质上只有$10^5$个点，因此其实可以上述过程只做一次，然后后续再在上述虚树的基础上再建虚树，这样复杂度其实是$(n \log ^ 2n + m \log n)$的，不过既然过了就没必要这么复杂了。 | 这题总节点个数$m$是$10^6$，但是本质上只有$10^5$个点，因此其实可以上述过程只做一次，然后后续再在上述虚树的基础上再建虚树，这样复杂度其实是$(n \log ^ 2n + m \log n)$的，不过既然过了就没必要这么复杂了。 | ||
| =====C.===== | =====C.===== | ||
| - | **solved by** | + | **upsolved by** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| 行 27: | 行 27: | ||
| 答案即为 $BA^{-1}B^T$ [[.2sozx:牛客多校第一天D|证明]] | 答案即为 $BA^{-1}B^T$ [[.2sozx:牛客多校第一天D|证明]] | ||
| =====E.===== | =====E.===== | ||
| - | **solved by** | + | **upsolved by** |
| ====题意==== | ====题意==== | ||
| ====题解==== | ====题解==== | ||
| 行 59: | 行 59: | ||
| 答案为$\dfrac{{(n!})^2}{(2n+1)!}$。 | 答案为$\dfrac{{(n!})^2}{(2n+1)!}$。 | ||
| =====记录===== | =====记录===== | ||
| + | 0min:开局，CSK冲F\\ | ||
| + | 30min:CSK T1 WA2 后AC ，MJX 冲C\\ | ||
| + | 32min:MJX WA后发现自己想的完全错了，ZYF 冲I\\ | ||
| + | 39min:ZYF WA，一起看了看J，CSK推出公式\\ | ||
| + | 54min:CSK AC，之后是漫长的挂机时间\\ | ||
| + | 180min:MJX 冲 I 挂了3次，期间 ZYF 发现 B 是原题改了数据范围，冲 B\\ | ||
| + | 217min:ZYF AC，之后 MJX 继续冲 I\\ | ||
| + | 268min:MJX AC，之后一起冲 H，发现题之前读错了 ZYF 冲 H\\ | ||
| + | 285min:ZYF AC\\ | ||
| + | after:7-14日，黑暗的一天，ZYF疯狂冲A然而无情TLE，CSK接力冲A依然TLE，MJX再接力冲A终于AC，但是都没发现之前的有什么问题，我们仍未知道那天所TLE的代码的原因。 | ||
| =====总结===== | =====总结===== | ||
| + | * ZYF不要因开局睡着而丧失斗志，坚持才是胜利，加油，奥力给！{{:2020-2021:teams:farmer_john:jjleo:奥力给高坚果.jpg?50|}} | ||
| + | * MJX要更好的总结题意，方便交接题目。 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第一场.1594977137.txt.gz · 最后更改: 2020/07/17 17:12 由 jjleo
