比赛链接：

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。插入元素与合并段的代码具体实现可以采用并查集，或者也可以直接采用类似链表的方式维护。

struct nod{
    int v,x;
    inline bool operator <(const nod &a)const{
        return v<a.v;
    }
};
class Solution {
public:
    /**
     * 找到所有长度子数组中最大值的最小值
     * @param numbers int整型vector 牛牛给出的数据
     * @return int整型vector
     */
    int f[110000],l[110000],r[110000];
    nod g[110000];
    int ans[110000];
    bool b[110000],hans[110000];
    int father(int x){
        if (f[x]!=x) f[x]=father(f[x]);
        return f[x];
    }
    void merge(int x,int y){
        int fx=father(x);
        int fy=father(y);
        if (fx!=fy){
            f[fx]=fy;
            if (l[fx]<l[fy]) l[fy]=l[fx];
            if (r[fx]>r[fy]) r[fy]=r[fx];
        }
    }
    vector<int> getMinimums(vector<int>& numbers) {
        // write code here
        //if (numbers.size()==1) return numbers;
        int n=numbers.size();
        for(int i=1;i<=n;++i){
            f[i]=l[i]=r[i]=i;
            g[i]=(nod){numbers[i-1],i};
            b[i]=hans[i]=0;
        }
        b[0]=b[n+1]=0;
        sort(g+1,g+n+1);
        for(int i=1;i<=n;++i){
            int &x=g[i].x;
            b[x]=1;
            if (b[x-1]) merge(x,x-1);
            if (b[x+1]) merge(x,x+1);
            int fx=father(x);
            int len=r[fx]-l[fx]+1;
            if (!hans[len]){
                hans[len]=1;
                ans[len]=g[i].v;
            }
        }
        for(int i=n-1;i>=1;--i){
            if (!hans[i]) ans[i]=ans[i+1];
            if (ans[i+1]<ans[i]) ans[i]=ans[i+1];
        }
        vector<int> v;
        for(int i=1;i<=n;++i) v.push_back(ans[i]);
        return v;
    }
};