Codeforces Round #530 Div. 1 自闭记

2021-07-25 06:32:07

　　A：显然应该让未确定的大小尽量大。不知道写了啥就wa了一发。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

#define inf 1000000010

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,p[N],fa[N],a[N],s[N],t,ans;

bool flag=;

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)

{

    if (!flag) return;

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

    {

        int x=edge[i].to,son=;

        for (int j=p[x];j;j=edge[j].nxt) son++;

        if (son==) a[x]=;

        else

        {

            int y=inf;

            for (int j=p[x];j;j=edge[j].nxt)

            y=min(y,s[edge[j].to]);

            if (y<s[k]) {flag=;break;}

            a[x]=y-s[k];s[x]=s[k]+a[x];

            for (int j=p[x];j;j=edge[j].nxt)

            a[edge[j].to]=s[edge[j].to]-s[x],dfs(edge[j].to);

        }

    }

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

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

#endif

    n=read();

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

    {

        int x=read();fa[i]=x;addedge(x,i);

    }

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

    a[]=s[];dfs();

    if (flag)

    {

        ll ans=;

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

        cout<<ans;

    }

    else cout<<-;

    return ;

    //NOTICE LONG LONG!!!!!

}

　　B：快1.5h时才想到一个不太靠谱的做法，然后交一发就wa on 4了。拍了好一会才发现做法假掉了，内心崩溃。花40min换了一个做法，写的时候就感觉这怎么这么简单肯定是假的，然后就wa on 7了，根本都不用拍就发现做法假掉了，内心崩溃。最后终于发现最开始的做法是能抢救一下的，把第二种做法合并上去就行了，然后就没时间了。

　　考虑枚举左上角的2*2方格怎么填。然后考虑前两列，如果将左上角直接向下复制，后面的每一列都只有不相关的两种填法，即两字母交替出现，取最优值即可；如果对左上角复制后进行一些同行内的交换，那么显然会有同一列的连续三行出现不同的字母，这样就固定了每一行都只能是将该行前两个字母复制。

　　事实上更优美的想法是最终填法要么每行内两字母交替出现，要么每列内两字母交替出现。根本想不到啊。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 300010

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,tot,v=N;

vector<char> a[N],b[N],ans[N];

char c[]={'A','C','G','T'};

bool flag[];

void check()

{

    //cout<<b[0][0]<<b[0][1]<<endl<<b[1][0]<<b[1][1]<<endl;

    tot=;

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

    b[i][]=b[i-][],b[i][]=b[i-][];

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

    {

        int ans1=,ans2=;

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

        ans1+=(a[i][j]!=b[i%][j%]),

        ans2+=(a[i][j]!=b[i%^][j&]);

        if (ans1<ans2)

        {

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

            b[i][j]=b[i%][j&];

        }

        else

        {

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

            b[i][j]=b[i%^][j&];

        }

    }

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

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

        tot+=a[i][j]!=b[i][j];

    if (tot<v)

    {

        v=tot;

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

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

            ans[i][j]=b[i][j];

    }

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

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

    {

        int ans1=,ans2=;

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

        ans1+=a[i][j]!=b[i%][j&],ans2+=a[i][j]!=b[i%][j&^];

        if (ans1<ans2)

        {

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

        }

        else

        {

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

        }

    }

    tot=;

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

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

        tot+=a[i][j]!=b[i][j];

    if (tot<v)

    {

        v=tot;

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

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

            ans[i][j]=b[i][j];

    }

}

void dfs(int x,int y)

{

    if (x>) {check();return;}

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

    if (!flag[i])

    {

        b[x][y]=c[i];

        flag[i]=;

        if (y==) dfs(x+,);

        else dfs(x,);

        flag[i]=;

    }

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

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

#endif

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

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

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

        a[i].push_back(getc());

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

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

        b[i].push_back(' '),ans[i].push_back(' ');

    dfs(,);

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

    {

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

        putchar(ans[i][j]);

        printf("\n");

    }

    return ;

    //NOTICE LONG LONG!!!!!

}

　　然后就垫底了。感觉应该早点弃掉这个毒瘤B去看C。哎还是菜爆。

　　大号终于变小号了。result：rank 341 rating -39

　　C：显然所有点的子树大小之和=所有点的深度之和，那么设度数限制为d，只要找到一组x_i满足∑ix_i=s且x_i>=dx_i+1即可。显然度数限制d越大，能构造出s的下界就越小，且增加的这部分边界应该是一段连续区间（因为只要度数限制不为1，就可以找到深度最大且不止一个点的一层，将其中一个点往下拉，使得总深度+1）。于是先找到最小的度数限制，这个随便都能求。然后考虑构造x_i，先构造出这个s的下界，再逐渐将其增大。只需要暴力模拟上述证明的过程即可。当然，不能一次只增大1，而是应该直接拉到最底端，以保证复杂度。（虽然事实上只有度数限制<=2时每次增大1的复杂度会出现问题）感觉还是做的太麻烦了。

#include<bits/stdc++.h>

using namespace std;

#define P 1000000007

#define N 100010

#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 n,ans,fa[N],a[N],size[N],deep[N];ll m;

void dfs(int k,int n,int x)

{

    size[k]=;a[deep[k]]++;

    if (1ll*(k-)*x+>n) return;

    for (int i=(k-)*x+;i<=min(n,k*x+);i++)

    {

        deep[i]=deep[k]+;

        dfs(i,n,x);

        size[k]+=size[i];

    }

}

ll check(int n,int k)

{

    deep[]=;memset(a,,sizeof(a));dfs(,n,k);

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

    return s;

}

void build(int d)

{

    int s=;

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

    {

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

        fa[j]=s-a[i-]+(j-s-)/d+;

        s+=a[i];

    }

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

    cin>>n>>m;

    int l=,r=n-;

    if ((1ll*n*(n+)>>)<m) {cout<<"NO";return ;}

    if ((1ll*n*(n+)>>)==m)

    {

        cout<<"YES\n";

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

        return ;

    }

    while (l<=r)

    {

        int mid=l+r>>;

        if (check(n,mid)<=m) ans=mid,r=mid-;

        else l=mid+;

    }

    if (!ans) {cout<<"NO";return ;}

    ll s=check(n,ans);

    int cur=n;while (cur&&a[cur]<=) cur--;

    int maxdeep;for (maxdeep=;maxdeep<=n;maxdeep++) if (a[maxdeep]==) break;

    maxdeep--;

    for (;;)

    {

        if (m==s) break;

        while (a[cur]==) cur--;

        if (maxdeep+-cur>=m-s) a[cur]--,a[cur+m-s]++,m=s;

        else a[++maxdeep]++,a[cur]--,s+=maxdeep-cur;

    }

    build(ans);

    cout<<"YES\n";

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

    return ;

}

码农公寓

相关文章