d-规则

【问题描述】
对任意给定的m(m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}

(m,n≤100)。现定义一种d规则如下：若存在a∈P，且存在K∈N+ ,K>1，使得K´a∈P，则修改P

为：P=P-{y|y=s´a,s∈N+ } ，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n

值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的

d规则序列，输出每次使用d规则时的分值和集合p的变化过程。
【输入格式】
输入仅一行，M,N的值。
【输出格式】
输出每次使用d规则时的分值和集合p的变化过程(即变化后的集合内所有的数,每个数用空格

隔开),注意D后面有个空格，冒号后面有个空格。如果没有一

#include<bits/stdc++.h>

using namespace std;

int n,m,z,ans;

bool a[];

set<int> b[],all;

int l[];

set<int>::iterator it;

void jian(set<int> &a,set<int> &b)

{

    set<int> c;

    c.clear();

    set_intersection(a.begin(),a.end(),b.begin(),b.end(),

    insert_iterator<set<int> >(c,c.begin()));

    for(it=c.begin();it!=c.end();it++)

    {

        a.erase(*it);

    }c.clear();

}

void print(set<int> a)

{

    for(it=a.begin();it!=a.end();it++)

        printf("%d ",*it);

}

int check()

{

    int minn=,minp=;

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

    if(a[i]==&&b[i].size()!=)

    {

        if(l[i]<=minn)

        {

            minn=l[i];

            minp=i;

        }

    }

    l[]=minp;

    return minp;

}

int main()

{

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

//    freopen("set.out","w",stdout);

    scanf("%d%d",&m,&n);

    z=n/-m+;

    for(int i=m;i<=n;i++) all.insert(i);

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

    {

        a[i]=;

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

        {

            b[i].insert(i*j);

        }

        l[i]=b[i].size();

    }

    while(check()!=)

    {

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

        if(a[i]==&&i!=l[])

        {

            jian(b[i],b[l[]]);

            b[i].erase(l[]);

            l[i]=b[i].size();

        }

        jian(all,b[l[]]);

        all.erase(l[]);

        printf("%d : ",l[]);

        print(all);

        printf("\n");

        b[l[]].clear();

        l[l[]]=;

        a[l[]]=;

        ans+=l[];

    }

    return ;

}

//10  1 2 1 1 2 3 2 1 1 2

次可以变化就输出0。
【样例输入】
(1)
1 10
(2)
56 57
【样例输出】
(1)
5 : 1 2 3 4 6 7 8 9
4 : 1 2 3 6 7 9
2 : 1 3 7 9
3 : 1 7
1 :
(2)
0

巴特西

d-规则

最新文章

热门文章