首页 > 牛客编程巅峰赛S2赛季(高级场第1场)考题参考代码
头像
吴国庆
编辑于 2020-11-17 22:25
+ 关注

牛客编程巅峰赛S2赛季(高级场第1场)考题参考代码

Tree IV

注意到第i层的最多有2^(i-1)个结点,并且编号都是连续的即可答题
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 6;
const int mod = 998244353;


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param n long长整型 表示标准完全二叉树的结点个数
     * @return long长整型
     */
    long long tree4(long long n) {
        // write code here
        ll ans=0;
        for(ll i=1,cur=1,dep=1;n>0;i*=2,dep++) {
            ll len=min(i,n);
            ans=(ans+len*(cur+cur+len-1)/2%mod*dep%mod)%mod;
            cur+=i;
            n-=len;
        }
        return ans;
    }
};

牛牛组数

肯定是优先让位数最多,并且最高位最大,那么把x串排序后,分为后k-1个长度为1的数字,和一个长度为n-k+1的数字,模拟一下大数加法即可。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 6;
const int mod = 1e9+7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最大和的字符串
     * @param x string字符串 即题目描述中所给字符串
     * @param k int整型 即题目描述中所给的k
     * @return string字符串
     */
    string Maxsumforknumers(string x, int k) {
        // write code here
        sort(x.begin(),x.end());
        int ans=0;
        for(int i=0;i<k-1;i++) {
            ans=ans+x[i]-'0';
        }
        int n=x.length();
        string a="",b="";
        for(int i=k-1;i<n;i++) {
            a+=x[i];
        }
        while(ans) {
            char ch=ans%10+'0';
            b+=ch;
            ans/=10;
        }
        string c="";
        int la=a.length(),lb=b.length();
        int i=0,j=0,f=0;
        while(i<la&&j<lb) {
            int ch=a[i]-'0'+b[j]-'0'+f;
            f=ch/10;
            ch%=10;
            c+=char(ch+'0');
            i++;j++;
        }
        while(i<la) {
            int ch=a[i]-'0'+f;
            f=ch/10;
            ch%=10;
            c+=char(ch+'0');
            i++;
        }
        while(j<lb) {
            int ch=b[j]-'0'+f;
            f=ch/10;
            ch%=10;
            c+=char(ch+'0');
            j++;
        }
        if(f) c+='1';
reverse(c.begin(),c.end());
        return c;
    }
};



牛牛算题

整除分块,注意取模也是连续的即可复杂度O(sqrt(n))
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 6;
const int mod = 1e9+7;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回1-n的所有k*m的和
     * @param num long长整型 正整数 n
     * @return long长整型
     */
    long long cowModCount(long long n) {
        // write code here
        ll ans=0;
        for(ll l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            ll s=n%l,t=n%r;
            if(s>t) swap(s,t);
            ans += (r - l + 1)*(s + t)/2%mod * (n / l)%mod;
            ans%=mod;
        }
        return ans;
    }
};

全部评论

(6) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