BZOJ4391 High Card Low Card [Usaco2015 dec]（贪心+线段树/set库

时间：2022-11-21 15:45:22

正解:贪心+线段树/set库

解题报告：

算辣直接甩链接qwq

恩这题就贪心？从前往后从后往前各推一次然后找一遍哪个地方最大就欧克了，正确性很容易证明

（这里有个，很妙的想法，就是，从后往前推从前往后推可能会有相同的牌嘛，但是其实这个是没有个关系的！

因为，既然有相同的牌那么就必定有多了的牌，然后如果这个多了的牌比重了的牌大我们就放前面，比重了的小我们就放后面，这样就不会影响答案的正确性了……

哇我觉得这个想法真是太神仙了像我这种菜鸡自己单独想的话是绝对想不到这个的我可能就直接放弃贪心了TT

但是纯贪心的话是会超时的TT然后我就又参考了下题解，发现有线段树&set库两种优化方法？因为set库还并不了解所以先把线段树的代码看完了……看完之后感觉对线段树也有了更深的认识啊（恩大概是因为我太菜了对线段树的认识太浅薄所以随便个什么东西都能让我感觉很神仙很有启发TT

直接放代码quq

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
#define my(i,x,y) for(register ll i=y;i>=x;--i)

;
ll n,a[N],b[N],ans[N],tot=;
];
];

ll read()
{
    ;
    ')ch=getchar();
    )+(x<<)+(ch^'),ch=getchar();
    return x;
}
void build(ll d,ll l,ll r)
{
    t[d].s1=t[d].s2=;
    if (l==r) return;
    ll mid=(l+r)>>;
    build(d<<,l,mid);build((d<<)|,mid+,r);
}

void update(ll d,ll op)
{
    ll s;
    )|].s1,t[d<<].s2);
    ].s1,t[(d<<)|].s2);
    t[d].s1=t[d<<].s1+t[(d<<)|].s1-s;
    t[d].s2=t[d<<].s2+t[(d<<)|].s2-s;
}

void ins(ll d,ll l,ll r,ll x,ll op)
{
    ;;return;}
    ;
    ,l,mid,x,op);
    )|,mid+,r,x,op);
    update(d,op);
}

int main()
{
    n=read();
    rp(i,,n)b[i]=read(),vis[b[i]]=;
    my(i,,n<<)if(!vis[i])a[++tot]=i;
    rp(i,,n)ins(,,n<<,a[i],),ins(,,n<<,b[i],),ans[i]+=i-t[].s1;
    build(,,n<<);
    my(i,,n)ins(,,n<<,a[i],),ins(,,n<<,b[i],),ans[i-]+=n-i+-t[].s1;
    ;
    rp(i,,n)mx=max(mx,ans[i]);
    printf("%lld",mx);
    ;
}

然后港下set做法?话说set做法实在太太太简单了趴,,,完全不用脑子的说,,,我当初还是太弱了呢连set和lower_bound都不会qwq

就非常简单啊,lower_bound优化一下查找过程就水过去了,挺无趣的qwq还是线段树的比较有趣qwq

然后代码放一下qwq

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,x,y) for(register ll i=x;i<=y;++i)
#define my(i,x,y) for(register ll i=x;i>=y;--i)

;
ll n,a[N],b[N],ans,f[N],g[N],tot;
];
set<ll>c;

ll read()
{
    ;
    ')ch=getchar();
    )+(x<<)+(ch^'),ch=getchar();
    return x;
}

int main()
{
    n=read();
    rp(i,,n)b[i]=read(),vis[b[i]]=;
    rp(i,,n<<)if(!vis[i])a[++tot]=i;
    rp(i,,n)c.insert(a[i]);
    rp(i,,n)
    {
        set<ll>::iterator it=c.upper_bound(b[i]);
        ]+,c.erase(it);
        ];
    }
    c.clear();
    rp(i,,n)c.insert(-a[i]);
    my(i,n,)
    {
        set<ll>::iterator it=c.upper_bound(-b[i]);
        ]+,c.erase(it);
        ];
    }
    rp(i,,n)ans=max(ans,f[i]+g[i+]);
    printf("%lld\n",ans);
    ;
}

//完美结束yeah!

完美结束嘻嘻嘻

ps：

感觉这个好像不是完全是个线段树？并不知道是什么思想暂且先当做线段树趴!

再，pppppps：

第一次在博客上写题解，感觉还挺新奇的？以后要多写点儿题解（毕竟灵巧太蒻了有很多题目都要再总结记录下来啊quq不然可能以后再看做过的题目都会怀疑自己以前写的代码都是些什么神仙玩意儿了QAQ

然后感觉格式有点儿丑啊还是……可能还有很多新奇的编辑工具不会用趴，比如说代码……我的代码插入那儿真是太丑了QAQ想换成主色调为黑的感觉超级酷可惜不会换（dbq我不该把心思都放在博客好不好看上的……忏悔TT

相关文章