欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces 962D Merge Equals

程序员文章站 2023-04-04 19:58:13
"洛谷题目页面传送门" & "CodeForces题目页面传送门" 题意见洛谷里的翻译。 这道题有$\bm2$种方法。 方法$\bf1$: 把所有数以数本身为第一关键字,下标为第二关键字压入堆,这样所有相同的数就可以挨在一起了。当堆里还有至少$1$个元素时,不断地从堆顶取两个元素,如果相等,就将它们 ......

洛谷题目页面传送门 & 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}\)