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

https://ac.nowcoder.com/acm/contest/9004
2020-11-17 20:00:00 至 2020-11-17 21:00:00
时长: 1小时
AC 1/3
Rank 459/853
罚时 00:26:10
A (719/3034) 00:16:10 (-2)
B (222/1915) (-8)
C (173/523)

本来人就菜,还好久好久没有做过题了,只通过了一道,问题很多。复盘一下。

A 最小差值

https://ac.nowcoder.com/acm/contest/9004/A
给你一个数组aa,请你求出数组a中任意两个元素间差的绝对值的最小值。

A.1 比赛时AC (现已不能AC,测试数据被改了)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型vector 数组a
     * @return int整型
     */
    int minDifference(vector<int>& a) {
        // write code here
        vector<int> v(a);
        sort(v.begin(),v.end());
        int d=abs(a[0]-a[1]);
        for(vector<int>::iterator i=v.begin();i!=v.end()-1;i++){
            int t=abs(*i-*(i+1));
            if(t<d)d=t;
        }
        return d;
    }
};

比赛时可以AC,但后来测试数据改了,比赛结束后已经不能通过,只能90.91。
问题1. 输入的a是引用,而不是const,没必要再复制一份才排序。
问题2. 最小值的初值当然可以取abs(a[0]-a[1]),但对于int更简单的方式是INT_MAX。
问题3. vector容器不用非得用迭代器,当数组用就行了。
问题4. 虽然返回值是int但计算中可能会溢出,后面测试数据改了就暴露了这个问题。

A.2 听讲解后写的 (未来以这个为准即可)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型vector 数组a
     * @return int整型
     */
    typedef long long LL;
    int minDifference(vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        LL m=LLONG_MAX;
        for(int i=1;i<a.size();i++){
            m=min(m,1ll*abs(a[i]-a[i-1]));
        }
        return (int)m;
    }
};
  1. 为了解决问题4,换用long long,为了简便可以用typedef起个别名。
  2. 与 INT_MAX 类似 long long 的上限为 LLONG_MAX。
  3. 不用写if判断谁小,直接用min函数一步到位。
  4. 写1的话,参与运算还是会出错,long long 中要写 1ll。
  5. 返回的时候再把 long long 转回int

A.3 what if 强行修改比赛时的版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型vector 数组a
     * @return int整型
     */
    int minDifference(vector<int>& a) {
        // write code here
        vector<int> v(a);
        sort(v.begin(),v.end());
        long long d=abs(a[0]-a[1]);
        for(vector<int>::iterator i=v.begin();i!=v.end()-1;i++){
            long long t=abs((long long)(*i)-(long long)(*(i+1)));
            if(t<d)d=t;
        }
        return (int)d;
    }
};
  1. 主要是为了避免溢出,把d,t类型设置成long long还有读取的 *i *(i+1) 转换成 long long。
  2. 返回时转换成int。

B Tree IV

https://ac.nowcoder.com/acm/contest/9004/B
给出一棵有个结点的标准的完全二叉树(即,若父结点编号为,则它的两个子结点的编号分别为),定义每个结点的价值为,即每个点的编号乘以每个点的深度(深度即为从根结点到这一结点最短路径经过的点的个数,定义根结点1的深度为1)。

请你求解这棵树中每个结点的价值和(由于答案可能会很大,请你对998244353取模),即

完全二叉树:若设二叉树的深度为,除第 层外,其它各层 的结点数都达到最大个数,第 层所有的结点都连续集中在最左边。
例如(图为一棵标准的完全二叉树):
图片说明

B.1 比赛时一直有错

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
    long long tree4(long long n) {
        // write code here
        long long m=n;
        long long l=1;
        while(m>1){
            m=m>>1;
            l++;
        }
        long long excess=n-(1<<l);
        long long sum=0;
        for(long long i=1;i<=l;i++){
            if(i<=l-1){
                sum+=(i*(((1<<(i-1))+((1<<i)-1))*(1<<(i-1))/2))%998244353;
            }else{
                sum+=(i*(((1<<(i-1))+n)*(n-((1<<(i-1))-1))/2))%998244353;
            }

            sum=sum%998244353;
        }
        return sum;
    }
};

