立即要去比赛了。

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

首先H题：

H. Happy Reversal

Input

Output

题意：给出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

Input

Output

题意：给出一些数。表示数轴上的位置。让你移动最少的点让全部相邻点的差值均相等！

求移动次数

分析：思路就是暴力，由于点仅仅有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;
}