CodeForces 124C【连通块】

思路：

a素数->b合数

c素数->b合数

a,c属于一类

so，预处理相同的，并且计数。1000怎么搞都无压力；

我这里也预处理了字母个数，从集合大的枚举下来，每次拿字母个数最多的去匹配。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e3+10;

bool isprime(int x)

{

    if(x==1) return false;

    int q=sqrt(x);

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

        if(x%i==0) return false;

    return true;

}

pair<int,int>sum[1010];

int ssum[30];

char s[N],ans[N];

bool vis[N];

int n;

vector<int>prime;

vector<int>num[200];

void init()

{

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

        if(isprime(i)) prime.push_back(i);

}

int pre[N];

int Find(int x)

{

    int r=x;

    while(pre[r]!=r)

        r=pre[r];

    int i=x,j;

    while(pre[i]!=r)

    {

        j=pre[i];

        pre[i]=r;

        i=j;

    }

    return r;

}

pair<int,int>xs[1010];

vector<int>pp[1010];

int main()

{

    //预处理素数

    init();

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

    n=strlen(s+1);

    //求和

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

    {

        int x=s[i]-'a';

        ssum[x]++;

    }

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

    {

        sum[i].first=ssum[i];

        sum[i].second=i;

    }

    //分块。

    int sz=prime.size();

    int ssz=sz;

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

    {

        if(prime[i]>n)

        {

            ssz=i;

            break;

        }

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

        {

            if(k*prime[i]>n) break;

            num[i].push_back(k*prime[i]);

        }

    }

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

        pre[i]=i;

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

    {

        int u=prime[i];

        int sss=num[i].size();

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

        {

            int v=num[i][k];

            int uu=Find(u);

            int vv=Find(v);

            if(uu!=vv)

                pre[uu]=vv;

        }

    }

    //建立 集合个数 和 集合元素

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

        xs[i].first=0;

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

    {

        int x=Find(i);

        xs[x].first++;

        xs[x].second=x;

        pp[x].push_back(i);

    }

    //从大到小

    sort(xs+1,xs+n+1);

    sort(sum,sum+26);

//    for(int i=n;i>=1;i--)

//    {

//        printf("%d %d\n",xs[i].first,xs[i].second);

//    }

//    for(int j=25;j>=23;j--)

//    {

//        printf("%d\n",sum[j].first);

//    }

    for(int i=n; i>=1; i--)

    {

        int sz=xs[i].first;     //集合个数

        int x=xs[i].second;     //集合老大

        if(pp[x].size()==0) break;

        bool flag=false;

        int j=25;

        if(sum[j].first>=sz)

        {

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

                ans[pp[x][k]-1]=sum[j].second+'a';

            sum[j].first-=sz;

        }

        else

            flag=true;

        sort(sum,sum+26);

        if(flag)

        {

            puts("NO");

            return 0;

        }

    }

    ans[n]='\0';

    puts("YES");

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

    return 0;

}

巴特西

CodeForces 124C【连通块】

最新文章

热门文章