HDU 6351 (带技巧的暴力）

题意：给定一个数，和一个最多交换次数k，问在不超过k次操作的情况，问可以得到的最大值和最小值是多少？

个人解题的艰辛路程，开始是想到了暴力枚举的可能，打出来发现在判断枚举的数组与原来数组交换了多少次出现了错误，我们扫一遍枚举的数组于原来的数组不相同就往后面找到相同，但这个是不行的，这样必须是每一位数都不一样才可以，然后无耻的看了题解， O！原来是枚举位置，然后题解，超时了，想了想发现当k>cnt 的时候，是一定可以构成出来的，不需要枚举，所以加了这样Ala

#include<bits/stdc++.h>

using namespace std ;

int A[],a[],T[],sumMAX[],sumMIN[];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(sumMIN,,sizeof(sumMIN));

        memset(sumMAX,,sizeof(sumMAX));

        int x,k;

        scanf("%d%d",&x,&k);

        int cnt=;

        while(x)

        {

            a[cnt++]=x%;

            sumMAX[x%]++;sumMIN[x%]++;

            x/=;

        }

        for(int i=cnt- ; i>= ; i--)

        {

            A[cnt--i]=a[i];

        }

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

        int MIN=0x3f3f3f3f,MAX=-;

        if(k>=cnt-)///剪枝

        {

            for(int i= ; i<= ; i++)///第一位排除0

            {

                if(sumMIN[i])

                {

                    printf("%d",i);

                    sumMIN[i]--;

                    break;

                }

            }

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

            {

                while(sumMIN[i])

                {

                    printf("%d",i);

                    sumMIN[i]--;

                }

            }

            printf(" ");

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

            {

                while(sumMAX[i])

                {

                    printf("%d",i);sumMAX[i]--;

                }

            }

            puts("");continue;

        }

        do

        {

            int now=;

            int ans=;

            if(A[a[]]==) continue;

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

            T[i]=a[i];

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

            {

                if(T[i]!=i)

                {

                    now++;

                    if(now>k) break;

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

                    {

                        if(T[j]==i)

                        {

                            swap(T[i],T[j]);break;

                        }

                    }

                }

                if(now>k) break;

                ans=ans*+A[a[i]];

            }

            if(now<=k)

            {

            //  printf("%d %d\n",ans,now);

              MAX=max(MAX,ans) , MIN=min(MIN,ans);

            }

        } while(next_permutation(a,a+cnt));

        printf("%d %d\n",MIN,MAX);

    }

}

巴特西

HDU 6351 (带技巧的暴力）

最新文章

热门文章