UOJ Logo paul2008的博客

博客

标签
暂无

UOJ840 龙门考古 题解

2022-08-27 17:44:20 By paul2008

首先考虑固定一个无法辨认的位置集合$S$,我们该如何求出字典序最小的排列。

令$nex_i$表示$>i$的位置中第一个为$1$的位置,若不存在则为$n+1$。

  • 对于$c_i=1$的位置$i$,他的限制是其$>[1,nex_i-1]$
  • 对于$c_i=0$的位置$i$,他没有任何限制。

我们考虑将所有$c_i=1$的元素移动到第$nex_i$个元素的前面。后文都在移动后的排列上考虑。

现在,对于$c_i=1$的位置$i$,他的限制是其$>i$前面的所有元素;对于$c_i=0$的位置$i$,仍然没有限制。

我们从前到后依次确定每个无法辨认的位置填什么,填能填且符合要求的数中最小的那个。正确性显然。


$dp_{i,j}$表示考虑了位置$\le i$且权值$\le j$的元素,他们的方案数。

令$Max_{i}$表示$max\{a_1...a_i\}$,$pos_i$表示权值为$i$的元素所在的位置。

当$pos_j>i$时:$dp_{i,j}=dp_{i,j-1}$

当$c_{pos_j}=0$时:

  • $pos_j$位置选择:$dp_{i,j-1}$
  • $pos_j$位置不选择:我们需要位置$>pos_j$的权值$

当$c_{pos_j}=1$时: - $pos_j$位置选择:$dp_{i,j-1}$ - $pos_j$位置不选择:我们需要权值在$(Max_{pos_j-1},j)$的元素都选择,因此方案数为$dp_{i,Max_{pos_j-1}}$

至此,我们就有了一个$O(n^2)$的做法。


我们将转移方程列一下:

if(pos[j]>i)
    dp[i][j]=dp[i][j-1];
else if(typ[pos[j]]==1)
    dp[i][j]=dp[i][j-1]+dp[i][Max[pos[j]-1]];
else
    dp[i][j]=dp[i][j-1]+dp[pos[j]][j-1];

称第一种转移为“平凡转移”,第二、三种转移为“非平凡转移”。

考虑从小到大扫描$i$,每次会加进来一个非平凡转移。加进来的是$j=a_i$的转移。

我们考虑构建一张$n+1$个点的有向无环图,初始为$0,1,2,......,n$,$i->i+1$,$0$处权值为$1$。

$dp_{i,j}$就是目前这个有向无环图中所有点的权值$*$这个点到$j$的路径数之和。

如果$typ_i=0$,相当于将$a_i$位置的权值加上$dp_{i,a_{i}-1}$。

如果$typ_i=1$,相当于让$Max_{i-1}$与$a_i$连边。

观察到所有新连的边互不相交,因此任意两点$i,j$之间路径数量为$2^{edge_{i,j}}$,其中$edge_{i,j}$为完全包含在$i,j$两点之间的额外边数量。

现在这个问题可以用一颗线段树维护,每个节点维护权值$*2^{edge_{x,n}}$,需要支持区间乘,单点加,区间和。

代码:https://uoj.ac/submission/677924

共 1 篇博客