牛客编程巅峰赛S2赛季第2场题解与参考代码

比赛链接：

https://ac.nowcoder.com/acm/contest/9223

https://ac.nowcoder.com/acm/contest/9224

初级场A题热心的牛牛：

不妨设牛牛获得x枚糖果，那么牛牛的朋友每人需要至少获得x+1枚糖果。那么这种情况下需要的总糖果数为x+n(x+1)，这个总数需要小于等于k。因此有x+n(x+1)<=k。整理得到(1+n)x+n<=k，合法的x值满足x<=(k-n)/(n+1)，因此输出该式下取整就是答案。

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

初级场B题&高级场A题牛牛切木棒：

这是比较经典的题目，使用斐波那契数列作为边长，可以使得任意三个数字不能作为一个三角形的边长。从小到大使用斐波那契数列的各项，就可以将木棒拆成若干个小木棒，任意三条木棒不能构成三角形。

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

初级赛C题&高级赛B题 Tree II：

根据完全k叉数的性质可以推导出，或者可以观察出bfs序为i(i>0)的点，其父结点在bfs序中的编号为(i-1)/k。利用这个性质扫描一遍即可完成统计。

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

高级赛C题数据分析：

这题我用了稍微复杂的方法，当做是抛砖引玉提供了另一种思路。思路大致是，（假设题目给定的输入是数组numbers）按照numbers中的数字大小从小到大考虑并维护答案。一开始不妨先当做numbers中所有数字都被拿掉了，然后按数字从小到大的顺序逐个放回numbers中的数字，那么某一时刻，numbers中只会存在一部分元素，在numbers中形成若干个连续段。假设现在从小到大考虑完的元素是numbers[i]，那么该时刻numbers中只会存在所有<=numbers[i]的所有数，之后考虑放入将numbers中所有数排序后的后继x，那么放入x后，可能会将其左右的两段连接成一个连续段。注意到目前放入numbers中的数都不大于x，因此当前numbers中存在的数形成的任何一个子区间最大值都不会大于x。考虑x所在的那么连续段，不妨设这个连续段的长度为l，那么x可以更新长度小于等于l的区间的区间最大值的答案，也就是说长度小于等于l的区间的区间最大值的最小值小于等于x。因此从小到大插入numbers中的元素，可以得到若干个上述ans[1..l]<=x的信息。最后利用这些信息就可以计算出ans。插入元素与合并段的代码具体实现可以采用并查集，或者也可以直接采用类似链表的方式维护。

牛客编程巅峰赛S2赛季第2场题解与参考代码

全站热榜