[ZROI 9.15模拟赛] Tutorial

时间：2023-03-09 15:28:53
[ZROI 9.15模拟赛] Tutorial

Link：

传送门

可能要补一补之前的题了

题目名字天(Sky)的(De)炭(C)好评啊……

A：

从买/卖物品的配对来考虑：

可以发现如果当前物品为卖，肯定从之前选最小的（无论其为买/卖），因为贡献都是差值！

如果要买的物品当前状态为卖，那么相当于将那条匹配链的卖的那一端转换

用优先队列维护$pair(w[i],0/1)$，0/1分别表示当前为卖/买的状态即可

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=1e5+;

int T,n,cnt,dat[MAXN];ll res=;

priority_queue<P,vector<P>,greater<P> > q;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&dat[i]);

        res=;cnt=;

        while(!q.empty()) q.pop();

        q.push(P(dat[],));

        for(int i=;i<=n;i++)

        {

            P t=q.top();

            if(dat[i]>t.X)

            {

                res+=dat[i]-t.X;

                cnt+=t.Y;q.pop();

                if(!t.Y) q.push(P(t.X,));

                q.push(P(dat[i],));

            }

            else q.push(P(dat[i],));

        }

        printf("%lld %d\n",res,cnt*);

    }

    return ;

}

Problem A

考场上写的$O(n^2)$ $dp$发现并不能优化……

其实已经想到用匹配来做，但没发现那条可反悔贪心的性质

一般需要优化的匹配问题除了网络流，都是顺序考虑每一个数而非整体考虑

这里还要注意必须将卖设为0，因为在$w[i]$相同时要先将卖转移

（如果优先队列中放的是结构体，注意每个维度的顺序！）

B：

关键要将上下边界也看成大的障碍点

考虑长度$d$不能通过的条件：

将所有长度小于$d$的连边后上下边界连通，这样一定无法通过这道屏障

用类似$Kruskal$的方法将所有边排序后用并查集维护连通性即可

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define pb push_back

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

P dat[MAXN];

int n,l,f[MAXN],tot;

struct edge{int x,y;double w;}e[MAXN];

double sqr(double a){return a*a;}

bool cmp(edge a,edge b){return a.w<b.w;}

void add_edge(int x,int y,double w)

{e[++tot]=(edge){x,y,w};}

int find(int x)

{return f[x]==x?x:f[x]=find(f[x]);}

double dist(int x,int y)

{return sqrt(sqr(dat[x].X-dat[y].X)+sqr(dat[x].Y-dat[y].Y));}

int main()

{

    scanf("%d%d",&n,&l);

    for(int i=;i<=n;i++)

        scanf("%d%d",&dat[i].X,&dat[i].Y);

    for(int i=;i<=n+;i++) f[i]=i;

    for(int i=;i<=n;i++)

        add_edge(,i,dat[i].Y),add_edge(i,n+,l-dat[i].Y);

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)

            add_edge(i,j,dist(i,j));

    sort(e+,e+tot+,cmp);

    for(int i=;i<=tot;i++)

    {

        int px=find(e[i].x),py=find(e[i].y);

        if(px==py) continue;f[px]=py;

        if(find()==find(n+)) return printf("%.3lf",e[i].w),;

    }

    return ;

}

Problem B

C：

将0/1分别看作-1/1的贡献

发现一个区间需要的最小修改次数为最大的不相交前/后缀和的和

感性证明：

最值：只要某位的前/后缀和大于零该位就一定要删除，因此该值为下界

可行性：如果后面还有大于零的点则一定会向后拓展

两种实现方式：

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define mid ((l+r)>>1)

#define lc k<<1,l,mid

#define rc k<<1|1,mid+1,r

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

int n,m,l,r;char s[MAXN];

struct node{int sum,lmx,rmx,mx;}seg[MAXN<<];

node operator + (node a,node b)

{

    node ret;

    ret.sum=a.sum+b.sum;

    ret.lmx=max(a.lmx,a.sum+b.lmx);

    ret.rmx=max(b.rmx,b.sum+a.rmx);

    ret.mx=max(a.lmx+b.rmx,max(a.sum+b.mx,b.sum+a.mx));

    return ret;

}

void build(int k,int l,int r)

{

    if(l==r)

    {

        if(s[l]=='') seg[k]=(node){-,,,};

        else seg[k]=(node){,,,};

        return;

    }

    build(lc);build(rc);

    seg[k]=seg[k<<]+seg[k<<|];

}

node Query(int a,int b,int k,int l,int r)

{

    if(a<=l&&r<=b) return seg[k];

    node ret=(node){,,,};

    if(a<=mid) ret=Query(a,b,lc);

    if(b>mid) ret=ret+Query(a,b,rc);

    return ret;

}

int main()

{

    scanf("%d%d%s",&n,&m,s+);

    build(,,n);

    for(int i=;i<=m;i++)

        scanf("%d%d",&l,&r),printf("%d\n",Query(l,r,,,n).mx);

    return ;

}

Solution A

如果求$pre+suf$的最值要注意将区间向外拓展1

（可能取$pre[l-1]$，也就是前缀不选）

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define mid ((l+r)>>1)

#define lc k<<1,l,mid

#define rc k<<1|1,mid+1,r

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=8e5+,INF=<<;

char s[MAXN];

int res,lft;

int n,q,l,r,pre[MAXN],suf[MAXN];

int mx[MAXN],lmx[MAXN],rmx[MAXN];

void pushup(int k)

{

    lmx[k]=max(lmx[k<<],lmx[k<<|]);

    rmx[k]=max(rmx[k<<],rmx[k<<|]);

    mx[k]=max(mx[k<<],max(mx[k<<|],lmx[k<<]+rmx[k<<|]));

}

void build(int k,int l,int r)

{

    if(l==r)

    {

        lmx[k]=pre[l],rmx[k]=suf[l];

        mx[k]=-INF;return;

    }

    build(lc);build(rc);

    pushup(k);

}

void Query(int a,int b,int k,int l,int r)

{

    if(a<=l&&r<=b)

    {

        if(lft==-INF)

            res=max(res,mx[k]),lft=lmx[k];

        else

            res=max(res,max(mx[k],lft+rmx[k])),

            lft=max(lft,lmx[k]);

        return;

    }

    if(a<=mid) Query(a,b,lc);

    if(b>mid) Query(a,b,rc);

}

int main()

{

    scanf("%d%d%s",&n,&q,s+);

    for(int i=;i<=n;i++)

        pre[i]=pre[i-]+(s[i]==''?-:);

    for(int i=n;i>=;i--)

        suf[i]=suf[i+]+(s[i]==''?-:);

    build(,,n+);

    while(q--)

    {

        scanf("%d%d",&l,&r);

        res=lft=-INF;l--;r++;

        Query(l,r,,,n+);

        printf("%d\n",res-pre[l]-suf[r]);

    }

    return ;

}

Solution B

针老师题解里的树上倍增可能不太懂啊……

相关文章