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) 回帖