笛卡尔树-JZTXT

模板

bool flag=0;
while(h[i]<h[sta[top]])
	top--,flag=1;
cr[sta[top]]=i;
if(flag)
	cl[i]=sta[top+1];
sta[++top]=i;

受限制的排列

对于一个 $1$ 到 $n$ 的排列 $p_1, p_2, \cdots, p_n$ ，我们可以轻松地对于任意的 $1 \leq i \leq n$ 计算出 $(l_i, r_i)$ ，使得对于任意的 $1 \leq L \leq R \leq n$ 来说 $\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ 当且仅当 $l_i \leq L \leq i \leq R \leq r_i$ 。

给定整数 $n$ 和 $(l_i, r_i)$ $(1 \leq i \leq n)$ ，你需要计算有多少种可能的 $1$ 到 $n$ 的排列 $p_1, p_2, \cdots, p_n$ 满足上述条件。

由于答案可能很大，你只需要给出答案对 $10^9 + 7$ 取模的值。

题解

实际上它就是一个笛卡尔树，先找到一段区间的最值点，然后一分为二分别处理两边，此时最值定下来了，左右互不影响，因此有$C_{len}^{l}$种情况。用map记录很巧妙。

代码

#include<iostream>
#include<cstring>
using namespace std;
int t,n;
string s;
int dp[2005][2005];
int dfs(int l,int r){
	if(dp[l][r]!=-1)
		return dp[l][r];
	if(l>r)
		return dp[l][r]=1;
	dp[l+2][r]=dfs(l+2,r);
	dp[l][r-2]=dfs(l,r-2);
	dp[l+1][r-1]=dfs(l+1,r-1);
	if((s[l]==s[r]&&dp[l+1][r-1]==1)||(s[l]==s[l+1]&&dp[l+2][r]==1&&s[r]==s[r-1]&&dp[l][r-2]))
		return dp[l][r]=1;
	return dp[l][r]=0;
}
int main(){
	scanf("%d\n",&t);
	while(t--){
		memset(dp,-1,sizeof(dp));
		cin>>s;
		n=s.size();
		s=" "+s;
		dfs(1,n);
		if(dp[1][n]==1)
			printf("Draw\n");
		else
			printf("Alice\n");
	}
}