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
题意,一门课有两个上课地点a,ba, b,在两个上课地点的时间不同,分别为[sai,eai],[sbi,ebi][sa_i, ea_i], [sb_i, eb_i]
定义venue-sensitive\text{venue-sensitive} 如下,存在课程集合SSsize(S)2\textbf{size}(S) \geqslant 2
使得SS 中的所有课在地点aa 上课冲突,在bb 上不冲突;或者在bb 冲突,在aa 不冲突
如果找不到venue-sensitive\text{venue-sensitive} 的课程集合,输出yes\text{yes},否则输出no\text{no}

对于课程ii 用一个四元组(sai,eai,sbi,ebi)(sa_i, ea_i, sb_i, eb_i) 表示,大致思路为
先找出[sa,ea][sa, ea] 存在重合(即在aa 上课重合)的集合SS,然后判断SS是否存在一组(i,j),ij(i, j), i \neq j
使得[sbi,ebi], [sbj,ebj][sb_i, eb_i], \ [sb_j, eb_j] 不重合,即存在有bb 上课不重合的两门课
如果找到了,说明存在venue-sensitive\text{venue-sensitive},返回true\text{true}

  • 活动选择模型,可以先根据saisa_i 对所有活动排序,用STL\text{STL} 容器SS 来维护所有活动[sa1san][sa_1 \cdots sa_n]
    对于活动ii[sai,eai][sa_i, ea_i],在SS 中二分查找位置pp,使得sap>eaisa_p > ea_i
    此时有saisai+1sap1eaisa_i \leqslant sa_{i+1} \leqslant \cdots \leqslant sa_{p-1} \leqslant ea_i
    也就是说,活动i, [sai,eai]i, \ [sa_i, ea_i] 与活动集V=[i+1,p1]V = [i+1, p-1] 在地点aa 相交
  • 接下来要判断活动i, [sbi,ebi]i, \ [sb_i, eb_i] 与活动集V=[i+1,p1]V=[i+1, p-1] 在地点bb 是否相交
    可以在一开始先针对地点bb 的活动建一个线段树
    只需在线段树中查询区间[i+1,p1][i+1, p-1]maxS, minE\text{maxS}, \ \text{minE}
    如果ebi<maxS or sbi>minEeb_i < \text{maxS} \ \textbf{or} \ sb_i > \text{minE}
    说明VV 中存在一个活动和活动ii 不重合,集合是venue-sensitive\text{venue-sensitive}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class SegTree {
public:
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l >= r) {
t[p].maxS = a[l].sb;
t[p].minE = a[l].eb;
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
pull(p);
}
};

bool solve() {
sort(a+1, a+1+n);
// according to eb
seg.build(1, 1, n);

vector<int> V;
V.push_back(0);
for (int i = 1; i <= n; i++) V.push_back(a[i].sa);

for (int i = 1; i <= n; i++) {
int p = upper_bound(V.begin(), V.end(), a[i].ea) - V.begin();
p--;
int maxS = seg.find(1, i+1, p, 0);
int minE = seg.find(1, i+1, p, 1);
if (a[i].eb < maxS || a[i].sb > minE) return false;
}
return true;
}

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) 求和即可