排位赛#13题解

排位赛 #13 题解写在前面难了好多！第四题提交 2 次才 AC，呜呜呜，我菜得模拟都不会了。个人评分：红红黄黄黄绿蓝紫。T1年龄分为今年之前的和今年之后的，直接处理比较麻烦。不妨将出生年移到今年，相应的下一场流星的时间也要修改，即 E←(E+B) mod 50,B←0E\gets(E+B)\bmod 50,B\gets 0E←(E+B)mod50,B←0。然后把寿命的起点移到下一场流星，也就是 L←L−E,E←0L\gets L-E,E\gets 0L←L−E,E←0。最后的答案当然就是 max⁡{0,⌊l50⌋+1}\max\{0,\lfloor\frac l{50}\rfloor+1\}max{0,⌊50l ⌋+1}。注意多测。T2因为这是一道不卡时间的字符串处理，所以我们可以使用 Python 解题。注意特判越界。T3首先是无解的情况：N≤KN\leq KN≤K，因为这样可以直接跳过去。排除这种情况，我们考虑如何求出人数。发现“在每个长度 K+1K+1K+1 的连续区间内都有至少 PPP 个 TNT”是“至少 PPP 人可以通过”的充分必要条件，否则将不会有足够的 TNT 支撑玩家通过。因此，我们求出每一个长 K+1K+1K+1 的区间中 TNT 的数量，取最小值，这就是最多能成功通过 TNT 路径的玩家人数。求数量的过程可以选择滑动窗口或前缀和，时空复杂度 Θ(n)\Theta(n)Θ(n)。T4典中典之，大模拟。。。特别坑！我们考虑把每一个牌用一个结构体存起来。存放点数时，我们按序用 map 映射点数，方便排序。然后，我们将牌按照第一点数，第二花色的顺序排序。最后按题意由优先级高到低判断——先判断三种顺子，如果不是顺子，就在桶排序后按照点数出现次数判断牌型。大坑：五张牌相同属于 High Card（高牌），而不是其它奇奇怪怪的牌型！被坑了一次提交23333。代码可能比较抽象，凑合着看吧。T5如果 T4 是大模拟，这题就是小模拟。加一条边最多在两边各加一个小正方形，判断两边的正方形四边是不是都被加了即可。可以用简单的位运算技巧方便判断。注意分类讨论。T6直接看比较麻烦，因为答案似乎被两个维度所限制。但是我们观察式子：∑i=1n((∣xi−x∣+∣yi−y∣)×ϵi)\sum_{i=1}^n((\left|x_i-x\right|+\left|y_i-y\right|)\times\epsilon_i) i=1∑n ((∣xi −x∣+∣yi −y∣)×ϵi )可以直接拆开：(∑i=1n(∣xi−x∣×ϵi))+(∑i=1n(∣yi−y∣×ϵi))\left(\sum_{i=1}^n(\left|x_i-x\right|\times\epsilon_i)\right)+\left(\sum_{i=1}^n(\left|y_i-y\right|\times\epsilon_i)\right) (i=1∑n (∣xi −x∣×ϵi ))+(i=1∑n (∣yi −y∣×ϵi ))要使其最小，就要使加号左右最小，而两边均只关于 xxx 和 yyy。权值 ϵi\epsilon_iϵi 很碍眼，由于 ϵi\epsilon_iϵi 不大，不妨把每一个 (xi,yi,ϵi)(x_i,y_i,\epsilon_i)(xi ,yi ,ϵi ) 拆分成 ϵi\epsilon_iϵi 个 (xi,yi)(x_i,y_i)(xi ,yi )。设拆分后有 mmm 对坐标，则上式可改写为：(∑i=1m∣xi−x∣)+(∑i=1m∣yi−y∣)\left(\sum_{i=1}^m\left|x_i-x\right|\right)+\left(\sum_{i=1}^m\left|y_i-y\right|\right) (i=1∑m ∣xi −x∣)+(i=1∑m ∣yi −y∣)要使加号左边最小，xxx 应该取什么呢？由绝对值性质得：∣x−xi∣+∣x−xn−i+1∣≥∣xi−xm−i+1∣\left|x-x_i\right|+\left|x-x_{n-i+1}\right|\geq\left|x_i-x_{m-i+1}\right| ∣x−xi ∣+∣x−xn−i+1 ∣≥∣xi −xm−i+1 ∣代入 i=1,2,⋯ ,ni=1,2,\cdots,ni=1,2,⋯,n 得{∣x−x1∣+∣x−xm∣≥∣x1−xm∣∣x−x2∣+∣x−xm−1∣≥∣x2−xm−1∣⋮∣x−xm∣+∣x−x1∣≥∣xm−x1∣\begin{cases} \left|x-x_1\right|+\left|x-x_m\right|&\geq\left|x_1-x_m\right|\\ \left|x-x_2\right|+\left|x-x_{m-1}\right|&\geq\left|x_2-x_{m-1}\right|\\ \vdots\\ \left|x-x_m\right|+\left|x-x_1\right|&\geq\left|x_m-x_1\right|\end{cases} ⎩⎨⎧ ∣x−x1 ∣+∣x−xm ∣∣x−x2 ∣+∣x−xm−1 ∣⋮∣x−xm ∣+∣x−x1 ∣ ≥∣x1 −xm ∣≥∣x2 −xm−1 ∣≥∣xm −x1 ∣求和得2∑i=1m∣x−xi∣≥∑i=1m∣xi−xm−i+1∣2\sum_{i=1}^m\left|x-x_i\right|\geq\sum_{i=1}^m\left|x_i-x_{m-i+1}\right| 2i=1∑m ∣x−xi ∣≥i=1∑m ∣xi −xm−i+1 ∣等号成立，当且仅当 x⌊m/2⌋≤x≤x⌈m/2⌉x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}x⌊m/2⌋ ≤x≤x⌈m/2⌉ 。所以要使原式最小，xxx 的取值范围当然就是 x⌊m/2⌋≤x≤x⌈m/2⌉x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}x⌊m/2⌋ ≤x≤x⌈m/2⌉ 。当然右边关于 yyy 也是一样的。所以代码实现很简单，时间复杂度为 Θ((∑ϵi)log⁡(∑ϵi))\Theta((\sum\epsilon_i)\log(\sum\epsilon_i))Θ((∑ϵi )log(∑ϵi ))。log 可以用 nth_element 求中位数去掉，当然直接排也没事。T7如果你比较熟悉 FJ，你应该对一道典题不陌生——Corn Fields，是状压 DP 的板题。而这道题类似于本题，区别在于 NNN 变大了（12→50012\to 50012→500），模数变了，同时不可以一只乌龟都不养。看起来 NNN 变大时间复杂度不行了，但是状压作法的复杂度略低于 O(n22m)O(n2^{2m})O(n22m)，nnn 变大的影响不大，所以还是状压板题。设 fi,jf_{i,j}fi,j 是在第 iii 行，当前行状态为 jjj 时的方案数，0 为不放，1 为放。我们知道不合法的方案有：行内有连续的 1，有 1 出现在养殖设备的位置。如果该行合法，我们枚举状态 kkk。kkk 同样需要满足上述条件，同时 kkk 与 jjj 不能有同位 1，因为行间也不能有连续的 1。如果一切都符合规则，则可以转移：fi,j←fi,j+fi−1,kf_{i,j}\gets f_{i,j}+f_{i-1,k}fi,j ←fi,j +fi−1,k 。别忘了边界条件：当 i=0i=0i=0 且 jjj 合法时，fi,j=1f_{i,j}=1fi,j =1。细节看注释。T8一道毒瘤的数据结构题。（数据结构题！）数据范围是 10510^5105，暴力显然不行，可以考虑 mnm\sqrt nmn 的分块作法或者 mlog⁡nm\log nmlogn 的线段树作法。如果您很强，那么还有可能用一堆树状数组以优雅的小常数完成此题，不过我不会。这里用线段树作法。首先是线段树的每个节点要存什么。显而易见的是加法懒标记和区间立方和的值。除此之外，由于高次和需要低次和推导而来，所以我们需要再维护区间平方和与区间和的值。然后是线段树的核心——懒标记下传。设当前区间的长度为 lll，加法标记的值为 xxx，s1,s2,s3s_1,s_2,s_3s1 ,s2 ,s3 分别是修改前的 1,2,31,2,31,2,3 次方和，s1′,s2′,s3′s_1^\prime,s_2^\prime,s_3^\primes1′ ,s2′ ,s3′ 分别是修改后的 1,2,31,2,31,2,3 次方和。从最简单的说起：区间和当然增加了 lxlxlx，也就是 s1′←s1+lxs_1^\prime\gets s_1+lxs1′ ←s1 +lx。然后是平方和：s2′=∑(ai+x)2=∑(ai)2+2x∑ai+∑x2=s2+2xs1+lx2\begin{aligned} s_2^\prime&=\sum(a_i+x)^2\\ &=\sum(a_i)^2+2x\sum a_i+\sum x^2\\ &=s_2+2xs_1+lx^2\end{aligned}s2′ =∑(ai +x)2=∑(ai )2+2x∑ai +∑x2=s2 +2xs1 +lx2最后是立方和：s3′=∑(ai+x)3=∑(ai)3+3x∑(ai)2+3x2∑ai+∑x3=s3+3xs2+3x2s1+lx2\begin{aligned} s_3^\prime&=\sum(a_i+x)^3\\ &=\sum(a_i)^3+3x\sum(a_i)^2+3x^2\sum a_i+\sum x^3\\ &=s_3+3xs_2+3x^2s_1+lx^2\end{aligned}s3′ =∑(ai +x)3=∑(ai )3+3x∑(ai )2+3x2∑ai +∑x3=s3 +3xs2 +3x2s1 +lx2代码实现时，不要忘记上传节点信息的时候三种区间信息都要更新。为了防止负数出现，我们在输入的时候把所有负数取模成正数即可。完整代码（稍有压行）。尾祝大家 CSP-J2/S2 rp++！