L - Looking for Taste Gym - 101991L 二进制枚举/思维

方法一：因为最多是10的六次方，所以可以直接枚举二进制上的每一位来得到最优结果。

AC代码：

#include<iostream>

#include<stack>

#include<stdio.h>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<string>

#include<cmath>

#include<cstring>

using namespace std;

# define inf 0x3f3f3f3f

# define maxn 1000000+100

# define ll long long

int a[maxn];

int tempsave[maxn];

int vis[maxn];

int maxx;

vector<int>ans[20];

int n,m;

void cal(int t)

{

    int num=0;

    int e=t;

    while(t)

    {

        int temp=t%2;

        t/=2;

        tempsave[++num]=temp;

    }

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

    {

        if(tempsave[i]!=0)

        {

            maxx=max(i-1,maxx);

            ans[i-1].push_back(e);//把和这一位有关的放进这一位上的容器里

        }

    }

}

ll Pow(ll t1,ll t2)

{

    t2--;

    ll temp=t1;

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

    {

        temp*=t1;

    }

    return temp;

}

bool judge(int t)

{

    int len=ans[t].size();

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

    {

        int temp=ans[t][i];

        if(vis[temp]==1)//如果这一位上已经有数了，返回就可以了。

        {

            return true;

        }

    }

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

    {

        int temp=ans[t][i];

        if(vis[temp]==0)//如果这一位上之前没有数，并且找到了，然后就直接用就可以了。因为二进制的话，越靠前肯定是越大的。

        {

            m--;

            vis[temp]=1;

            return true;

        }

    }

    return false;//如果都没有找到，返回false

}

int main()

{

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

    int T;

    scanf("%d",&T);

    while(T--)

    {

        maxx=0;

        for(int i=0; i<50; i++)ans[i].clear();

        memset(vis,0,sizeof(vis));

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

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

        {

            scanf("%lld",&a[i]);

            cal(a[i]);

        }

        ll sum=0;

        int t=0;

        for(int i=maxx; i>=0; i--)

        {

            if(m==0)break;

            if(judge(i))

            {

                if(i==0)sum+=1;

                else

                    sum+=Pow(2,i);

            }

        }

        printf("%d\n",sum);

    }

    return 0;

}

方法二：看数据，直接把所有的数“|”就完事了，因为给的数是大于20的。。。。、

AC代码：

#include<iostream>

#include<stack>

#include<stdio.h>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<string>

#include<cmath>

#include<cstring>

using namespace std;

# define inf 0x3f3f3f3f

# define maxn 100000+100

# define ll long long

ll a[maxn];

int main()

{

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

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

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

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

        {

            scanf("%lld",&a[i]);

        }

        ll sum=0;

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

        {

            sum=sum|a[i];

        }

        printf("%d\n",sum);

    }

    return 0;

}

巴特西

L - Looking for Taste Gym - 101991L 二进制枚举/思维

最新文章

热门文章