牛客编程巅峰赛S2第2场

-> 青铜&白银&黄金
https://ac.nowcoder.com/acm/contest/9223
钻石&王者
https://ac.nowcoder.com/acm/contest/9224
2020-11-20 20:00:00 至 2020-11-20 21:00:00
时长: 1小时
AC 2/3
Rank 261/768
罚时 00:53:22
A (534/2635) 00:05:31
B (361/1170) (-5)
C (274/669) 00:47:51

A 热心的牛牛

牛牛是个非常热心的人，所以他有很多的朋友。这一天牛牛跟他的个朋友一起出去玩，在出门前牛牛的妈妈给了牛牛块糖果，牛牛决定把这些糖果的一部分分享给他的朋友们。由于牛牛非常热心，所以他希望他的每一个朋友分到的糖果数量都比牛牛要多（严格意义的多，不能相等）。牛牛想知道他最多能吃到多少糖果？

A.1 比赛时AC

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回牛牛能吃到的最多糖果数
     * @param n long长整型 
     * @param k long长整型 
     * @return long长整型
     */
    long long Maximumcandies(long long n, long long k) {
        // write code here
        long long e=k/(n+1),m=k%(n+1);
        if(m==n)return e;
        return e-1;
    }
};

A.2 讲解1 二分法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回牛牛能吃到的最多糖果数
     * @param n long长整型 
     * @param k long长整型 
     * @return long长整型
     */
    long long Maximumcandies(long long n, long long k) {
        // write code here
        long long left=0,right=k,ans=0;
        while(left<=right){
            long long mid=(left+right)/2;
            if(check(n,k,mid)){
                ans=mid;
                left=mid+1;
            }
            else{
                right=mid-1;
            }
        }
        return ans;
    }
    bool check(long long n,long long k,long long mid){
        return (__int128_t)(mid+1)*n+mid<=k;
    }
};

1e18

A.3 讲解2 解不等式

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回牛牛能吃到的最多糖果数
     * @param n long长整型 
     * @param k long长整型 
     * @return long长整型
     */
    long long Maximumcandies(long long n, long long k) {
        // write code here
        return (k-n)/(n+1);
    }
};

B 牛牛切木棒

牛牛有一根长度为的木棒，现在牛牛想将木棒分成一些段（每段木棒长度必须为整数），使得分隔后的木棍中，任意三段都不能构成三角形，牛牛想知道木棒最多被分成几段呢？

B.1 比赛时一直错误

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    int stick(long long a) {
        // write code here
        int count=2;
        long long last=1,n=1,sum=2;
        while(sum<=a){
            n+=last;
            sum+=n;
            last=n;
            count++;
        }
        //if(sum==a)return count;
        return --count;
    }
};

知道是斐波那契数列，但是写错了。。
只有一个last 导致后面是翻倍。。
1 1 2 4 8 16.。。

B.2 讲解

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    int stick(long long a) {
        // write code here
        long long arr[61];
        arr[0]=1;arr[1]=1;
        for(int i=2;i<=60;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        long long sum=0;
        for(int i=0;i<=60;i++){
            sum+=arr[i];
            if(sum>a){
                return i;
            }
        }
    }
};

B.3 按照讲解思路写的

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    long long f[100]={1,1},sum=2;
    int stick(long long a) {
        // write code here
        for(long long i=2;i<100;i++){
            f[i]=f[i-1]+f[i-2];
            sum+=f[i];
            if(sum>=a)return i;
        }
        return 0;
    }
};

B.4 把比赛时代码修改

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    int stick(long long a) {
        // write code here
        int count=2;
        long long ll=1,last=1,n,sum=2;
        while(sum<a){
            n=ll+last;
            sum+=n;
            ll=last;
            last=n;
            count++;
        }
        return count-1;
    }
};

一个上次last 一个上上次 ll

C Tree II

