ABC323D 题解

这个题笔者场上 Wa 了六次……

首先发现一个性质：

考虑单个的 \(s\)，它自己所能合并成的块就是 \(c\) 的二进制表示。

例如当 \(s=3,c=7\) 时，显然我们可以先两两合并，得到 \(3\) 个 \(s=6\) 的，再把其中的两个合并得到一个 \(s=12\) 的。

发现 \(7=(111)_2\)，正好最终只有三个块：\(s=3,6,12\)，即 \(s=3\times 2^0,3\times 2^1,3\times 2^2\)。

这个性质读者自己想一想就会明白的，想明白了再看下面的部分。

下面考虑“连环合并”的情况，类似于 \(3+3\to 6+6\to 12\) 这样。

如何把 \(s\) 的情况转移给 \(2s\) 呢？

由于 \(s\) 能合并出的就是 \(c\) 的二进制表示，那么 \(c\) 右移一位就是 \(2s\) 的表示了！

那还剩最后一位怎么办？

如果 \(s\) 是当前最小的块，那么没有人能合成它，于是如果剩下一个 \(s\) 没有合并，就一定不会再被合并了。如果最后一位是 \(1\) 答案加 \(1\)，直接扔掉就行。

由此，我们发现一定要从小到大依次合并。

具体来说，用一个 map 记录每个 \(s\) 对应的 \(c\)，从小到大遍历（一定是完全遍历！！！这是我最后一个 Wa 的点），用 \(s\) 更新 \(2s\)，并贡献答案。

可以证明每个 \(s\) 至多更新 \(\log_2{10^9} < 30\) 次，所以复杂度正确。

#define rep(i,x,y) for(int i=x;i<=y;i++)
const int N=1e5+5;
map<LL,LL> c;
map<LL,LL>::iterator it;
int n,ans;
int main(){
    n=read();
    rep(i,1,n) {
        LL x=read();
        c[x]=read();
    }
    for(it=c.begin();it!=c.end();++it){
        LL x=(*it).first,y=(*it).second;
        if(y>1) c[x<<1]+=(y>>1);
        //这里判断 y>1 只是为了降低时空复杂度，不加也行
        ans+=(y&1);
    }
    printf("%d\n",ans);
    return 0;
}