Codeforces Round#509 Div.2翻车记

时间：2023-03-09 23:38:14
Codeforces Round#509 Div.2翻车记

　　A：签到

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int n,a[N];

int main()

{

    n=read();

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

    sort(a+,a+n+);

    cout<<a[n]-a[]+-n;

    return ;

}

　　B：签到

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define ll long long

ll a,b,x,y;

ll gcd(ll n,ll m){return m==?n:gcd(m,n%m);}

int main()

{

    cin>>a>>b>>x>>y;

    ll tmp=gcd(x,y);x/=tmp,y/=tmp;

    cout<<min(a/x,b/y);

    return ;

}

　　C：贪心，每次选择最后一次喝咖啡最早的一天，看是否能将此次喝咖啡加入这天，不行就新开一天。堆维护即可。开始的时候写了半天线性的一直wa on 9，掉rating瞬间稳了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 200010

int n,m,k,tot,ans[N];

struct data{int x,i;

    bool operator <(const data&a) const

    {

        return x<a.x;

    }

}a[N];

struct data2{int id,tim;

    bool operator <(const data2&a) const

    {

        return tim>a.tim;

    }

};

priority_queue<data2> q;

int main()

{

    n=read(),m=read(),k=read()+;

    for (int i=;i<=n;i++) a[i].x=read(),a[i].i=i;

    sort(a+,a+n+);

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

    {

        if (q.empty()||q.top().tim+k>a[i].x)

        {

            tot++;ans[a[i].i]=tot;

            q.push((data2){tot,a[i].x});

        }

        else

        {

            ans[a[i].i]=q.top().id;

            data2 y=q.top();q.pop();

            q.push((data2){y.id,a[i].x});

        }

    }

    cout<<tot<<endl;

    for (int i=;i<=n;i++) printf("%d ",ans[i]);

    return ;

}

　　D：按间隔长度尺取即可。没看到没有相交段，惨惨。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 200010

int n,m,cnt,c[N],d[N],ans,t=;

struct data{int x,y;

    bool operator <(const data&a) const

    {

        return x<a.x;

    }

}a[N],b[N];

int main()

{

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i].x=read(),a[i].y=read();

    sort(a+,a+n+);

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

    {

        int x=a[i].y,t=i;

        while (t<n&&a[t+].x<=x) t++,x=max(x,a[t].y);

        cnt++,b[cnt].x=a[i].x,b[cnt].y=x;

        i=t;

    }

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

    t++,c[t]=b[i].y-b[i].x,d[t]=b[i+].x-b[i].y;

    c[++t]=b[cnt].y-b[cnt].x;

    for (int i=;i<=t;i++) c[i]+=c[i-];

    for (int i=;i<t;i++) d[i]+=d[i-];

    ans=c[]+m;

    int x=;

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

    {

        while (x+<t&&d[x+]-d[i-]<m) x++;

        ans=max(ans,c[x+]-c[i-]+m);

    }

    cout<<ans;

}

　　E：容易发现任意一条边的两端总有一端包含最大值，先把这个判掉。不妨设n号点为树根，此时考虑n-1号点，其与n号点的距离就应为n-1号点的出现次数。类似地发现构造一个链或者菊花就好了，构造完再判断是否合法。n<=1000可能是为了写起来舒服一点。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int n,a[N],b[N],cnt[N],tree[N],x;

int main()

{

    n=read();

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

    {

        a[i]=read(),b[i]=read();cnt[a[i]]++;

        if (b[i]!=n) {printf("NO\n");return ;}

    }

    tree[]=n;x=;

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

    if (cnt[i]) tree[x+=cnt[i]]=i;

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

    if (!cnt[i])

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

        if (!tree[j]) {tree[j]=i;break;}

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

    {

        int x=;

        for (int j=i+;j<=n;j++) x=max(x,tree[j]);

        cnt[x]--;

        if (cnt[x]<) {printf("NO\n");return ;}

    }

    printf("YES\n");

    for (int i=;i<n;i++) cout<<tree[i]<<' '<<tree[i+]<<endl;

}

　　F：比赛时看错题了以为是找最长的交替等差子序列，这拿头做啊。结束半个小时了才发现。考虑如何选取公差，若d=a*b且b是奇数，那么d=a一定会更优。所以只枚举2的幂次作为公差然后map存一下取模的结果就行了。注意ans初值设成2，因为可能存在横坐标相同的点。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

int n,m,x,y,a[N],b[N],ans=;

map<int,int> f,g;

int main()

{

    n=read(),x=read();

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

    m=read(),y=read();

    for (int i=;i<=m;i++) b[i]=read();

    for (int x=;x<=1E9;x<<=)

    {

        f.clear();g.clear();

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

        for (int i=;i<=m;i++) g[b[i]%(x<<)]++;

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

        ans=max(ans,f[a[i]%(x<<)]+g[(a[i]+x)%(x<<)]);

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

        ans=max(ans,g[b[i]%(x<<)]+f[(b[i]+x)%(x<<)]);

    }

    cout<<ans;

}

　　总体是一场readforces&speedforces。于是就翻车了。当然自己还是弱爆。