腾讯音乐笔试4.18

• 按照题意模拟即可，每两项插入0，特判null节点

   ListNode* insert0(ListNode* head) {
        ListNode* ret=head;
        while(head){
            ListNode* nxt=head->next;
            ListNode* p=new ListNode(0);
            if(nxt!=nullptr){
                head->next=p;
                p->next=nxt;
            }
            head=nxt;
        }

        return ret;
    }

• 构造，可以知道最后一层节点有 \frac{2}{n-1}，则根节点权值给\frac{2}{n-1} 往下递归时，子节点值为根节点/2即可

  void dfs(int d,TreeNode* cur,int n){
        if(d==n) return;
        cur->left=new TreeNode((cur->val)/2);
        cur->right=new TreeNode((cur->val)/2);
        dfs(d+1,cur->left,n);
        dfs(d+1,cur->right,n);
     }
    TreeNode* create(int n) {
        TreeNode* root=new TreeNode(1<<(n-1));
        dfs(1,root,n);

        return root;
    }

• 先算出R的所有和，若为奇数，则需要在没染色的奇数格子里选奇数个方块，假设有odd个，方案数有C(odd,1)+C(odd,3)+...,偶数格子里任选,每个格子选和不选两种情况，方案数为qmi(2,even)，两者相乘即可，若为偶数，则奇数方案数为C(odd,0)+C(odd,2)+...，偶数任选，两者相乘

 typedef long long ll;
     const ll N=2e5+10;
     ll a[200005],cnt=0,mod=1e9+7;
     ll fact[200005],inv[200005];
    int getMethod(ListNode* head, string colors) {
        // write code here
        ListNode* cur=head;
        while(cur){
            a[cnt++]=cur->val;
            cur=cur->next;
        }
        fact[0]=inv[0]=1;
        for(ll i=1;i<=cnt;i++){
            fact[i]=fact[i-1]*i%mod;
            inv[i]=qmi(fact[i],mod-2,mod)%mod;
        }
        ll s=0,odd=0,even=0;
        for(ll i=0;i<cnt;i++){
            if(colors[i]=='R') s+=a[i];
            else{
                odd+=(a[i]&1);
                even+=(a[i]%2==0);
            }
        }
       // cout<<s<<" "<<odd<<" "<<even<<endl;
        if(s&1){
            if(odd){
                ll ans=1,res=0;
                for(int i=1;i<=odd;i+=2){
                    res=(res+C(odd,i))%mod;
                }
                ans=res*qmi(2,even,mod)%mod;
                return ans;
            }
            else return 0;
        }else{
            cout<<s<<" "<<odd<<" "<<even<<endl;
            ll ans=1;
            ll res=0;
            for(int i=0;i<=odd;i+=2){
                res=(res+C(odd,i))%mod;
            }
            ans=res*qmi(2,even,mod)%mod;
            cout<<ans<<endl;
            return ans;
        }
    }
    ll C(ll x,ll y){
        return (((fact[x]*inv[y])%mod)*inv[x-y])%mod;
    }
    ll qmi(ll x,ll y,ll mod){
        ll res=1;
        while(y){
            if(y&1) res=res*x%mod;
            y>>=1;
            x=x*x%mod;
        }
        return res;
    }

• 二分答案最后的最小连续1长度x是多少，问题转化为把一段连续1，转化成1连续长度不超过x，那么假设这段1长度为len，每x+1个1，就需要变1个0，分隔开他们，所以贡献值是len/(x+1)，累加所有的len长度，判断贡献值和sum是否<=题目给出的最大操作数k即可

bool check(string& s,int x,int k){
        int res=0;
        for(int i=0;i<s.size();i++){
            int j=i;
            if(s[i]=='1'){
                int j=i;
                while(j+1<s.size()&&s[j+1]=='1'){
                    j++;
                }
                int len=j-i+1;
                if(len>x){
                    res+=len/(x+1);
                }
                i=j;
            }
        }
        cout<<x<<" "<<res<<" "<<k<<endl;
        return res<=k;
    }
    int maxLen(string s, int k) {
        // write code here
        int l=0,r=s.size();
        while(l<r){
            int mid=l+r>>1;
            if(check(s,mid,k)) r=mid;
            else l=mid+1;
        }

        return l;
    }