Avito Cool Challenge 2018 自闭记

2022-10-20 14:53:14

　　A：n==2?2:1。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

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;

int main()

{

/*#ifndef ONLINE_JUDGE

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

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

#endif*/

    n=read();

    if (n==) cout<<;else cout<<;

    return ;

}

　　B：sort一下，组内人数相同的放一组，超了就换一组。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

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,ans[N],cnt;

struct data

{

    int x,y;

    bool operator <(const data&a) const

    {

        return x<a.x;

    }

}a[N];

int main()

{

/*#ifndef ONLINE_JUDGE

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

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

#endif*/

    n=read();

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

    sort(a+,a+n+);

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

    {

        int t=i;

        while (t<n&&a[t+].x==a[i].x&&t+-i+<=a[i].x) t++;

        if (t-i+!=a[i].x) {cout<<"Impossible";return ;}

        cnt++;

        for (int j=i;j<=t;j++) ans[a[j].y]=cnt;

        i=t;

    }

    printf("Possible\n");

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

    return ;

}

　　C：f[i][j]前i个有j块那啥的方案数，转移显然。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define P 998244353

#define N 2010

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

int main()

{

/*#ifndef ONLINE_JUDGE

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

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

#endif*/

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

    f[][]=m;

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

    {

        f[i][]=m;

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

        f[i][j]=(f[i-][j]+1ll*f[i-][j-]*(m-))%P;

    }

    cout<<f[n][k];

    return ;

}

　　D：kruskal求出最小瓶颈树，最后使所有标记点连接成一个连通块的边即为答案。莫名其妙的写了一堆东西还wa了两发。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

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

bool flag[N],f[N];

struct data

{

    int x,y,z;

    bool operator <(const data&a) const

    {

        return z<a.z;

    }

}e[N];

namespace tree

{

    int p[N],t,size[N],dfn[N],cnt;

    struct data{int to,nxt,len;

    }edge[N<<];

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

    void dfs(int k,int from)

    {

        size[k]=f[k];dfn[k]=++cnt;

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

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

        {

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

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

        }

    }

}

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

int main()

{

/*#ifndef ONLINE_JUDGE

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

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

#endif*/

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

    for (int i=;i<=k;i++) f[read()]=;

    /*for (int i=1;i<=m;i++)

    {

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

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

    }*/

    for (int i=;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].z=read();

    sort(e+,e+m+);

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

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

    {

        int p=find(e[i].x),q=find(e[i].y);

        if (p!=q) fa[q]=p,tree::addedge(e[i].x,e[i].y,e[i].z),tree::addedge(e[i].y,e[i].x,e[i].z),flag[i]=;

    }

    tree::dfs(,);

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

    if (flag[i])

    {

        int x=e[i].x,y=e[i].y;

        if (tree::dfn[x]<tree::dfn[y]) swap(x,y);

        if (tree::size[x]&&tree::size[x]<k) {for (int j=;j<=k;j++) printf("%d ",e[i].z);return ;}

    }

    return ;

}

　　E：真的自闭了。本身就非常思博还想了50min。肝F无果回来hack的时候，在最后1min发现了输出没开I64d，居然还犹豫了一下是不是实际上并不会出问题，然后还真的就没改。看来就算define int long long也解决不了我天天爆int了。

　　注意到对于偶数位我们应该让这里的前缀和尽量小，因为下一位可以任意取。于是记录到每个偶数位时的最小前缀和即可。同时由平方差公式，可以暴力枚举偶数位上的数的因数来快速枚举每种情况。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 200010

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

const double eps=1E-;

ll a[N];

int main()

{

/*#ifndef ONLINE_JUDGE

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

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

#endif*/

    n=read();

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

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

    {

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

        if (a[i]%j==)

        {

            int x=j,y=a[i]/j;//q-p=x q+p=y

            if ((x+y&)||(y-x&)) continue;

            int q=x+y>>,p=y-x>>;//p i-1ǰ׺ q iǰ׺

            if (f[i-]<p) f[i]=q,a[i-]=1ll*p*p-1ll*f[i-]*f[i-];

        }

        if (f[i]==) {cout<<"No";return ;}

    }

    cout<<"Yes\n";

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

    return ;

}

　　一夜回到*。虽然看起来大号还是不会变成小号的。

　　不过好像D和E都fst了不少？

　　然后我还发现F原来是真随机本来一直在想靠谱做法。

　　再也不打Chinese Round了

　　result：rank 477 rating -52

上一篇：转载: 国内的go get无法连接问题的解决


下一篇：DMA&PIO