题解 P5032 【经验】

· · 题解

解法1：
我有信仰，我是MC玩家，输出-1。预计得分：15.

解法2：
我会特判，处理ai=1,n=1的情况，预计得分：15.

解法3：
我会暴力，直接模拟。时间复杂度 O(n^2) 。预计得分：30.

解法4：
我们发现，每次只要合并最小的两本书，然后合并。再往上找。找最小的两本书可以类似于合并果子，用优先队列做就好啦。预计得分：40-95(数据居然没有卡掉，还是那个-1的点卡常卡掉的23333).

解法5：
我们继续寻找规律，或者由合并果子的思路得来。这些附魔书合并前和合并后均有单调性，我们开两个队列就可以O(n)做。预计得分100.

解法6： 由于是两本合成一本附魔书，所以最坏情况下，附魔书的最大等级为a[i]+log_2N，我们就可以用递归来求解。开始只要桶排求出每种附魔书有多少本就可以了。递归有点小小的难打。预计得分100.

在这里附上50分代码和100分代码：

50pts:

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int cost,lev,lei;
    friend bool operator < (Node x,Node y){
        if(x.lev==y.lev){
            if(x.cost==y.cost)  return x.lei>y.lei;
            return x.cost>y.cost;
        }
        return x.lev>y.lev;
    }
}x;
priority_queue <Node> q; 
int ans=0,cnt=214748347;
int ex_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int e=ex_gcd(b,a%b,y,x);
    y-=x*(a/b);
    return e;
}
int main(){
    int n,qwq,orz;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&x.lev),x.lei=1,x.cost=0,q.push(x);
    Node fir;
    while(q.size()>1){
        if(q.top().lev>ans)  ans=q.top().lev,cnt=q.top().cost;
        else if(q.top().lev==ans)   cnt=min(cnt,q.top().cost);
        fir=q.top();    q.pop();
        while(q.top().lev!=fir.lev) fir=q.top(),q.pop();
        Node nxt,sec=q.top();
        nxt.cost=fir.cost+sec.cost+fir.lei+sec.lei;
        nxt.lei=max(fir.lei,sec.lei)*2+1;
        nxt.lev=fir.lev+1;
        q.pop(); q.push(nxt); 
    }
    if(q.top().lev>ans)  ans=q.top().lev,cnt=q.top().cost;
    if(ex_gcd(ans,cnt,qwq,orz)!=1)  cout<<-1<<endl;
    else{
        qwq=(qwq%cnt+cnt)%cnt;
        cout<<qwq<<endl;
    }
    return 0;
}

100pts:

#include<queue>
#include<cstdio>
#include<iostream>
#define int long long
#define MAXN 10000200
using namespace std;
int c[MAXN+50],d[MAXN+50],cnt,ans;
int ex_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int e=ex_gcd(b,a%b,y,x);
    y-=x*(a/b);
    return e;
}
int dg(int x){//获得一本等级为x的书的花费 
    if(d[x]){
        d[x]--;
        return 1;
    }   
    int p=dg(x-1),q=dg(x-1);
    ans+=p+q;
    return (max(p,q)*2+1) ;
}
inline void read(int &x){
    char ch;x=0;
    while(!isdigit(x))  ch=getchar();
    while(isdigit(x))   x=x*10+ch-'0',ch=getchar();
}
signed main(){
//  freopen("exp.in","r",stdin);
//  freopen("exp.out","w",stdout);
    int n,x,y;
    cin>>n;//cout<<"qwq"<<endl;
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        d[x]++;c[x]++;
    }//cout<<"qwq"<<endl;
    for(int i=1;i<=MAXN;i++){
        c[i+1]+=c[i]/2;      c[i]%=2;
        if(c[i+1])  cnt=max(cnt,i+1);
    } //cout<<"qwq"<<endl;
    dg(cnt);
    if(ex_gcd(cnt,ans,x,y)!=1)  cout<<-1<<endl;
    else{
        x=(x%ans+ans)%ans;
        printf("%lld\n",x);
    }  
 //   cout<<ans<<" "<<cnt<<endl;
    return 0;
}