2019牛客多校第一场A. Equivalent Prefixes
当然单调栈的解法这里就不提了。。。
说一下笛卡尔树的解法
其实这个题意一出来，只要学过笛卡尔树的人，都应该知道怎么解了。
如果两个序列前K项，满足要求他们的子集合的最小值位置相同，那么他们数组的前K项构造出来的其实笛卡尔树其实是相同的。
方法1.每次二分一个长度len，然后构造序列的前len项，然后判断这个数是否是相同的。判断规则就是每个节点的父亲节点以及儿子节点是否相同
方法2.其实熟悉笛卡尔树性质的人，就知道笛卡尔树构造到位置i那么所有的节点1到i-1号节点的都在左边，
画个图我们就知道，要求的最大长度，其实就是这两个笛卡尔树的前缀是否是相同的，也就是说，去掉len后面的节点后，这个树的形状是完全相同的
那么我们该如何更加优雅的判断呢？？？
我们其实只需要考虑第i位的左儿子是否是相同的即可，如果是相同的，那么前i项的形状一定是相同的。因为对于一个节点，它的左儿子节点一定是其位置比他小的，而它的右儿子节点一定都是位置比他大的。证明我也不知道怎么证明。。。
方法1：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+10; int stk[maxn],tp; int aa[maxn],bb[maxn]; void build(int n,int a[],int ch[][2],int fa[]){ tp=0; for (int i=1;i<=n;i++) { int last=0; while(tp){ if (a[stk[tp]]<=a[i]){ if (ch[stk[tp]][1])ch[i][0]=ch[stk[tp]][1],fa[ch[stk[tp]][1]]=i; ch[stk[tp]][1]=i;fa[i]=stk[tp]; break; } last=stk[tp--]; } if (!tp && last)ch[i][0]=last,fa[last]=i; stk[++tp]=i; } } int fa[maxn],ch[maxn][2],faa[maxn],chh[maxn][2]; bool same(int len){ for (int i=1;i<=len;i++){ fa[i]=0; ch[i][0]=0; ch[i][1]=0; faa[i]=0; chh[i][0]=0; chh[i][1]=0; } build(len,aa,ch,fa); build(len,bb,chh,faa); int flag=0; for (int i=1;i<=len;i++){ if (fa[i]!=faa[i])flag=1; if (ch[i][0]!=chh[i][0])flag=1; if (ch[i][1]!=chh[i][1])flag=1; if (flag)break; } if (flag)return 0; else return 1; } int main(){ int n; while(~scanf("%d",&n)){ memset(stk,0,sizeof(stk)); // memset(aa,0,sizeof(aa)); for (int i=1;i<=n;i++){ scanf("%d",&aa[i]); } for (int i=1;i<=n;i++){ scanf("%d",&bb[i]); } int l=1; int r=n; int ans=1; while(l<=r){ int mid=(l+r)>>1; if(same(mid)){ ans=mid; l=mid+1; }else { r=mid-1; } } printf("%d\n",ans); } return 0; }
方法2：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+10; int stk[maxn],tp; int aa[maxn],bb[maxn]; void build(int n,int a[],int ch[][2],int fa[]){ tp=0;//栈指针 for (int i=1;i<=n;i++) { int last=0;//栈顶元素 while(tp){ if (a[stk[tp]]<=a[i]){//如果当前的值大于栈顶 //如果现在栈顶元素的右儿子是存在的 //需要把栈顶元素的右儿子断掉加入新节点的左儿子， //同时把新节点加入栈顶元素的右儿子 if (ch[stk[tp]][1])ch[i][0]=ch[stk[tp]][1],fa[ch[stk[tp]][1]]=i; ch[stk[tp]][1]=i;fa[i]=stk[tp]; break; } last=stk[tp--];//先除去栈顶元素 } //如果栈为空，并且last有值的话，把这个值加入左儿子 if (!tp && last)ch[i][0]=last,fa[last]=i; stk[++tp]=i; } } int fa[maxn],ch[maxn][2],faa[maxn],chh[maxn][2]; int main(){ int n; while(~scanf("%d",&n)){ memset(stk,0,sizeof(stk)); // memset(aa,0,sizeof(aa)); for (int i=1;i<=n;i++){ fa[i]=0; faa[i]=0; ch[i][0]=0; ch[i][1]=0; chh[i][0]=0; chh[i][1]=0; } for (int i=1;i<=n;i++){ scanf("%d",&aa[i]); } for (int i=1;i<=n;i++){ scanf("%d",&bb[i]); } int ans=1; build(n,aa,ch,fa); build(n,bb,chh,faa); int cnt=1; for (int i=2;i<=n;i++){ if (ch[i][0]==chh[i][0]) cnt++; else break; } printf("%d\n",cnt); } return 0; }
查看18道真题和解析