t2: Tree IV

  1. 同一层的坐标 要相乘的 层数 都是一样,所以同层的坐标可以用等差数列求和
  2. 注意取模的问题,特别是除法 a/b%mod!=(a%mod)/(b%mod)%mod ,除法要用到逆元,这题范围没那么大,所以可以求完除法再取模
    typedef long long ll;
    class Solution {
     ll mod=998244353;
    public:
     long long tree4(long long n) {
         ll ans=0;
         ll level=1;
         ll num=1;
         ll st=1,ed=1;
         while (n>0)
         {
             ans+=sum(st,ed)*level%mod;
             ans%=mod;
             n-=num;
             ++level;
             num*=2;
             st*=2;
             ed=min(ed*2+1,st+n-1);
         }
         return ans;
     }
     ll sum(ll a,ll b)
     {
         ll n=b-a+1;
         return n*(a+b)/2%mod;
     }
    };

t3:牛牛组数

  1. 显然是贪心,位数越长越有利
  2. 所以先对题目给的字符串按照逆序排列,且第一个取的串尽可能的长,让剩下的k-1个数字都只有一个字符
  3. 剩下就是字符串相加了,但是字符串相加很慢,一个优化就是,既然剩下k-1个数字都是一个字符,即都是单个数字,可以先求和这k-1个数字
  4. 最后只用一次字符串相加:第一个贪心得来的超长的字符串 + 剩下k-1个数字的和后的字符串
class Solution {
public:
    string Maxsumforknumers(string x, int k) {
        sort(x.rbegin(),x.rend());
        if (k==1)
            return x;
        int x_size=x.size();
        if (k==x_size)
        {
            int ans=0;
            for (char i:x)
                ans+=i-'0';
            return to_string(ans);
        }
        string num1=x.substr(0,x_size-k+1);
        int n2=0;
        for (int idx=x_size-k+1;idx<x_size;++idx)
            n2+=x.at(idx)-'0';
        string num2=to_string(n2);
        string ans;
        int i=num1.size()-1,j=num2.size()-1;
        int sum;
        int num1_i,num2_j;
        int carry=0;
        while (i>=0 || j>=0)
        {
            num1_i= i>=0 ? num1.at(i)-'0' : 0;
            num2_j= j>=0 ? num2.at(j)-'0' : 0;
            sum=carry+num1_i+num2_j;
            ans+=(sum%10+'0');
            carry=sum/10;
            --i;
            --j;
        }
        if (carry==1)
            ans+='1';
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

t4.牛牛算题

  1. 旭日东升BJFU的题解里的这个图很强

图片说明

  1. 剩下一个整数分块
  2. 然后再用到等差数列求和
typedef long long ll;
/*
 * n=p*k+m 求p从1~n,所有的k*m求和
 * 即 sum((n/p) * (n%p))
 * 即 sum((n/p) * (n-n/p*p))
 * 整数分块,即在一定区间内n/p都是一个值,根据结果反推p的取值范围
 * int(num/i)=C
   i在[l,r]的一个区间,只需要知道l
   C=num/l
   r=num/(num/l)
 * 递归下去就是l=r+1
 */
class Solution {
    ll mod=1e9+7;
public:
    long long cowModCount(long long num) {
        ll ans=0;
        ll l=1,r,C;
        while (l<num)
        {
            r=num/(num/l);
            C=num/l;
            ll cnt=r-l+1;
            ll sum_p=sum(l,r);
            ans+=C*(cnt*num%mod-C*sum_p%mod+mod)%mod;
            ans%=mod;
            l=r+1;
        }
        return ans;
    }
    ll sum(ll a,ll b)
    {
        ll n=b-a+1;
        return n*(a+b)/2%mod;
    }
};