牛客编程巅峰赛S2第2场 - 青铜&白银&黄金

A 热心的牛牛
解题思路：想要给n个朋友分严格比自己多的糖，自己又想要分尽可能多的糖，那么假设朋友分得x个糖，自己分得b个糖，x=b+1时自己的糖最多，即（b+1）*n+b=k，b=（k-n）/（n+1）。

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

B 牛牛切木棒
解题思路：三角形的任何两边之和都大于第三边，只要分出的段中任何两边之和都小于等于第三边即可，假设分成了n段，a[1],a[2]...a[n],则保证 a[i]>=a[i-1]+a[i-2] 即可，取等号时每个段最小分出的段数最多，分出的段即是斐波那契数列，数列和大于木棒长度时，最后一段不足的木棒长度加到上一个木棒上即可，也能保证上述不等式成立（这点比赛的时候没想到，卡了=.=），以下两个代码均可。

class Solution {
public:
    /**
     * 
     * @param a long长整型 木棒的长度
     * @return int整型
     */
    long long f[100]={1,1};
    int stick(long long a) {
        // write code here

        for(int i=2;i<64;i++)f[i]=f[i-1]+f[i-2];
        int t=0;
        while(f[t]<=a){
            t++;
            a=a-f[t-1];
        }
        return t;
    }
};

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

C Tree II
解题思路：完全k叉树，第i个结点的父结点编号为(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) {
        // write code here
        int n=a.size();
        long long ans=0;
        for(int i=1;i<n;++i){
            ans+=a[i]^a[(i-1)/k];
        }
        return ans;
    }
};

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=1,m=a.size();
        queue<int>q;
        q.push(a[0]);
        while(!q.empty())
        {
            if(n==m)break;
            int d=q.front();
            q.pop();
            for(int i=1;i<=k;++i)
            {
                if(n<m){
                   ans+=d^a[n];
                   q.push(a[n]);
                   n++;
                }
            }
        }
        return ans;
    }
};