AtCoder Grand Contest 055题解

我太菜啦！！！md，第一题就把我卡死了...感觉对构造题不会再爱了...

A - ABC Identity

先来看这个题吧，题意就是给定你一个字符串，让你将这个字符串最多分成6个子串，使得每个字符都在某个子串当中，使得每个子串都满足以下条件，每个子串的长度为3的倍数，且前1/3和中间的1/3和最后的1/3内部必须字母一样，且这三部分互不相等。...

构造题我也不是没做过，看到最多6种，我就知道肯定有一种方法是6中且满足所有的情况。可怎么向也想不到....呜呜呜呜。3和6的关系...，最后看看题解，不就是排列吗？6是3的全排列啊，我们先将整个字符串分成三部分，每次从每部分各拿出一个，然后按照格子的排列合并不就行了....吐了...

#include<bits/stdc++.h>

using namespace std;

const int N=6e5+10;

int n,b[N],vis[N];

char c[N];

inline void work(char A,char B,char C,int id)

{

    int tot1=0,tot2=0,tot3=0;

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

    {

        if(!vis[i]&&c[i]==A) tot1++;

        if(!vis[n+i]&&c[n+i]==B) tot2++;

        if(!vis[2*n+i]&&c[2*n+i]==C) tot3++;

    }

    tot1=tot2=tot3=min(min(tot1,tot2),tot3);

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

    {

        if(!vis[i]&&c[i]==A&&(tot1--)>0) b[i]=id,vis[i]=1;

        if(!vis[n+i]&&c[n+i]==B&&(tot2--)>0) b[n+i]=id,vis[n+i]=1;

        if(!vis[2*n+i]&&c[2*n+i]==C&&(tot3--)>0) b[2*n+i]=id,vis[2*n+i]=1;

    }

}

int main()

{

//    freopen("1.in","r",stdin);

    scanf("%d",&n);

    scanf("%s",c+1);

    work('A','B','C',1);

    work('A','C','B',2);

    work('B','A','C',3);

    work('B','C','A',4);

    work('C','A','B',5);

    work('C','B','A',6);

    for(int i=1;i<=3*n;++i) printf("%d",b[i]);

    return 0;

}

AtCoder Grand Contest 055题解的相关教程结束。