求调 D
  • 板块学术版
  • 楼主sunkuangzheng
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/2 18:06
  • 上次更新2023/11/2 16:30:52
查看原帖
求调 D
679936
sunkuangzheng楼主2023/10/2 18:06

计算所有节点的编号和挂了,思路是考虑所有叶子节点深度差不超过 11,先算前面满二叉树编号和,再找规律算最后一层不满的。

void solve(){
    if(n == 1) return cout << (m ? -1 : 1) << "\n",void();
    int k = __lg(n - 1) + 1,p = (1ll << k) - 1,sm = p + (n - (1ll << (k - 1))) * 2,bs = sm - p,qs = bs;
    if(m > sm - 1) return cout << "-1\n",void();
    int ans1 = p * (p + 1) / 2;
    int sb = 3,d = 1,res = (1ll << k) * 2 + 1;bs -= 2;
    while(bs >= (1ll << d)) res += sb * (1ll << (k - d)) * 2 + (1ll << (d-1)),bs -= (1ll << d),d ++,sb *= 4;
    int q = bs / 2,fu = (1ll << d) + 1;
    if(q > 0) res += ((fu + fu + 2 * (q - 1)) * q / 2) * (1ll << (k-d)) * 2 + q;
    cout << (long long)(res + ans1) << "\n";
    if(!m) write((max((res + ans1) / (k + 1),ans1 / k))),cout << "\n";
    else{
        m -= qs;int fk = k;
        while(m > 0) m -= (1ll << (-- fk));
        int pp = (1ll << fk) - 1;
        write(((pp * (pp + 1) / 2 / fk))),cout << "\n";
    }
}
2023/10/2 18:06
加载中...