牛客编程巅峰赛S2第2场 - 钻石&王者 ABC

ABC题解
A牛牛切木棒
任意三个不能构成三角形，一定是：1，1，2，3，5……斐波那契数列，刚好任意三个一定满足a+b<=c

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    int stick(long long a) {
        // write code here
        if(a<=3)return 2;
        int nm=2;
        long long a1=1,a2=1,tmp;
        a-=2;
        while(a>0){
            tmp=a1+a2;
            a1=a2;
            a2=tmp;
            a-=tmp;
            if(a<0)break;
            nm++;
        }
        return nm;
    }
};

BTree II
比赛时写麻烦了，还分层写了下。。

其实我们观察发现：每个点的儿子节点刚好是k个，而且是连续的，

1号点的儿子是2，3，4，

2号点的儿子是5，6，7，

依此类推。

我们只需要枚举点，枚举其K个儿子，然后让儿子点序号加上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) {
        // write code here
        long long ans=0;
        for(int i=0,j=1;a.size();;i++)
        {
            for(int l=0;l<k&&j+l<n;l++)ans+=a[i]^a[j+l];
            j+=k;
        }
        return ans;
    }
};

C：数据分析
从问题本质去想：

连续K子数组最大值，的最小值。

对于任意一个数a[i],

他做为可以最大值的区间假如是：[L,R]，即max([a[L]->a[R]).

于是，当K小于等于R-L+1时，a[i]可以对最终最小值产生贡献。

到这里问题就解决了！

只要快速求出每个数做为最大值维护的区间即可。

这是单调栈的经典问题。

class Solution {
public:
    /**
     * 找到所有长度子数组中最大值的最小值
     * @param numbers int整型vector 牛牛给出的数据
     * @return int整型vector
     */
    int a[100007];
    int s[100007],p,l[100007],r[100007];
    vector<int> getMinimums(vector<int>& numbers) {
        // write code here
        int n =numbers.size();
        for(int i=1;i<=n;i++)a[i]=numbers[i-1];
        p=0;
        for(int i=1;i<=n;i++){
            while(p&&a[i]>=a[s[p]])p--;
            l[i]=s[p];
            s[++p]=i;
        }
        p=0;s[p]=n+1;
        for(int i=n;i>=1;i--){
            while(p&&a[i]>=a[s[p]])p--;
            r[i]=s[p];
            s[++p]=i;
        } 
        vector<int>ans;
        for(int i=1;i<=n;i++)ans.push_back(1e9+7);
        for(int i=1;i<=n;i++){
            int id=r[i]-l[i]-1;
            ans[id-1]=min(ans[id-1],a[i]);
        }
        for(int i=n-2;i>=0;i--)ans[i]=min(ans[i+1],ans[i]);
        return ans;
    }
};