2020牛客暑期多校第一场

比赛链接

upsolved by 2sozx JJLeo Bazoka13

设函数 $B(t_1t_2 \cdots t_k)=b_1b_2\cdots b_k$ 其中 $b_i = \min(j-i)(b_i == b_j)(j<i)$，如果不存在则 $b_i=0$ 。现在给定字符串 $S$ ，求 $S$ 的每个后缀的 $B$ 函数的排序

令 $c_i = \min(j-i)(c_i == c_j)(j>i)$，如果不存在则令 $c_i=n+i$ ,对 $c$ 用后缀数组排序，反向输出即可。
证明http://www.stringology.org/event/2008/p08.html

solved by JJLeo

原题题目和题解：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$秒。

这题总节点个数$m$是$10^6$，但是本质上只有$10^5$个点，因此其实可以上述过程只做一次，然后后续再在上述虚树的基础上再建虚树，这样复杂度其实是$(n \log ^ 2n + m \log n)$的，不过既然过了就没必要这么复杂了。

upsolved by

upsolved by 2sozx

给定一个 $n\times n$ 的正定二次型 $A$ 以及 $1\times n$ 的 $B$，找到 $(x_1,x_2,\cdots,x_n)$ 满足 $X^T A X \le 1$ 并且使得 $BX^T$ 最大，求最大值的平方。$n\le200$

答案即为 $BA^{-1}B^T$ 证明

upsolved by

solved by Bazoka13

给定两个字符串，比较其无限循环形成字符串的大小

直接取长度的2倍比较即可

solved by

solved by JJLeo

给出一个带费用的网络流，多次询问当所有边容量设为$x(x<1)$时，从源点输送$1$容量到汇点的最小费用。

先按容量为$1$用$\text{EK}$费用流跑一遍，然后一条条增广路套新的容量算即可。

solved by 2sozx

给定一个 $n$ 个结点 $m$ 条边的无向图，问是否可以删除若干条边使得最终每个点的度数为要求的度数 $d_i$。 $1 \le n \le 50,1 \le m \le 100,1 \le d_i \le 2$。多组数据，无重边和自环。

如果存在点的度数小于目标度数一定不存在一种删边方式，特判即可。令 $du_i$ 为未删边时点 $i$ 的度数，对于每个点拆成 $du_i-d_i$ 个点。对于每条边拆成两个点，将其中一个点向这条边所连的一个点所拆的所有点连边，另一个点与这条边所连的另一个点所拆的所有点连边，并将每条边所拆的两个点连边。对这个图进行一般图匹配，如果存在完美匹配则有一种删边方式满足条件，否则不存在。

solved by Bazoka13 JJLeo

求定积分$\int_{0}^{1}\left(x-x^{2}\right)^{n} \mathrm{d} x$，对$998244353$取模。

答案为$\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不要因开局睡着而丧失斗志，坚持才是胜利，加油，奥力给！
• MJX要更好的总结题意，方便交接题目。