2014北京邀请赛(部分题解)

骑猪看日落 2022-08-27 08:49 163阅读 0赞

马上要去比赛了。

今天做了一下2014北京邀请赛，出了两道题目，感觉很水啊、、、

首先H题：

# H. Happy Reversal #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][] [PID: 34988][PID_ 34988]

Font Size:\+\-

Elfness is studying in an operation " NOT".

For a binary number A, if we do operation " NOT A", after that, all digits of A will be reversed. (e.g. A= 1001101, after operation " NOT A", A will be 0110010).

Now Elfness has N binary numbers of length K, now he can do operations " NOT" for some of his numbers.

Let's assume after his operations, the maximum number is M, the minimum number is P. He wants to know what's the maximum M - P he can get. Can you help him?

## Input ##

The first line of input is an integer T (T ≤ 60), indicating the number of cases.

For each case, the first line contains 2 integers N (1 ≤ N ≤ 10000) and K (1 ≤ K ≤ 60), the next N lines contains N binary numbers, one number per line, indicating the numbers that Elfness has. The length of each binary number is K.

## Output ##

For each case, first output the case number as "Case \#x: ", and x is the case number. Then you should output an integer, indicating the maximum result that Elfness can get.

题意：给出n个二进制串，可以把其中的一些0和1反转（即0变1,1变0），找出转化后n个串中的最大值和最小值的差值。

分析：思路就是把所有的串和反转的存在一个数组中，然后排序，找最大值和最小值的差，（如果是同一个串反转的就找第二大的和最小的或第二小和最大的中的最大值）。注意假如只有一个串的话结果为0

代码：

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    class number
    {
    public:
        long long p;
        string s;
        void Set(long long p,string s)
        {
            this->p = p;
            this->s = s;
        }
        friend bool operator < (number a,number b)
        {
            return a.s < b.s;
        }
    };
    int main()
    {
        long long T,c=0;
        cin>>T;
        number num[20020];
        while(T--)
        {
            c++;
            long long n,k;
            cin>>n>>k;
            string s;
            for(long long i = 0; i < 2*n; ++ i)
            {
                cin>>s;
                num[i].Set(i,s);
                for(long long j = 0; j < k; ++ j)
                    if(s[j]=='0')
                        s[j]='1';
                    else
                        s[j]='0';
                ++i;
                num[i].Set(i-1,s);
            }
            sort(num,num+2*n);
    //        for(long long i = 0; i < 2*n; ++ i)
    //            cout<<num[i].s<<endl;
            cout<<"Case #"<<c<<": ";
            if(n == 1)
            {
                cout<<"0"<<endl;
            }
            else if(num[0].p!=num[2*n-1].p)
            {
                long long a=0,b=0;
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(num[0].s[i] == '1')
                        a+=j;
                }
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(num[2*n-1].s[i] == '1')
                        b+=j;
                }
                cout<<b-a<<endl;
            }
            else
            {
                string s1,s2;
                long long a=0,b=0,ans=0;
                s1 = num[0].s;
                s2 = num[2*n-2].s;
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(s1[i] == '1')
                        a+=j;
                }
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(s2[i] == '1')
                        b+=j;
                }
                ans = b-a;
                b=0;a=0;
                s1 = num[1].s;
                s2 = num[2*n-1].s;
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(s1[i] == '1')
                        a+=j;
                }
                for(long long i = k-1,j=1; i >= 0; -- i,j<<=1)
                {
                    if(s2[i] == '1')
                        b+=j;
                }
                cout<<max(ans,b-a)<<endl;
            }
        }
        return 0;
    }

B题：

# B. Beautiful Garden #

Time Limit: 15000ms

Case Time Limit: 8000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 1] [PID: 34982][PID_ 34982]

Font Size:\+\-

There are n trees planted in lxhgww's garden. You can assume that these trees are planted along the X-axis, and the coordinate of i th tree is x i.

But in recent days, lxhgww wants to move some of the trees to make them look more beautiful. lxhgww will recognize the trees as beautiful if and only if the distance between any adjacent trees is the same.

