diverta 2019 Programming Contest 2自闭记

签到（a-b problem不用贴了吧，以后atcoder小于300分题均不贴代码）

发现选择的p,q一定是其中两点间的距离，于是可以O(n²)枚举两点，再O(n²)判断，其实可以做到O(n³)不过O(n⁴)就够了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,ans;

ll x[],y[];

int main()

{

    scanf("%d",&n);

    ans=n;

    for(int i=;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);

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

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

    {

        ll dx=x[i]-x[j],dy=y[i]-y[j];

        int sum=;

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

        {

            int flag=;

            for(int l=;l<=n;l++)if(x[k]-x[l]==dx&&y[k]-y[l]==dy){flag=;break;}

            sum+=flag;

        }

        ans=min(ans,sum);

    }

    printf("%d\n",ans);

}

按照从小到大排成a1,a2,...,an，分类讨论：1、只有两个数直接相减。2、对于全是正的，显然应该先拿a1的减去除了an以外其他数，再用an减去该数，显然答案就是a2+a3+...+an-a1。对于全是负的，可以采用类似的方法。3、对于有正有负的，显然选出a1和an，a1减去除an外的正数，an减去除a1外的负数，再an-a1即可，答案就是所有数的绝对值

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

int n,m,a[N],ax[N],ay[N];

int main()

{

    scanf("%d",&n);

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

    sort(a+,a+n+);

    if(n==)

    {

        printf("%d\n%d %d\n",a[]-a[],a[],a[]);

        return ;

    }

    if(a[]>=)

    {

        for(int i=;i<n;i++)ax[++m]=a[],ay[m]=a[i],a[]-=a[i];

        ax[++m]=a[n],ay[m]=a[],a[n]-=a[];

        printf("%d\n",a[n]);

        for(int i=;i<=m;i++)printf("%d %d\n",ax[i],ay[i]);

        return ;

    }

    if(a[n]<=)

    {

        int ans=a[n];

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

        printf("%d\n",ans);

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

        return ;

    }

    int pos=;

    for(int i=;i<=n;i++)if(a[i]>=){pos=i;break;}

    for(int i=;i<pos;i++)ax[++m]=a[n],ay[m]=a[i],a[n]-=a[i];

    for(int i=pos;i<n;i++)ax[++m]=a[],ay[m]=a[i],a[]-=a[i];

    ax[++m]=a[n],ay[m]=a[],a[n]-=a[];

    printf("%d\n",a[n]);

    for(int i=;i<=m;i++)printf("%d %d\n",ax[i],ay[i]);

}

发现只会做两轮交易，A->B，B->A，然后发现是个完全背包DP，并且第二次背包的容量是O(n²)的，于是就可以直接O(n²)DP结束了，感觉这个D比C简单吧。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

int n,m,a[],b[];

ll ans,f[N*N];

int main()

{

    scanf("%d",&n);

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

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

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

    if(b[i]>a[i])

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

    f[j]=max(f[j],f[j-a[i]]+b[i]-a[i]);

    for(int i=;i<=n;i++)m=max(1ll*m,f[i]),f[i]=;

    m+=n;

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

    if(a[i]>b[i])

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

    f[j]=max(f[j],f[j-b[i]]+a[i]-b[i]);

    for(int i=;i<=m;i++)ans=max(ans,f[i]);

    ans+=m;

    printf("%lld",ans);

}

考后5min写出来，简直自闭……早知道不去写F的打表程序还没跑出来……就是每次移动总是min->max，然后f[i]表示max为i时的方案数，显然对于多个max的可以变换成x!种（x为max的人数），然后求一个阶乘前缀和即可。注意最后f[n]不要求。

#include<bits/stdc++.h>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int N=1e6+,mod=1e9+;

int n,d,h,f[N],fac[N],inv[N],sf[N],s[N<<];

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

void update(int k,int v,int l,int r,int rt)

{

    if(l==r){s[rt]=v;return;}

    int mid=l+r>>;

    if(k<=mid)update(k,v,lson);

    else update(k,v,rson);

    s[rt]=(s[rt<<]+s[rt<<|])%mod;

}

int query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R)return s[rt];

    int mid=l+r>>,ret=;

    if(L<=mid)ret+=query(L,R,lson);

    if(R>mid)ret+=query(L,R,rson);

    return ret%mod;

}

int main()

{

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

    fac[]=;for(int i=;i<=n;i++)fac[i]=1ll*fac[i-]*i%mod;

    for(int i=;i<=n;i++)sf[i]=(sf[i-]+fac[i])%mod;

    update(,fac[n],,h,);

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

    {

        f[i]=query(max(,i-d),i-,,h,);

        if(i<h)f[i]=1ll*f[i]*sf[n]%mod,update(i,f[i],,h,);

    }

    printf("%d",f[h]);

}

好吧，看了网上程序，差不多是构造个近似fib数列的玩意，把表抄上也没管了……

#include<bits/stdc++.h>

using namespace std;

long long a1[]={,,,,,,,,,},a2[]={,,,,,,,,,};

long long n,w=,mp[][];

int main()

{

    cin>>n;

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

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

    {

        for(int j=i+;j<=n;j++)mp[i][j]=mp[j][i]=w*a1[j-i-];

        w*=a2[n-i];

    }

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

    {

        for(int j=;j<=n;j++)cout<<mp[i][j]<<' ';

        cout<<endl;

    }

}

result：rank101 rating+=58，精准地没进前100……

巴特西

diverta 2019 Programming Contest 2自闭记

最新文章

热门文章