2019多校第一场A Equivalent Prefixes

登录—专业IT笔试面试备考平台_牛客网

https://ac.nowcoder.com/acm/contest/881/A

https://ac.nowcoder.com/acm/contest/881/A
题意:两个数列完全相同等价于两个数列的任意子区间的最小元素下标都相同,给定两个数列,求最大的p,使得A[1...p]与B[1...p]相同。
思路1:考虑p=x-1时是满足条件的,那么加入第x个元素,新增的所有区间为x一直向左延伸,我们维护两个单调递增栈,当且仅当p时两个数列的两个单调递增栈都一样时,p是满足条件的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+100;

int n,a[maxn],b[maxn];
stack<int> x,y,z;

int main()
{
    //freopen("input.in","r",stdin);
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&b[i]);
        int ans=n;
        for(int i=1;i<=n;i++)
        {
            int suba=0,subb=0;
            while(!x.empty() && a[x.top()]>a[i])x.pop(),suba++;
            while(!y.empty() && b[y.top()]>b[i])y.pop(),subb++;
            x.push(i);
            y.push(i);
            if(suba!=subb){ans=i-1;break;}
        }
        x=y=z;printf("%d\n",ans);
    }
    return 0;
}

思路2:二分枚举p,考虑一个p对应的区间[1...p],假如最小值下标都在x处,那么跨越x的所有区间都是满足的,只需要看区间[1,x-1],[x+1,p],这样递归分治也是一个好办法,复杂度略高,但这个队友想出的方法很有意思。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int Maxn=1e5+5;
int a[Maxn],b[Maxn];
int minna[30][Maxn],minnb[30][Maxn];

void RMQ_Init()
{
    for(int i=1;i<=n;i++)minnb[0][i]=minna[0][i]=i;
    for(int k=1;(1<<k)<=n;k++)
    {
        for(int i=1;i+(1<<k)-1<=n;i++)
        {
            if(a[minna[k-1][i]]<a[minna[k-1][i+(1<<(k-1))]])minna[k][i]=minna[k-1][i];
            else minna[k][i]=minna[k-1][i+(1<<(k-1))];
            if(b[minnb[k-1][i]]<b[minnb[k-1][i+(1<<(k-1))]])minnb[k][i]=minnb[k-1][i];
            else minnb[k][i]=minnb[k-1][i+(1<<(k-1))];
        }
    }
}

int RMQ(int l,int r)
{
    int k=0;
    while((1<<(k+1)<=r-l+1))k++;
    int ma=(a[minna[k][l]]<a[minna[k][r-(1<<k)+1]]?minna[k][l]:minna[k][r-(1<<k)+1]);
    int mb=(b[minnb[k][l]]<b[minnb[k][r-(1<<k)+1]]?minnb[k][l]:minnb[k][r-(1<<k)+1]);
    if(ma!=mb)return 0;
    return  ma;
}
bool solve(int l,int r)
{
    if (l>r) return 1;
    int m=RMQ(l,r);
    if (!m) return 0;
    return solve(l,m-1)&&solve(m+1,r);
}
int main(){
   // freopen("in.txt","r",stdin);
    while (~scanf("%d",&n))
    {
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=n;i++) scanf("%d",&b[i]);
        RMQ_Init();
        int low=1,high=n;
        while (low<=high)
        {
            int mid=(low+high)>>1;
            if (solve(1,mid)) low=mid+1;else high=mid-1;
        }
        printf("%d\n",high);
    }
    return 0;
}
全部评论

相关推荐

程序员牛肉:这一眼假啊,基本上都是骗人的,不然就涉及到职位贪腐了,就像之前华为的OD事件,看你运气好不好了
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务