AISing Programming Contest 2019 翻车记

2023-08-16 23:53:46

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

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 h,w,n;

int main()

{

    n=read(),h=read(),w=read();

    cout<<(n-w+)*(n-h+);

}

　　B：签到*2。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 110

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,b,p[N];

int main()

{

    n=read(),a=read(),b=read();

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

    int ans=,x=,y=,z=;

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

    {

        if (p[i]<=a) x++;

        if (p[i]>a&&p[i]<=b) y++;

        if (p[i]>b) z++;

    }

    cout<<min(x,min(y,z));

}

　　C：考虑在相邻两异色格间连边，这样同一个连通块的异色点间一定存在合法路径。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 410

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,m,a[N][N],fa[N*N],size[N*N][];

int trans(int x,int y){return (x-)*m+y;}

int wx[]={,,,-},wy[]={,,-,};

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

int main()

{

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

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

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

        {

            char c=getchar();

            while (c!='.'&&c!='#') c=getchar();

            a[i][j]=c=='.';

        }

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

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

        {

            fa[trans(i,j)]=trans(i,j);

            size[trans(i,j)][a[i][j]]=;

        }

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

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

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

            if (i+wx[k]>=&&i+wx[k]<=n&&j+wy[k]>=&&j+wy[k]<=m&&a[i+wx[k]][j+wy[k]]!=a[i][j])

            {

                int p=find(trans(i,j)),q=find(trans(i+wx[k],j+wy[k]));

                if (p!=q)

                {

                    fa[p]=q;

                    size[q][]+=size[p][],size[q][]+=size[p][];

                }

            }

    ll ans=;

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

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

        if (find(trans(i,j))==trans(i,j)) ans+=1ll*size[trans(i,j)][]*size[trans(i,j)][];

    cout<<ans;

}

　　D：显然分为两个过程，第一个过程中两人取数互不相关，第二个过程中两人从大到小依次取数。二分套二分找到分界点，瞎搞一波前缀和即可。不知道为啥写了一年。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

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,m,a[N];

ll s[N],f[N];

int findmax(int x,int k)

{

    int l=,r=n;

    while (l+<r)

    {

        int mid=l+r>>;

        if (mid+k->n) r=mid;

        else if (x-a[mid]>a[mid+k-]-x) l=mid;

        else r=mid;

    }

    int ans=l;

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

    if (r+k-<=n&&max(x-a[i],a[i+k-]-x)<max(x-a[ans],a[ans+k-]-x)) ans=i;

    return a[ans+k-];

}//和x最接近的数中取k个后最大的

bool check(int k,int x)

{

    if (k*->n) return ;

    //cout<<k<<' '<<x<<endl;

    //cout<<findmax(x,1)<<' '<<a[n-k+1]<<endl;

    return findmax(x,k-)<a[n-k+];

}

int main()

{

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

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

    sort(a+,a+n+);

    s[]=a[];

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

    for (int i=n;i>=;i--) f[i]=f[i+]+a[i];

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

    {

        int x=read();

        int l=,r=n,t=;

        while (l<=r)

        {

            int mid=l+r>>;

            if (check(mid,x)) t=mid,l=mid+;

            else r=mid-;

        }

        //cout<<t<<endl;

        ll ans=f[n-t+];int y=n-t*;

        if (y>) ans+=s[y];

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

    }

}

　　E：正常的想法是设f[i][j]为i子树中包含j的连通块权值和为j时最少要割多少边，显然这样不行，于是就反过来，设f[i][j]为i子树中割j条边能使i所在连通块获得的最小权值和（当然割出的除根以外的连通块均需要合法）。同时设g[i]表示i子树中最少割多少条边能使i所在连通块均为正数（前提同上）。转移类似树形背包。莫名其妙写的非常慢感觉非常恶心。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 5010

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],p[N],g[N],size[N],t;

ll sum[N],f[N][N];

struct data{int to,nxt;

}edge[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void dfs(int k,int from)

{

    sum[k]=a[k];

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        dfs(edge[i].to,k);

        sum[k]+=sum[edge[i].to];

    }

    if (a[k]>)

    {

        g[k]=;

        for (int i=p[k];i;i=edge[i].nxt)

        if (edge[i].to!=from)

        {

            int x=g[edge[i].to];

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

            if (f[edge[i].to][j]<) {x=min(x,j+);break;}

            g[k]+=x;

        }

    }

    f[k][]=a[k];

    size[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        for (int j=size[k]+size[edge[i].to];j>=;j--)

        {

            f[k][j]+=sum[edge[i].to];if (j-g[edge[i].to]->=) f[k][j]=min(f[k][j],f[k][j-g[edge[i].to]-]);

            for (int x=max(,j-size[k]);x<=min(j,size[edge[i].to]);x++)

            {

                if (x) f[k][j]=min(f[k][j],f[k][j-x]+f[edge[i].to][x]);

                if (x<j&&f[edge[i].to][x]<) f[k][j]=min(f[k][j],f[k][j-x-]);

            }

        }

        size[k]+=size[edge[i].to];

    }

}

int main()

{

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

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

    n=read();

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

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

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

    }

    memset(g,,sizeof(g));

    memset(f,,sizeof(f));

    dfs(,);

    /*for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;

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

    cout<<endl;

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

    {

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

        cout<<f[i][j]<<' ';

        cout<<endl;;

    }

    for (int i=1;i<=n;i++) cout<<sum[i]<<' ';cout<<endl;*/

    int ans=g[];

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

    if (f[][i]<) {ans=min(ans,i);break;}

    cout<<ans;

    return ;

}

　　为什么算rating的时候不把unrated的去掉啊。result：rank 43 rating +138

码农公寓

相关文章