Good Bye 2018 没打记

时间：2024-12-30 15:07:26

　　场外选手赛时只口胡出了CD感觉非常惨。只看了E并且还没看到题面里的wiki我能咋办

　　C：f只与gcd(n,k)有关。

　　D：考虑每种起始位置，对于跨越的两个排列，只有前一个排列的后缀单减时不产生贡献。答案就非常显然了。注意最后+1，因为这样没考虑n~1的排列。

　　E：根据题面给出的定理，n+1号点度数增大时，以该点在已从大到小排序的序列里的位置为分割点，k较大时不等式更难满足，k较小时不等式更易满足，且分割点位置左移。因此每一个位置存在一个连续的合法区间，区间并即为答案，显然其也是一个连续区间。找到任意一个合法答案后二分即可。这个任意答案也可以二分得到，具体地，根据n+1号点度数所在位置及其右边位置是否合法决定二分方向。不等式显然可以树状数组优化一下检验（甚至可以线性？）。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

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

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;

}

int n,a[N],b[N],tree_size[N],isodd,down,up;

ll tree_sum[N];

void ins(int x){for (int i=x+;i<=n+;i+=i&-i) tree_size[i]++,tree_sum[i]+=x;}

int query_size(int k){int s=;k++;while (k) s+=tree_size[k],k-=k&-k;return s;}

ll query_sum(int k){ll s=;k++;while (k) s+=tree_sum[k],k-=k&-k;return s;}

int findanyans()

{

    int l=,r=(n>>)+;

    while (l<=r)

    {

        int mid=l+r>>,k=mid<<|isodd;

        if (k>n) r=mid-;

        else

        {

            memset(tree_sum,,sizeof(tree_sum));

            memset(tree_size,,sizeof(tree_size));

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

            int pos=;

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

            if (b[i]<k)

            {

                for (int j=n+;j>i;j--) b[j]=b[j-];

                b[i]=k;pos=i;break;

            }

            if (pos==) pos=n+;

            ll s=;for (int i=;i<=n+;i++) s+=b[i];

            bool flag=;

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

            {

                if (s>1ll*i*(i-)+1ll*i*((n+-i)-query_size(i))+query_sum(i)) {flag=;break;}

                s-=b[i];ins(b[i]);

            }

            if (!flag) r=mid-;

            else

            {

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

                {

                    if (s>1ll*i*(i-)+1ll*i*((n+-i)-query_size(i))+query_sum(i)) {flag=;break;}

                    s-=b[i];ins(b[i]);

                }

                if (flag) return mid;else l=mid+;

            }

        }

    }

    return -;

}

bool check(int mid)

{

    mid<<=,mid+=isodd;

    if (mid>n) return ;

    memset(tree_sum,,sizeof(tree_sum));

    memset(tree_size,,sizeof(tree_size));

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

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

    if (b[i]<mid)

    {

        for (int j=n+;j>i;j--) b[j]=b[j-];

        b[i]=mid;break;

    }

    ll s=;for (int i=;i<=n+;i++) s+=b[i];

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

    {

        if (s>1ll*i*(i-)+1ll*i*((n+-i)-query_size(i))+query_sum(i)) return ;

        s-=b[i];ins(b[i]);

    }

    return ;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("e.in","r",stdin);

    freopen("e.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

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

    sort(a+,a+n+);reverse(a+,a+n+);

    for (int i=;i<=n;i++) isodd^=a[i]&;

    down=up=findanyans();

    if (down==-) {cout<<-;return ;}

    int l=,r=down;

    while (l<=r)

    {

        int mid=l+r>>;

        if (check(mid)) down=mid,r=mid-;

        else l=mid+;

    }

    l=up,r=(n>>)+;

    while (l<=r)

    {

        int mid=l+r>>;

        if (check(mid)) up=mid,l=mid+;

        else r=mid-;

    }

    for (int i=down;i<=up;i++) printf("%d ",i<<|isodd);

    return ;

}

　　F：显然每一段都是前一部分步行/游泳，后一部分飞。同样显然的是最后把精力值用完才是最优的，于是总飞行时间也固定了。现在所要做的就是尽量使用游泳来攒精力。那么当处于游泳路段时，只要精力值不会多余就攒精力，否则直接飞到终点。处于步行路段时，只要能满足之后强制飞行路段的需求就飞，否则步行攒精力。怎么这么简单啊？然后才发现原来还有原地徘徊这种操作。不过事实上只要根据后面的需求延长路径且尽量在游泳路段延长就行了？

相关文章