Hack一下 注释去掉的minb
  • 板块学术版
  • 楼主LINjoker
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/15 22:31
  • 上次更新2024/10/16 11:15:19
查看原帖
Hack一下 注释去掉的minb
1365651
LINjoker楼主2024/10/15 22:31

P3147 题解中的分治解法 去掉题解中我认为有必要的一部分,提交上去竟然AC,求hack 或说明难道不必要?

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=270000;
int n,pre[maxn],suc[maxn];
struct node
{
    int t,num;
}a[maxn];
void update(int l,int r)
{
    for(int i=l;i<=r;i=suc[i])
    {
        if(i!=l&&a[pre[i]].t==a[i].t) 
                    {
                        a[pre[i]].num+=a[i].num;
                        suc[pre[i]]=suc[i];
                        pre[suc[i]]=pre[i];
                    }
    }
}
int solve(int l,int r,int b)
{
    if(l>r||b>60) return 0;
    update(l,r);
    int last=l,re=0,minb=(maxn<<1);
    for(int i=l;i<=r;i=suc[i])
    {
        re=max(re,a[i].t);
        if(a[i].t==b) 
            {
                if(a[i].num==1)
                {
                    re=max(re,solve(last,pre[i],b));//minb=(maxn<<1);
                    last=suc[i];
                    continue;
                }
                int pd=(a[i].num&1);
                a[i].t++;a[i].num>>=1;minb=b+1;
                if(pd)
                {
                    int tmp=a[i].num;
                    suc[i+tmp]=suc[i];pre[i+tmp]=i;
                    suc[i]=i+tmp;pre[suc[i+tmp]]=i+tmp;
                    a[i+tmp]=a[i];
                    re=max(re,solve(last,i,b));//minb=(maxn<<1);
                    last=i+tmp;
                }
            }
            else minb=min(minb,a[i].t);
    }
    
    if(re<b) return re;
    re=max(re,solve(last,r,minb));
    return re;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].t);
        a[i].num=1;
        suc[i]=i+1;
        pre[i]=i-1;
    }
    printf("%d",solve(1,n,1));
    return 0;
}
2024/10/15 22:31
加载中...