CodeForces 962D Merge Equals

洛谷题目页面传送门 & codeforces题目页面传送门

题意见洛谷里的翻译。

这道题有\(\bm2\)种方法。

---

方法\(\bf1\)：

把所有数以数本身为第一关键字，下标为第二关键字压入堆，这样所有相同的数就可以挨在一起了。当堆里还有至少\(1\)个元素时，不断地从堆顶取两个元素，如果相等，就将它们弹出并且将它们相加的和再压入堆中，否则说明再也没有数能够与第一个取的数合并了（因为以后取的数会更大，没有更大的数的两倍会变小），便将它弹出并压入答案序列里。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long//防爆int
struct cmp{//堆的比较方式
    bool operator()(pair<int,int> x,pair<int,int> y){
        if(x.first!=y.first)return x.first>y.first;//以数本身为第一关键字
        return x.second>y.second;//下标为第二关键字
    }
};
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> q;//堆
struct cmp0{//存储答案的堆的比较方式
    bool operator()(pair<int,int> x,pair<int,int> y){
        return x.second>y.second;//以下标比较，以便从左往右输出
    }
};
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp0> q0;//存储答案
signed/*int已经被define成long long了，只能用signed*/ main(){
    int n/*数的个数*/,i;cin>>n;
    for(i=1;i<=n;i++){
        int x;cin>>x;
        q.push(make_pair(x,i)/*数是pair的第一元，下标是第二元*/);//压入堆
    }
    while(q.size()>1){//当堆还剩至少2个元素时
        int x1/*数1*/=q.top().first,y1/*下标1*/=q.top().second;q.pop();//第一个数无论如何都要弹出，就先弹出了
        int x2/*数2*/=q.top().first,y2/*下标2*/=q.top().second;
        if(x1==x2)/*相等？*/q.pop()/*弹出第二个数*/,q.push(make_pair(x1<<1,y2/*保留第二个数的位置*/));//压入和
        else q0.push(make_pair(x1,y1));//第一个数进答案序列
    }
    q0.push(q.top());//堆中剩下的那个孤独的数也是要进答案序列的
    cout<<q0.size()<<"\n";
    while(q0.size())cout<<q0.top().first<<" ",q0.pop();
    return 0;
}

---

方法\(\bf2\)：

先把所有的数中的因数\(2\)全部除干净，然后将原来的\(0\sim n-1\)的访问顺序进行以除了因数\(2\)之后的数为第一关键字、原数为第二关键字、下标为第三关键字排序，这样相当于做了一次分类，将可能能合并的，即除了因数\(2\)之后的数相同的数放在了一起，每一类中又将相同的数放在了一起。接下来访问每一类（这里不需要考虑顺序不合题意的问题，因为类与类之间不会互相干涉）。对于每一类，又分几轮访问，每轮访问访问相同的数。在每轮中，第奇数次访问时，如果已经访问完了，就将它加入答案序列（因为再也没有数可以与它合并了）并退出这一轮；第偶数次访问时，将前一次访问的数与它合并（因为访问顺序的第三关键字是下标，所以第偶数次的下标一定是比前一次大的中最小的，符合题意），此时它已经变成了原来的\(2\)倍，然后让它在下一轮被访问到。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[150000]/*原数*/,b[150000]/*除了因数2后的数*/,ord[150000]/*访问顺序*/,las[150000]/*上一轮加入到这一轮的下标*/,now[150000]/*这一轮要访问的下标*/,will_be_las[150000]/*即将加到下一轮的下标*/;
ll ans[150000];//答案序列
bitset<150000> isans;//是否加入了答案序列（用bitset比bool数组省空间）
bool cmp(int i,int j){//访问顺序的排序方式
    if(b[i]!=b[j])return b[i]<b[j];//以除了因数2后的数为第一关键字，可以让同类数挨在一起
    if(a[i]!=a[j])return a[i]<a[j];//以原数为第二关键字，可以让相等的数挨在一起
    return i<j;//以下标为第三关键字
}
int main(){
    int n/*数的个数*/,i,t=0/*答案个数*/,nlas/*las的大小*/,nnow/*now的大小*/,nwill_be_las/*
    will_be_las的大小*/;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",a+i);
        b[i]=a[i];while((b[i]&1)==0)b[i]>>=1;//除光因数2
        ord[i]=i;//访问顺序一开始是0~n-1
    }
    sort(ord,ord+n,cmp);//对访问顺序排序
    for(int l=0/*目前的类的区间左端点*/,r=0/*右端点*/;l<n;l=r/*下一类*/){//区间前闭后开
        while(r<n&&b[ord[r]]==b[ord[l]])r++;//算出右端点
        nlas=0;//清空las
        ll val=a[ord[l]];//此轮的所有数的值
        int at=l;//此类的访问进度
        while(nlas/*即使at到了r，也可能有上一轮的余留*/||at<r){
            nnow=nwill_be_las=0;//清空
            while(at<r&&a[ord[at]]==val)now[nnow++]=ord[at++];//整理此轮要访问的下标
            int atlas=0,atnow=0;//las、now的访问进度
            while(atlas<nlas||atnow<nnow){//当还有东西可访问时继续访问
                int x;
                if(atlas<nlas/*las还有*/&&(atnow==nnow||las[atlas]<now[atnow])/*now没了或las的更先访问*/)x=las[atlas++];//于是访问las的
                else x=now[atnow++];//否则访问now的
                if(atlas==nlas&&atnow==nnow)/*奇数次时访问完，剩下了*/{isans.set(x);ans[x]=val;t++;/*加入答案序列*/break;/*退出*/}
                if(atlas<nlas&&(atnow==nnow||las[atlas]<now[atnow]))x=las[atlas++];
                else x=now[atnow++];//同上
                will_be_las[nwill_be_las++]=x;//合并，给下一轮
            }
            nlas=nwill_be_las;for(i=0;i<nwill_be_las;i++)las[i]=will_be_las[i];//即将加到下一轮的该加到下一轮了
            val<<=1;//增大一倍
        }
    }
    printf("%d\n",t);
    for(i=0;i<n;i++)if(isans[i])printf("%lld ",ans[i]);
    return 0;
}

---

\(2\)种方法的时间复杂度都是\(\mathrm{o}(n\log_2n)\)，不过方法\(2\)的常数小一点（因为它的中间部分是\(\mathrm{o}(n)\)的，只是除光因数\(2\)和排序要了一点\(\mathrm{o}(n\log_2n)\)的时间而已，而方法\(1\)从头到尾一直多次使用堆，很显然是彻彻底底的\(\mathrm{o}(n\log_2n)\)）。方法\(2\)最大的一个测试点只用了\(93\mathrm{ms}\)，然而方法\(1\)也只用了\(452\mathrm{ms}\)。