Difference between revisions of "2018 Multi-University,Nowcoder Day 1"

From EOJ Wiki
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 84: Line 84:
  
 
那么,我们想要的$query(l,r)$,就是树状数组所维护的区间$[l,r]$的和。
 
那么,我们想要的$query(l,r)$,就是树状数组所维护的区间$[l,r]$的和。
 
== Problem K ==
 
 
Unsolved.
 
 
题意:
 
 
题解:
 

Latest revision as of 04:09, 29 August 2018

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

Unsolved.

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]$的和。