ARC104F Visibility Sequence

大概有两种做法。

首先写一下官方题解的做法。

我们设 $i \to P_i$ 存在一条边,同时将 $P_i=-1$ 看做 $P_i = 0$ ,并添加虚点 $0$ ,于是对于任意一个排列,必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。

然后会发现,对于整棵树的一个子树,它必然在序列上对应一个区间,而它的根就是区间的左端点。考虑任意一个位置 $i$ ,它后面的第一个比它大的位置在 $j$ ,考虑 $[i+1,j-1]$ 这一段之间的所有数,显然它们不会连到 $i$ 的前面。再考虑 $j$ 向后的位置,它们不可能连到 $j$ 前面,因此 $i$ 的子树一定是这么一段区间。

考虑一棵子树,在删除根后它的儿子的子树就会构成一个森林。设子树从左到右的权值分别是 $A_1,A_2,\dots ,A_k$ ,当前位置的权值是 $A$ ,那么必然有

因为如果这个位置 $\le$ 后面某个位置的权值,那么那个位置会成为这个位置的兄弟。而这些子树的权值如果不满足大小关系,内部就不是兄弟关系而是父子关系了。

显然,我们考虑所有点的权值都尽量小的时候一种树的形态是否存在,而且这样的话同一种树的形态必然对应唯一一种权值序列。

于是可以考虑设 $f[x][l][r]$ 表示区间 $[l,r]$ 构成了一棵树,根为 $l$ ,最小情况下权值是 $x$ ,设 $g[x][l][r]$ 表示区间 $[l,r]$ 构成了一个森林,森林最右边的树的根最小情况下的值为 $x$ 的方案数量。显然这种情况下权值不需要超过 $n$ ,于是可以直接给每个点的上限与 $n$ 取较小值。

考虑转移。

所以树的转移很简单

考虑森林的转移,这种转移的常见操作是枚举一棵树,然后分成一棵树和剩下的森林,这里显然枚举后面的树会比较方便。由于 $g[x][l][r]$ 表示的是权值最小的情况下最右边的子树权值是 $x$ 的森林个数,所以转移的时候,需要满足两边必须有一边的最小情况下的的权值是 $x$ 。如果是左边满足,那么直接把右边的子树的根的权值变成 $x$ ,如果右边满足就没必要修改。

这样就可以不重不漏计算了,复杂度是 $O(n^4)$ 。一份代码

还有一种 zjk 做法(非常好写)。

类似刚刚的思路,考虑所有点的权值都尽量小的情况下,会发现一棵原题中的树会对应唯一一种笛卡尔树。因为会发现原题中的树进行一次左兄弟,右儿子的变化后就会成为一棵笛卡尔树!不难发现做完这个操作后,这个笛卡尔树必须满足左儿子和当前点可以相等,而右儿子必须小于。

一张看起来非常阳间的配图:

image.png

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 126
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 7;
int n , m;
int A[MAXN];

vi val;
int dp[MAXN][MAXN][MAXN];

int fuck( int l , int r , int x ) {
int& s = dp[l][r][x];
if( ~s ) return s;
if( l > r ) return s = 1;
if( !x ) return 0;
s = 0;
rep( p , l , r ) s = ( s + fuck( l , p - 1 , min( x , A[p] ) ) * 1ll * fuck( p + 1 , r , min( x , A[p] ) - 1 ) ) % P;
return s;
}

void solve() {
cin >> n;
rep( i , 1 , n ) scanf("%d",A + i) , A[i] = min( A[i] , n );
memset( dp , -1 , sizeof dp );
cout << fuck( 1 , n , n ) << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/03/21/arc104f-visibility-sequence/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog