2019.9.16 csp-s模拟测试44 反思总结

虽然说好像没有什么写这个的价值OAO

来了来了来写总结了，不能怨任何东西，就是自己垃圾x

开题顺序又和主流背道而驰，先一头扎进了公认最迷的T2，瞎搞两个小时头铁出来，然后T1和T3爆炸。基础很差，全靠瞎蒙，能力不足，不如滚蛋。

T1：D

发现对于一个长为n的序列，从右端点开始往回和前面的数依次求gcd最多不超过logn个，原因是每次的gcd若缩小则一定除以2。那么从前往后传递gcd，需要维护的gcd也不超过logn个。

于是从1~n枚举序列右端点，每一次把当前存在的gcd分别和新的右端点求gcd，用map映射存下这个gcd当前存在的这段序列中它的最小左端点，尝试更新答案。

不要忘了记录当前的右端点x

时间复杂度是O（nlog²n），当然有标准的O（nlogn）做法啦，但我懒嘛。

代码：

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

int n;

long long a[];

map<long long,int>mp,m;

map<long long,int>::iterator it;

long long ans;

long long GCD(long long a,long long b){

    return !b?a:GCD(b,a%b);

}

int main()

{

    scanf("%d",&n);

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

        scanf("%lld",&a[i]);

        ans=max(ans,a[i]);

        for(it=m.begin();it!=m.end();it++){

            long long gcd=GCD(a[i],it->first);

            if(gcd*(i-it->second+)>ans)ans=gcd*(i-it->second+);

            if(!mp.count(gcd))mp[gcd]=it->second;

            else mp[gcd]=min(mp[gcd],it->second);

        }

        if(!mp.count(a[i]))mp[a[i]]=i;

        m=mp;

        mp.clear();

    }

    printf("%lld",ans);

    return ;

}

谜一样的比较大小:D

总之稍微记一下定义迭代器以及gcd不超过logn个的定理…

T2：E

说得简单一点，考虑两种情况。一种是最大最小两个球同色，另一种是异色。

异色的话假设最大值蓝色，最小值红色，那么要让两边的差都尽量小，直接把每一组的大值染蓝小值染红就OK了。

同色要麻烦一些，把各个组按小值从小到大排序，然后依次把同一组大小值反色，更新答案。假设最大值最小值都是蓝色，这样依次操作的时候红球的最大最小值是不降的，而翻转以后上一组最大最小值已经计算过了，不影响答案。这样解释有点玄学，但是自己举了几组例子好像没有反例，就试着写了一下，居然过了……

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n;

long long rmin=1e18,rmax,bmin=1e18,bmax,r,b;

long long ans=1e18,minn=1e18,maxx,posmin,posmax;

struct node{

    long long a,b;

}x[];

bool cmp(node a,node b){

    if(a.a==b.a)return a.b<b.b;

    else return a.a<b.a;

}

int main()

{

    scanf("%d",&n);

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

        scanf("%lld%lld",&x[i].a,&x[i].b);

        if(x[i].a>x[i].b)swap(x[i].a,x[i].b);

        rmin=min(x[i].a,rmin);

        rmax=max(x[i].a,rmax);

        bmin=min(x[i].b,bmin);

        bmax=max(x[i].b,bmax);

        if(x[i].a<minn){

            minn=x[i].a;

            posmin=i;

        }

        if(x[i].b>maxx){

            maxx=x[i].b;

            posmax=i;

        }

    }

    ans=(rmax-rmin)*(bmax-bmin);

    if(posmin==posmax)printf("%lld",ans);

    else{

        sort(x+,x+n+,cmp);

        bmin=minn,bmax=maxx;

        rmax=max(x[n].a,x[].b);

        minn=x[].b;

        rmin=min(x[].b,x[].a);

        long long ans1=rmax-rmin;

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

            rmax=max(rmax,x[i].b);

            rmin=min(min(x[i].b,x[i+].a),minn);

            minn=min(minn,x[i].b);

            ans1=min(ans1,rmax-rmin);

        }

        ans=min(ans,ans1*(bmax-bmin));

        printf("%lld",ans);

    }

    return ;

}

玄学代码

T3：F

你好，线段树优化DP，下一个。

说实话我连简单的三十分DP都没想出来，我大约是个睿智。不我应该自信地拿掉大约这两个字，毕竟你看垃圾就是垃圾，没什么好说的。

写出简单的转移式，f（i，j）中i为当前操作到第i个其中一个指针在pi，j为另一个指针在j处。

f（i，j）=f（i-1，j）+|pi-pi-1|，假如从上一个pi转移过来

f（i，pi-1）=f（i-1，j）+|pi-j|，假如从上一个j转移过来。

然后发现可以用线段树来维护，第一个转移式就是区间加，第二个转移式要维护最小fj-j和fj+j值，每次拆开绝对值根据正负查询。

注意开头的时候要先把a、b两处的f值维护成“第一个操作从b转移来”和“第一个操作从a转移来”，然后从第二次操作开始。因为对于p1来说，上一次移动的位置可以是aa也可以是bb。不写明白这个居然还有八十分:D

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

long long inf=1e18;

int n,q,aa,bb,lst;

struct node{

    int l,r;

    long long min1,min2,f,add;

}a[];

void build(int p,int l,int r){

    a[p].l=l,a[p].r=r;

    a[p].f=a[p].min1=a[p].min2=inf;

    if(l==r)return;

    int mid=(l+r)/;

    build(p*,l,mid);

    build(p*+,mid+,r);

}

void update(int p){

    if(a[p].add){

        a[p*].add+=a[p].add;

        a[p*+].add+=a[p].add;

        a[p*].min1+=a[p].add;

        a[p*+].min1+=a[p].add;

        a[p*].min2+=a[p].add;

        a[p*+].min2+=a[p].add;

        a[p*].f+=a[p].add;

        a[p*+].f+=a[p].add;

        a[p].add=;

    }

}

void change(int p,int l,int r,long long val){

    if(l<=a[p].l&&a[p].r<=r){

        a[p].f=min(a[p].f,val);

        a[p].min1=a[p].f-l;

        a[p].min2=a[p].f+l;

        return;

    }

    update(p);

    int mid=(a[p].l+a[p].r)/;

    if(l<=mid)change(p*,l,r,val);

    if(r>mid)change(p*+,l,r,val);

    a[p].min1=min(a[p*].min1,a[p*+].min1);

    a[p].min2=min(a[p*].min2,a[p*+].min2);

    a[p].f=min(a[p*].f,a[p*+].f);

}

void change1(int p,int l,int r,long long val){

    if(l<=a[p].l&&a[p].r<=r){

        a[p].add+=val;

        a[p].min1+=val;

        a[p].min2+=val;

        a[p].f+=val;

        return;

    }

    update(p);

    int mid=(a[p].l+a[p].r)/;

    if(l<=mid)change1(p*,l,r,val);

    if(r>mid)change1(p*+,l,r,val);

    a[p].min1=min(a[p*].min1,a[p*+].min1);

    a[p].min2=min(a[p*].min2,a[p*+].min2);

    a[p].f=min(a[p*].f,a[p*+].f);

}

long long query1(int p,int l,int r){

    if(l<=a[p].l&&a[p].r<=r){

        return a[p].min1;

    }

    update(p);

    int mid=(a[p].l+a[p].r)/;

    long long val=inf;

    if(l<=mid)val=min(val,query1(p*,l,r));

    if(r>mid)val=min(val,query1(p*+,l,r));

    a[p].min1=min(a[p*].min1,a[p*+].min1);

    a[p].min2=min(a[p*].min2,a[p*+].min2);

    a[p].f=min(a[p*].f,a[p*+].f);

    return val;

}

long long query2(int p,int l,int r){

    if(l<=a[p].l&&a[p].r<=r){

        return a[p].min2;

    }

    update(p);

    int mid=(a[p].l+a[p].r)/;

    long long val=inf;

    if(l<=mid)val=min(val,query2(p*,l,r));

    if(r>mid)val=min(val,query2(p*+,l,r));

    a[p].min1=min(a[p*].min1,a[p*+].min1);

    a[p].min2=min(a[p*].min2,a[p*+].min2);

    a[p].f=min(a[p*].f,a[p*+].f);

    return val;

}

long long query(int p,int l,int r){

    if(l<=a[p].l&&a[p].r<=r){

        return a[p].f;

    }

    update(p);

    int mid=(a[p].l+a[p].r)/;

    long long val=inf;

    if(l<=mid)val=min(val,query(p*,l,r));

    if(r>mid)val=min(val,query(p*+,l,r));

    a[p].min1=min(a[p*].min1,a[p*+].min1);

    a[p].min2=min(a[p*].min2,a[p*+].min2);

    a[p].f=min(a[p*].f,a[p*+].f);

    return val;

}

int main()

{

    scanf("%d%d%d%d",&n,&q,&aa,&bb);

    build(,,n);

    scanf("%d",&lst);

    change(,aa,aa,abs(lst-bb));

    change(,bb,bb,abs(lst-aa));

    for(int i=,x;i<=q;i++){

        scanf("%d",&x);

        long long num1=query1(,,x);

        long long num2=query2(,x,n);

        long long num=min(num1+x,num2-x);

        change1(,,n,(long long)abs(x-lst));

        change(,lst,lst,num);

        lst=x;

    }

    printf("%lld",query(,,n));

    return ;

}

写得贼麻烦的代码

晚上好，今天墨雨笙小朋友复习了一个重要的道理，叫作垃圾就是垃圾。这没什么问题，毕竟你就是差劲呀:D

渣滓稍微活一活就知足吧

巴特西

2019.9.16 csp-s模拟测试44 反思总结

最新文章

热门文章