牛客编程巅峰赛S2第2场——题解

谁践踏了优雅 2022-12-23 00:56 111阅读 0赞

#  牛客编程巅峰赛S2第2场——题解 #

## 热心的牛牛 ##

### 题目描述 ###

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

### 题解 ###

如果平均分配，计算牛牛和他的朋友最少都能获得多少糖果num

n u m = k / ( n + 1 ) num=k/(n+1) num=k/(n\+1)（向下取整）

然后计算余数是多少， m o d = k mod=k%(n+1) mod=k

直接进行判断：

1.  如果mod==n，则可以将剩余的糖果分给他的朋友一人一颗，这样所有的朋友的糖果数量都大于牛牛的糖果数量
2.  否则的话，就将牛牛的糖果数量-1，这样所有朋友的糖果数量也大于牛牛的糖果数量

### AC代码（cpp) ###

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 num=k/(n+1);
            long long mod=k%(n+1);
            if(mod==n) return num;
            return num-1;
        }
    };

## 牛牛切木棒 ##

### 题目描述 ###

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

### 题解 ###

如果要构成三边能构成三角形的话需要满足两个条件：1.两边之和大于第三边；2.两边之差小于第三边

于是要是得任意三边都不能构成三角形的话，则需要构造，可以直接从1开始往后推，不难发现有个规律：

当满足这样一个序列：1、1、2、3、5…时，任意三边都不能构成三角形，而这个序列恰好是**斐波拉契数列**

故：此题可解，直接求出在\[0,1e18\]区间中所有的斐波拉契数列值，保存到一个数组中。

然后遍历这个数组，当当前遍历的斐波拉契数组的前缀和大于输入的值时，则证明找到了木棒能被分成的最大段数

### AC代码（cpp） ###

class Solution {
        
    public:
        /**
         * 
         * @param a long长整型 木棒的长度
         * @return int整型
         */
        int stick(long long a) {
        
            // write code here
            //保存[0,1e18]中所有斐波拉契数列值
            long long f[100];
            f[1]=1,f[2]=1;
            for(int i=3;;i++){
        
                f[i]=f[i-1]+f[i-2];
                if(f[i]>(long long)1e18) break;
            }
            int ans=0;
            for(int i=1;f[i]<=a;i++){
        
                a-=f[i];
                ans++;
            }
            return ans;
        }
    };

## Tree II ##

### 题目描述 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center]

### 题解 ###

直接按照题目要求就行，想复杂了。。。

n个结点的完全二叉树，现在需要对每个结点与它的父节点计算异或值，并求和。

直接层次遍历整棵树即可。

### AC代码（cpp） ###

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 n=a.size();
            long long ans=0;
            for(int i=0;i<n;i++){
        
                for(int j=i*k+1;j<=i*k+k&&j<n;j++){
        
                    ans+=(a[i]^a[j]);
                }
            }
            return ans;
        }
    };

## 数据分析 ##

### 题目描述 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center 1]

### 题解 ###

比较明显的单调栈题。

单调栈比较明显的特征求：滑动窗口中的最大值（最小值）或者是当前元素左边（右边）第一个比他大（小） 的元素位置

这题可以维护一个单调递增栈（当前元素大于栈顶元素时，栈顶元素出栈；否则当前元素入栈）

用left\[\]，right\[\]分别保存左边和右边第一个比他小的数（左边不能取等右边可以取等，原因因为是求最大值嘛）

用ans\[\]记录窗口长度为i时的结果

### AC代码（cpp） ###

#define inf 0x3f3f3f3f
    class Solution {
        
        
    public:
        /**
         * 找到所有长度子数组中最大值的最小值
         * @param numbers int整型vector 牛牛给出的数据
         * @return int整型vector
         */
        vector<int> getMinimums(vector<int>& numbers) {
        
            // write code here
            int n=numbers.size();
            //left[i]:第i个元素左边第一个比它小的元素的位置，right[i]:第i个元素右边第一个比它大的元素的位置
            vector<int> left(n),right(n);       
            
            stack<int> sta;
            for(int i=0;i<n;i++){
        
                while(!sta.empty()&&numbers[i]>numbers[sta.top()]) sta.pop();
                if(sta.empty()) left[i]=-1;
                else left[i]=sta.top();
                sta.push(i);
            }
            while(!sta.empty()) sta.pop();
            for(int i=n-1;i>=0;i--){
        
                while(!sta.empty()&&numbers[i]>=numbers[sta.top()]) sta.pop();
                if(sta.empty()) right[i]=n;
                else right[i]=sta.top();
                sta.push(i);
            }
            
            vector<int> ans(n,inf);
            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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c66431f8345d4b9fa20162fd7b10bf52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/ff34888827704769b41c4de992b42333.png