Now, lxhgww wants to know what is the minimum number of trees he need to move.

Just to be clear, after moving, there should still be n trees in the X-axis.

## Input ##

The first line of the input contains a single integer T, which is the number of test cases.

For each case,

*  The first line contains an integers number n (1 ≤ n ≤ 40), representing the number of trees lxhgww planted;
 *  The second line contains n integers numbers, the ith number represents xi. (-1000000000 ≤ xi ≤ 1000000000)

## Output ##

For each case, first output the case number as "Case \#x: ", and x is the case number. Then output a single number, representing the minimum number of trees lxhgww needs to move.

题意：给出一些数，表示数轴上的位置，让你移动最少的点让所有相邻点的差值均相等！求移动次数

分析：思路就是暴力，因为点只有40个，所以我们可以枚举相邻点的差值，因为我最少也能够保证两个点是不动的，那么我枚举这两个点作为所有的差值，然后找一个落在枚举的方案的最大点的方案。

此题目坑点很多！首先有可能两个点落在同一位置，其次枚举的话数据范围会超int。算是一个坑题。

代码：

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    using namespace std;
    long long a[200];
    int main()
    {
        long long T;
        scanf("%lld",&T);
        for(long long cas=1;cas<=T;cas++)
        {
            long long n,ans=0;
            scanf("%lld",&n);
            long long len=n;
            for(long long i=0;i<n;i++)  ///输入
            {
                scanf("%lld",&a[i]);
            }
            sort(a,a+n);
            long long count=0,tmp=1;
            for(long long i=1;i<n;i++)  //找数组中只有两个数且重点的最小值
            {
                if(a[i]==a[i-1])
                {
                    tmp++;
                }
                else
                    break;
            }
            long long xx = 0,tt=0;
            int  p = 0;
            for(int i = 0; i < n; ++ i)  //找所有里面重点最多的
            {
                if(i == n-1)
                {
                    ++tt;
                    if(xx < tt)
                        xx = tt;
                }
                else if(a[i]==a[p])
                tt++;
                else
                {
                    p = i;
                    if(xx < tt)
                        xx = tt;
                    tt=1;
                }//printf("*%lld\n",tt);
            }
    //        printf("x%lld\n",tmp);
            count = min(tmp,len-tmp);
            for(long long i=1;i<n;i++)  ///删除重复元素
            {
                if(a[i]==a[i-1])
                {
                    for(long long j=i;j<n-1;j++)
                        a[j]=a[j+1];
                    n--;i--;
                }
            }
    //        for(long long i=0;i<n;i++)
    //            printf("%lld ",a[i]);
            for(long long i=0;i<n-1;i++)  ///枚举结果
            {
                for(long long j=i+1;j<n;j++)
                {
                    long long lis=a[j]-a[i];
    //                if(lis==0)
    //                    continue;
                    for(long long k=0;k<n;k++)
                    {
                        long long mm=0;
                        long long ri=a[k]+(len-1)*lis;
    //                    printf("x%lld ",ri);
                        for(long long f=k;f<n && a[f]<=ri;f++)
                        {
    //                        if(f==i || f==j)
    //                            continue;
                            long long tmp=a[f]-a[i];
                            if(tmp<0)
                                tmp=-tmp;
                            if(tmp%lis==0)
                                mm++;
                        }
    //                    printf("%lld\n",mm);
                        if(mm>ans)
                            ans=mm;
                    }
                }
    //            printf("xx\n\n");
            }
            printf("Case #%lld: ",cas);
            if(n==1 || len==2)
            {
                printf("0\n");continue;
            }
            else if(n==2 && len>2)
            {
                printf("%lld\n",count);continue;
            }
            printf("%lld\n",min(len-ans,len-xx));
        }
        return 0;
    }

[Submit]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3927#
[Status]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3927#status/H
[PID_ 34988]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=34988
[Status 1]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3927#status/B
[PID_ 34982]: http://www.bnuoj.com/bnuoj/problem_show.php?pid=34982