Hello 2020

B. New Year and Ascent Sequence
这题实际上是一个计数问题,要求任意子序列连接起来,构成上升序列
任意子序列处理起来比较麻烦,我们把问题转换成为整个序列单调不降,任意子序列都是单调不降的
此时序列个数为CC,最后的答案就是n2Cn^2 - C

这样我们任意一个序列就可以用二元组(li,ri)(l_i, r_i) 表示,liA[0]riA[n1]l_i \leftarrow A[0], r_i \leftarrow A[n-1]
问题转换为求解满足rilj,(i,j)r_i \geqslant l_j, \quad (i, j) 的序对

for j: xlj\textbf{for} \ \forall j: \ x \leftarrow l_j,在所有数中二分查找
\quad 找到第一个满足rixr_i \geqslant xrir_i[ri,end)[r_i, end) 即为能够取的所有值
这里如果用一个二元组表示,要将rir_i 作为第一关键字,即(ri,li)(r_i, l_i)

C. New Year and Permutation
这个问题比较 tricky,其实观察后发现
如果[l,r][l, r] 是满足条件的子列,那么[mini=lrpimaxi=lrpi][\min_{i = l}^{r} p_i \cdots \max_{i = l}^{r} p_i] 属于[l,r][l, r] 这个子段
所以可以将这个子段缩成一个点,子段的长度为len=rl+1len = r-l+1

  • 长度为nn 的排列一共有nlen+1n-len+1 种长度为lenlen 的子段
  • 将子段缩点,剩下有nlenn-len 个数,用隔板法插入,一共有nlen+1n-len+1 种插入方式
  • 所以最后答案就是(nlen+1)(nlen+1)(len)!(nlen)!(n-len+1)\cdot (n-len+1) \cdot (len)! \cdot (n-len)!

D. New Year and Conference

codeforces round 714 div2

F. Swapping Problem
div2-714F

  • 很显然,对于最左边的情况,不论交换前后,绝对值都为pi+2over+pjp_i + 2\cdot \text{over} + p_j
    其中pi,pjp_i, p_j 表示两条线段不相交部分,over\text{over} 表示相交部分,结果不可能变好
  • 能够使得结果变好的情况,按照向量方向为从小到大,如图所示,可以分为两类
    根据Ai<BiA_i < B_iBi<AiB_i < A_i 分为两类,{X:Ai<Bi}, {Y:Bi<Ai}\{X: A_i < B_i\}, \ \{Y: B_i < A_i\}
    ans=absi2over,overans = \sum {\text{abs}_i} - 2 \cdot \text{over}, \quad \text{over} 表示线段相交部分的长度
    这样可以初步设计出一种算法
  • 对于Ai<BiA_i < B_i,固定AiA_i,在满足BjAiB_j \leqslant A_i 的条件下,找到最大的AjA_j
    这样使得线段overlap部分最大,即over((Ai,Bi),(Bj,Aj))\text{over}((A_i, B_i), (B_j, A_j)) 最大
  • 对于Bi<AiB_i < A_i,也是类似的

具体的算法如下

  • 每个集合X(AiBi),Y(BiAi)X(A_i \to B_i), \quad Y(B_i \to A_i) 拆成两个集合,以便于之后按照第一关键字排序
    X1(Ai,Bi),X2(Bi,Ai),Y1(Bi,Ai),Y2(Ai,Bi)X1(A_i, B_i), X2(B_i, A_i), Y1(B_i, A_i), Y2(A_i, B_i),之后根据第一关键字排序

  • Ai<BiA_i < B_i 的情况,遍历集合X1X1,对于Ai\forall A_i:

    • 在集合YY 中,找到满足BjAiB_j \leqslant A_i 的最大的BjB_j
      此时BjB_j 是关键字,所以BjY1B_j \in Y1
      遍历满足条件的BjY1\forall B_j \in Y1,将BjB_j 所对应的AjA_j 值用一个set\textbf{set} 来维护
    • Aj=set.rbegin()A_j = \textbf{set}.rbegin()overmax{min(Aj,Bi)Ai}\text{over} \leftarrow \max \{\min(A_j, B_i) - A_i\}
  • Bi<AiB_i < A_i 的情况也类似

  • 最后iAiBi2over\sum_i |A_i - B_i| - 2\cdot \text{over} 就是答案

Add One
首先很容易想到一种数位dp的方法
一开始的时候,统计xx 有那些数字,以第几次操作作为”阶段“,f(i,b)f(i, b) 表示第ii 阶段,数字bb 的长度

f(0,b)=1,bdigit(x)f(i,b+1)=f(i,b+1)+f(i1,b)b[0,8]f(i,0)=f(i,0)+f(i1,9)f(i,1)=f(i,1)+f(i1,9)b=9\begin{aligned} &f(0, b) = 1, \quad b \in \text{digit}(x) \\ &f(i, b+1) = f(i, b+1) + f(i-1, b) \quad b \in [0, 8] \\ &f(i, 0) = f(i, 0) + f(i-1, 9) \quad f(i, 1) = f(i, 1) + f(i-1, 9) \quad b = 9 \end{aligned}

但这样每个询问都必须重新计算遍,会超时,这里可以反着来dpdp
mm 次操作视为阶段00,因为每一次操作对数位的影响,是相互独立的,所以算法正确

  • b[0,8]b \in [0, 8],第ii 阶段数字bb 的长度和第i1i-1 阶段数字b+1b+1 的长度相等
    f(i,b)=f(i1,b+1)f(i, b) = f(i-1, b+1)
  • b=9b = 9,第ii 阶段数字是99,那么第i1ii-1 \to i 阶段存在(09),(19)(0 \to 9), (1 \to 9) 的转移
    换句话说,第ii 阶段99 的长度来源于第i1i-1 阶段0,10, 1 贡献的长度
    f(i,9)=f(i1,0)+f(i1,0)f(i, 9) = f(i-1, 0) + f(i-1, 0)
  • 最后统计b[0,9]b \in [0, 9],看看bb 中那些数在xx 的数位中出现,对f(m,b)f(m, b) 求和即可