牛客编程巅峰赛S2第1场 - 钻石&王者
Tree IV
https://ac.nowcoder.com/acm/contest/9005/A
A:Tree IV
刚开始看错题目,以为n<=100000.。。
直接写个二叉树遍历。。T了,然后快速改了下,分层等差数列统计即可。。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n long长整型 表示标准完全二叉树的结点个数 * @return long长整型 */ long long ans=0,mod=998244353; long long tree4(long long n) { // write code here ans=0; long long tp=1,dep=1; while(tp<=n){ long long r=min(2*tp-1,n); ans=(ans+dep*((tp+r)*(r-tp+1)/2%mod)%mod)%mod; tp=r+1; dep++; // cout<<tp<<" "<<r<<" "<<ans<<endl; } return ans; } };
B:牛牛组数
简单的贪心,一定是一个最大的串+一堆单个的,最小的数。
模拟求和即可。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回最大和的字符串 * @param x string字符串 即题目描述中所给字符串 * @param k int整型 即题目描述中所给的k * @return string字符串 */ int a[100007]; string Maxsumforknumers(string x, int k) { // write code here sort(x.begin(),x.end()); int n=x.length(),len=0; memset(a,0,sizeof(a)); for(int i=k-1;i<n;i++){ a[i-(k-1)]=x[i]-'0'; len++; // cout<<i-(n-k)<<" "<<a[i-(n-k)]<<" "<<len<<endl; } for(int i=0;i<k-1;i++){ a[0]+=x[i]-'0'; } int up=0; for(int i=0;i<n;i++){ if(a[i])up=i; if(a[i]>=10){ a[i+1]+=a[i]/10; a[i]%=10; } } string ans; for(int i=up;i>=0;i--){ ans+=a[i]+'0'; } return ans; } };
C:牛牛算题
显然是:
然后用整数分块搞一下即可。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回1-n的所有k*m的和 * @param num long长整型 正整数 n * @return long长整型 */ long long cowModCount(long long num) { // write code herek=n; long long ans=0,k=num,n=num,mod=1e9+7; //分块k/i 从1->n for(long long l=1,r;l<=n;l=r+1) { r=(k/l)?min(k/(k/l),n):n;//取min防止r超出边界 long long x=k/l; //n*x- x*2*i ans=(ans+n*x%mod*(r-l+1)%mod)%mod; ans=(ans-x*x%mod*((l+r)*(r-l+1)/2%mod)%mod+mod)%mod; // cout<<l<<" "<<r<<" "<<x<<" "<<ans<<endl; } return ans; } };