【学习笔记】NOIP模拟赛

又又又暴零了

max

原题是 AGC056B Range Argmax

这题现场也没几个人过吧。。。

考虑对于一个合法的序列$x$，找到唯一的排列$p$与之对应。

那么我们从$n$开始填数，可以放置的位置是，对于所有包含这个位置的区间，其对应的$x_i$都是这个位置。然后把包含这个位置的区间删去，表示后续填数不会对其造成影响。

显然不同的$x$对应的排列$p$是不同的，同时排列$p$也对应一个$x$序列，因此我们只需要计算合法的$p$数目即可。

假设固定$p_m=n$，那么相当于固定跨过$m$的区间对应的$x$都等于$m$，并且左区间填的数一定都比右区间填的数大。道理很简单，因为左右区间是独立的，如果左区间没有填完，那么意味着接下来无论如何左区间都无法填满了。

对于右区间$(m,r]$的计算是容易的，相当于只处理$(m,r]$中所有区间的$x_i$的数量，因为之前的位置都已经填满了。而对于左区间$[l,m)$所有$x_i$来说，不能存在一个位置，满足所有包含它的区间的$x_i$都是这个位置，并且这个位置不在任意跨$m$的区间内。

设跨$m$区间的最左端点是$l$，因而在去掉跨$m$区间的限制后能填的数的位置一定$\ge l$。

基于上述观察，我们可以写出如下$dp$：

$1.1$ 设$d{p}_{l,r,k}$表示区间$[l,r]$最大值位置$\ge k$的合法$p$序列的数目（或者说$x_i$的方案数），$g_{l,r,k}$表示区间$[l,r]$内跨$k$的限制区间的最左端点。

$1.2$ 有转移式$d{p}_{l,r,k}=d{p}_{l,r,k+1}+d{p}_{l,k-1,g_{l,r,k}}\times d{p}_{k+1,r,k+1}$

复杂度$O(n^3)$。

ps:这个$dp$的确是不平凡的，或许我还没有get到大佬的脑洞？？

#include
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=998244353;
int n,m,g[305][305][305],v[305][305];
ll dp[305][305][305];
void add(ll &x,ll y){
	x=(x+y)%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);memset(g,0x3f,sizeof g);
	cin>>n>>m;for(int i=1;i<=m;i++){
		int l,r;cin>>l>>r;for(int k=l;k<=r;k++){
			g[l][r][k]=l;
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			for(int k=i;k<=j;k++){
				if(g[i][j][k]==0x3f3f3f3f)g[i][j][k]=min(g[i+1][j][k],g[i][j-1][k]);
			}
		}
	}for(int i=1;i<=n;i++)dp[i][i][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=i;k<=j;k++){
				if(g[i][j][k]==0x3f3f3f3f)g[i][j][k]=0;
			}
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			for(int k=j;k>=i;k--){
				dp[i][j][k]=dp[i][j][k+1];
				if(k==j)add(dp[i][j][k],dp[i][j-1][g[i][j][j]]);
				else if(k==i)add(dp[i][j][k],dp[i+1][j][i+1]); 
				else add(dp[i][j][k],dp[i][k-1][g[i][j][k]]*dp[k+1][j][k+1]);
			}
		}
	}cout<<dp[1][n][1];
}
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

draw

原题是「CEOI2022」Drawing

没错这是道构造题 但我依然分毫未取233

考场上没有想到二叉树的性质怎么用。

考虑对于一般的树，把左下角的点作为根，然后极角排序划分成若干子树即可。

考场上的极限也就是$O(n^2)$了。