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