2018 Multi-University,Nowcoder Day 1

Problem A

Solved.

题意：往 n×m 的格子里填 0,1,2，求左边比右边小，上面比下面小的填法数量。

题解：显然，就是求分界线0/1和1/2不相交的方案数，不会啊.....

是什么Lindström–Gessel–Viennot定理？直接找规律吧...

根据定理，最终推出的结论就是：${C_{n+m}^{n}}^{2}-C_{n+m}^{m-1}*C_{n+m}^{n-1}$

Problem B

Solved.

题意：

题解：

Problem C

Unsolved.

题意：

题解：

Problem D

Solved.

题意：

题解：

Problem E

Solved.

题意：求把一个数列删除恰好 m 元素之后有多少种不同的结果数列。

题解：直接dp，$f[i][j]$表示结尾为$a[i]$，前$i$位，移除了$j$位的方案数。

显然，如果对于$x,y$满足$a[x]=a[y]$，那么由$f[i](i<x,y)$同时向$f[x]$和$f[y]$转移是没有意义的（会重复）。

那么我们记录一下每一个位置后面紧接着的所有数的最近位置，只向那个最近的位置转移即可。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Upsolved by Xiejiadong.

题意：给出一个数列$a$，求$RMQ$形态与$a$相同的、所有数都是在$[0,1]$区间内均匀分布的数列$b$的和的期望。

题解：先构建出$a$的笛卡尔树，与$a$的笛卡尔树同构的个数，就是树的拓扑序数量$\frac {n!}{\prod^{n}_{i=1} size_i}$，对于$a$直接构造笛卡尔树，然后遍历即可

而$\sum b_i$的期望显然是$\frac {n}{2}$，将两个答案相乘即可

Problem I

Unsolved.

Problem J

Solved.

题意：求一个前缀+一个后缀出现的不同数字数量。

题解：我们可以$O(n)$预处理出区间$[1,x]$中有$b[x]$个不同的数。

可以在$[1,n]$后面重复的再接上一串一样数，那么询问$(l,r)$就变成了询问区间$[r,l+n]$中有多少个不同的数字。

显然，我们的答案就是$b[l+n]-b[r-1]+query(l,r)$,$query(l,r)$表示区间$[l,r]$和区间$[1,l-1]$中共有的数。

我们将询问按照按照左端点排序。

考虑用树状数组离线维护$query(l,r)$。

$c[i]=1$表示位置$$上的数在当前区间的左边也存在。

我们每次左边区间的移动，如果这个数字是最后一次出现（即已经全部移到了左边，以后不会再出现），我们将标记$-1$，否则，我们将与这个数相同的后一个位置标记$+1$。

那么，我们想要的$query(l,r)$，就是树状数组所维护的区间$[l,r]$的和。