C.1 比赛时AC

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree2(int k, vector<int>& a) {
        // write code here
        long long sum=0;
        int i;
        for(i;i<a.size();i++){
            //if(i*k+1>=a.size())break;
            if((i+1)*k>=a.size())break;
            long long tmp=0;
            for(int j=0;j<k;j++){
                tmp+=a[i]^a[i*k+1+j];
            }
            sum+=tmp;
        }
        long long tmp=0;
        for(int j=i*k+1;j<a.size();j++){
                tmp+=a[i]^a[j];
            }
        sum+=tmp;
        return sum;
    }
};

叉树，的子节点为
最后一个子节点不完全的单独算。

C.2 讲解1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree2(int k, vector<int>& a) {
        // write code here
        int curPos=1;
        int n=a.size();
        long long ans=0;
        queue<int> eq;
        eq.push(a[0]);
        while(!eq.empty()){
            if(curPos==n)break;
            int now=eq.front();
            eq.pop();
            for(int i=1;i<=k;i++){
                if(curPos<n){
                    ans+=now^a[curPos];
                    eq.push(a[curPos]);
                    curPos++;
                }
            }
        }
        return ans;
    }
};

BFS中 根节点最先进队

1. 找到当前节点
2. 连接所有儿子

C.3 更优雅一点

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    long long tree2(int k, vector<int>& a) {
        // write code here
        long long ans=0;
        int n=a.size();
        int curPos=1;
        for(int i=0;i<n;i++){
            if(curPos==n)break;
            for(int j=0;j<k;j++){
                if(curPos<n){
                    ans+=a[i]^a[curPos];
                    curPos++;
                }
            }
        }
        return ans;
    }
};

1. 出队
2. 找下一个点儿子

D 数据分析

作为一个优秀的程序员，牛牛喜欢钻研各种技术。最近，牛牛就在研究数据分析有关技术。
牛妹给了牛牛一批商品销量数据，想让牛牛帮忙分析。作为经典的指标，一段时间内的最高销量是一个很好的研究起点，牛牛就打算研究某个长度的子数组中的最高销量中的最小值。
举例子来说，考虑销量序列 [1,3,5,2,4,6]，我们考虑长度为 3 的子数组，从左到右分别为[1,3,5],[3,5,2],[5,2,4]和[2,4,6]，最高销量分别为[5,5,5,6] ，最高销量中的最小值为 5。
然而，牛妹觉得这个仍然不是很直观，她提出了一个更进一步的问题：能不能找出 中每个长度的子数组中最高销量的最小值？举例子来说，对于 [1,3,5,2,4,6]，我们已经求出来了 k=3 时候的最小值为 5，牛妹还想要其他长度的最小值。
虽然牛牛对数据很敏感，但是解决这个问题对他来说还是有点困难了，希望你能完善函数，帮他解决这个问题。牛牛将把这 N 个销量数据给你，你需要返回一个长度恰好为 N 的序列，第一个元素为长度为 1 的答案，第二个元素为长度为 2 的答案，以此类推。

D.1 讲解

class Solution {
public:
    /**
     * 找到所有长度子数组中最大值的最小值
     * @param numbers int整型vector 牛牛给出的数据
     * @return int整型vector
     */
    vector<int> getMinimums(vector<int>& numbers) {
        // write code here
        int n=numbers.size();
        vector<int> right(n,n),left(n,-1);
        stack<int> st;
        for(int i=0;i<n;i++){
            while(!st.empty()&&numbers[st.top()]<numbers[i]){
                right[st.top()]=i;
                st.pop();
            }
            if(!st.empty()){
                left[i]=st.top();
            }
            st.push(i);
        }
        vector<int> ans(n,0x3f3f3f3f);
        for(int i=0;i<n;i++){
            int len=right[i]-left[i]-1;
            ans[len-1]=min(ans[len-1],numbers[i]);
        }
        for(int i=n-2;i>=0;i--){
            ans[i]=min(ans[i],ans[i+1]);
        }
        return ans;
    }
};

单调栈
类似

1. 滑动窗口的最大值
2. 直方图内最大矩形