牛客编程巅峰赛S2第1场 - 青铜&白银场

一、A 最小差值

A 最小差值传送门

自己给自己挖的坑：int rt=(1<<31)-1;//不能用0x3f3f
PS:原因是测试数据范围很广

• 解法：排序+暴力

(1)本代码未能AC（测试时间2020.11.17比赛完）

本代码在比赛最初测试数据没有更新前能AC，更新后无法AC，只能过90%附近

• 根据牛油反馈修正

//注意，这个代码在更新数据后只能过90%，请勿拿这个代码测试

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型vector 数组a
     * @return int整型
     */
    int minDifference(vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        int rt=(1<<31)-1;//不能用0x3f3f
        int len=a.size();

        for(int i=1; i<len; ++i)
        {
            rt=min(rt, a[i]-a[i-1]);
        }

        return rt;
    }
};

（2）测试数据更新后能AC的

AC 100%代码
推测添加的测试数据，一个是a[i]在(1<<31)-1附近，被减的a[i-1]是int中负数最大的附近
这样一减，就会溢出，大于int，所以可以用long long承载

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型vector 数组a
     * @return int整型
     */
    int minDifference(vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        long long rt=(1<<31)-1;
        int len=a.size();

        for(int i=1; i<len; ++i)
        {
            rt=min(rt, (long long)a[i]-(long long)a[i-1]);
        }

        return rt;
    }
};

二、B Tree IV

B Tree IV传送门

（1）没AC的

较（2）AC的，坑点在于

long long cheng=(a+b)*(b-a+1)/2%maxn;

原先写的是

long long cheng=(a+b)*(b-a+1)%maxn/2;

PS:虽然先前那么写，小范围数据也能AC，但是到大范围的数据，就会发现，如果先模998244353，可能会导致精度出问题。

（2）AC的

• 解法：前缀和+数列求和

const int maxn=998244353;
long long node[35];
long long sum[35];//第i层存节点数多少个,Sn节点个数
void init()
{
    node[0]=0;
    sum[0]=0;
    node[1]=1;
    sum[1]=1;
    for(int i=2; i<31;++i)
    {
        node[i]=node[i-1]*2;
        sum[i]=node[i];
    }

    for(int i=2; i<31; ++i)
    {
        sum[i]=sum[i]+sum[i-1];
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
    long long tree4(long long n) {
        // write code here
        init();
        long long rt=0;

        if( 0==n )
        {
            return 0;
        }

        if( 1==n )
        {
            return 1;
        }


        int num=1;
        for(; num<31; ++num)
        {
            if( sum[num]>=n )
            {
                break;
            }
        }


        for(int i=1; i<num; ++i)
        {
            long long a=sum[i-1]+1;
            long long b=sum[i];
            long long cheng=(a+b)*(b-a+1)/2%maxn;
            long long temp=i*cheng%maxn;
            rt+=temp;
            rt%=maxn;
        }



        long long  a=sum[num-1]+1;
        long long b=n;
        long long cheng=(a+b)*(b-a+1)/2%maxn;

        long long temp=num*cheng%maxn;
        rt+=temp;
        rt%=maxn;

        return rt;
    }
};

三、C 牛牛组数

C 牛牛组数传送门

坑点：static const int maxn=100005;一行，在第一次提交的时候，没有加static关键字，“运行超时”，通过该90%样例
加上static之后，就AC了。

• 解法：模拟+贪心

static const int maxn=100005;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最大和的字符串
     * @param x string字符串 即题目描述中所给字符串
     * @param k int整型 即题目描述中所给的k
     * @return string字符串
     */

    //数字化后a>=0，b>=0
    string add(string a,string b)
    {
        string ans;
        int aa[maxn]= {0};
        int bb[maxn]= {0};

        int lenA=a.size();
        int lenB=b.size();

        for(int i=0; i<lenA; i++) 
        {
            aa[lenA-1-i]=a[i]-'0';
        }
        for(int i=0; i<lenB; i++) 
        {
            bb[lenB-1-i]=b[i]-'0';
        }

        int num=max( lenA, lenB);

        for(int i=0; i<num; i++) 
        {
            aa[i]+=bb[i];
            aa[i+1]+=aa[i]/10;
            aa[i]%=10;
        }

        if(aa[num]) 
        {
            ++num;
        }
        for(int i=num-1; i>=0; i--) 
        {
            ans+=aa[i]+'0';
        }

        return ans;
    }

    string Maxsumforknumers(string x, int k) {
        // write code here
        sort(x.begin(),x.end());
        reverse(x.begin(),x.end());

        --k;
        string rt="0";
        while(k--)
        {
            rt=add(rt,string(1,x.back()));
            x.pop_back();
        }
        rt=add(rt,x);
        return rt;
    }
};