问题1. excess用到了n,但excess本身没用到,也就不用把n再复制成一个m了。啊后面用到了,没问题,excess删了就行。
问题2. long long 可以像A题一样,typedef起个别名。
问题3. l其实用不到long long 但也没问题吧。
问题4. 计算每层最左最右节点编号时,太不直观了,不如定义两个变量出来,也可以更方便的处理不完全的层数。
问题5. sum累加的取余了,累加后的结果没有取余,会导致溢出。啊后面也取余了,没问题。
问题6. 可以把取余用到的大整数定义成常量啊。
问题7. i*等差数列求和可能溢出了,不如先取个余。
问题8. 1<<i 不对 得 1ll<<i。

B.2 听讲解后写的

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
    typedef long long LL;
    const LL Mod=998244353;
    long long tree4(long long n) {
        // write code here
        LL layer=0,sum=0,x,y,dep=1;
        for(LL i=1;i<=n;i*=2){
            x=i;
            if(i*2<=n){
                y=i*2-1;   
            }else{
                y=n;
            }
            layer=((x+y)*(y-x+1))/2%Mod*dep%Mod;
            sum=(sum+layer)%Mod;
            dep++;
        }
        return sum;
    }
};
  1. typedef const 更直观。
  2. for 循环的结构,不用单独计算层数,一个计数器累计深度即可,更直观。
  3. 注意等差数列先乘起来保证是偶数再除2,不然就按整除***出错。
  4. 乘深度前先取个余防止溢出。
  5. 等差数列先乘起来取余再除2貌似会出错,有人说是精度打折了,不是很懂。???

B.3 强行修改比赛时的代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
    long long tree4(long long n) {
        // write code here
        long long m=n;
        long long l=1;
        while(m>1){
            m=m>>1;
            l++;
        }
        long long excess=n-(1<<l);
        long long sum=0;
        for(long long i=1;i<=l;i++){
            if(i<=l-1){
                sum+=((((1ll<<(i-1))+((1ll<<i)-1))*(1ll<<(i-1))/2))%998244353*i%998244353;
            }else{
                sum+=((((1ll<<(i-1))+n)*(n-((1ll<<(i-1))-1))/2))%998244353*i%998244353;
            }

            sum=sum%998244353;
        }
        return sum;
    }
};
  1. 换成1ll。
  2. 注意取余问题,很有意思,这里除2再取余就没问题。???

C 牛牛组数

https://ac.nowcoder.com/acm/contest/9004/C
牛牛现在有一个长度为n的只包含数字1-9的字符串x,牛牛想用这n个数字组成k个数。这k个数每个数至少要用字符串x中的一个数字,字符串x中的每个位置的字符要在这k个数中出现一次。牛牛想知道这k个数的和最大是多少。

组成数字的定义如下:
比如n=3的字符串x为“121”
如果k=3,那么组成k个数只有{1,1,2}这一种可能,和只有一种可能为4
如果k=2,那么组成k个数的方案有{11,2},{12,1},{21,1}三种可能,和最大为21+1=22
如果k=1,那么组成k个数的方案有{112},{121},{211}三种可能,和最大为211

C.1 比赛时的代码

太惨了,比赛就没做到这道题。

C.2 听了讲解后的代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最大和的字符串
     * @param x string字符串 即题目描述中所给字符串
     * @param k int整型 即题目描述中所给的k
     * @return string字符串
     */
    string Maxsumforknumers(string x, int k) {
        // write code here
        int num[100010]={0};
        int tong[10]={0};
        for(int i=0;i<x.size();i++){
            tong[x[i]-'0']++;
        }
        int p=9;
        for(int i=x.size()-k;i>=0;i--){
            while(p>=0&&!tong[p])p--;
            if(tong[p]){
                num[i]=p;
                tong[p]--;
            }
        }
        while(p>=0){
            if(tong[p]){
                num[0]+=p;
                tong[p]--;
            }else{
                p--;
            }
        }
        int i;
        for(i=0;i<100010;i++){
            int tmp=num[i];
            num[i]=tmp%10;
            num[i+1]+=tmp/10;
            if(tmp==0)break;
        }
        string str;
        for(i--;i>=0;i--){
            str+=('0'+num[i]);
        }
        return str;
    }
};

听了讲解所以直接写出来了。贪心法。
各位数字由大到小,拆成一个最长的数和一堆小的一位数。
原来总共n位数,拆成k个数。
最大的数只要留n-k+1位就好了,刚好是x.size-k到0。
剩下的全加到个位数上进位即可。
28行一开始,从桶里取数,桶中剩下的忘记--了,所以进了死循环,改了就对了。
讲解的思路很流畅,不用直接存到数组中再排序,用桶就会简单很多。
从高位开始存数据的思路很重要。
进位计算很经典,得记一下。