题解：P5940 [POI1997] 跳

· · 题解

题目传送门：P5940 [POI1997] 跳

分析题意

不难发现这道题是没有 SPJ 的，意思是这个有唯一解？对这两个操作重新理解：操作一的意思是将一个 1 拆成 2 个 1，操作二的意思是将两个 1 合成 1 个 2。也就是说可以把前两个相邻的数合成为一个。这个合并是不是有点斐波那契的意思了。

不妨假设，第 i 个位置是第 i 个斐波那契数。此时就有性质，斐波那契数的和是不变的。因为 f_{i-2} 和 f_{i-1}“消失”可以换为一个 f_i，所以每次操作后的和是不变的。（消失的对象是将每个位置对印的斐波那契数）。

举个例子：

位置：    1 2 3 4 5
斐波那契：1 1 2 3 5
棋子个数：5 9 2 4 0 对应位置和：5 * 1 + 9 * 1 + 2 * 2 + 3 * 4 + 5 * 0 = 30

经过一次操作（i = 3 操作二）

位置：    1 2 3 4 5
斐波那契：1 1 2 3 5
棋子个数：5 9 1 3 1 对应位置和：5 * 1 + 9 * 1 + 1 * 2 + 3 * 3 + 1 * 5 = 30

再经过一次操作（i = 3 操作一）

位置：    1 2  3 4 5
斐波那契：1 1  2 3 5
棋子个数：6 10 2 3 1 对应位置和：6 * 1 + 10 * 1 + 2 * 2 + 3 * 3 + 1 * 5 = 30

这里只是给出例子证明，没有严格证明，但是因该很好想。

最后，我们只需要构造一个不相邻的数列满足对应的斐波那契额数和跟原数列相等即可。Zeckendor 定理说明分解唯一，即大到小，能放就放。

代码实现

斐波那契增长速度非常快，所以需要高精度；因为位置有负数，所以需要偏移一个数，因为斐波那契增长速度非常快，所以这个偏移量不用很大。

// __JCY__ | 20241210

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e6 + 520, D = 1314; // D 是偏移量

//高精度
class Bigint{public:Bigint(long long=0);Bigint(const string&);Bigint(const char*str){*this=string(str);}Bigint&operator=(long long num){return*this=Bigint(num);}Bigint&operator=(const string&str){return*this=Bigint(str);}Bigint&operator=(const char*str){return*this=Bigint(str);}bool operator<(const Bigint&obj)const{return cmp(obj)<0;}bool operator>(const Bigint&obj)const{return cmp(obj)>0;}bool operator<=(const Bigint&obj)const{return cmp(obj)<=0;}bool operator>=(const Bigint&obj)const{return cmp(obj)>=0;}bool operator==(const Bigint&obj)const{return cmp(obj)==0;}bool operator!=(const Bigint&obj)const{return cmp(obj)!=0;}Bigint operator+()const{return*this;}Bigint operator-()const{return Bigint(-sign_,val_);}Bigint operator+(const Bigint&)const;Bigint operator-(const Bigint&)const;Bigint operator*(const Bigint&)const;Bigint operator/(const Bigint&)const;Bigint operator%(const Bigint&)const;Bigint&operator+=(const Bigint&obj){return*this=*this+obj;}Bigint&operator-=(const Bigint&obj){return*this=*this-obj;}Bigint&operator*=(const Bigint&obj){return*this=*this*obj;}Bigint&operator/=(const Bigint&obj){return*this=*this/obj;}Bigint&operator%=(const Bigint&obj){return*this=*this%obj;}Bigint&operator++(){return*this+=1;}Bigint&operator--(){return*this-=1;}Bigint operator++(int);Bigint operator--(int);friend istream&operator>>(istream&,Bigint&);friend ostream&operator<<(ostream&,const Bigint&);protected:enum div_type{division,remainder};enum cmp_type{with_sign,without_sign};static const int base_=(int)1e4;static const int width_=4;Bigint(int s,const vector<int>&v):sign_(s),val_(v){}int cmp(const Bigint&,cmp_type=with_sign)const;Bigint&delZero();Bigint&add(const Bigint&);Bigint&sub(const Bigint&);Bigint&mul(const Bigint&,const Bigint&);Bigint&div(Bigint&,Bigint,div_type=division);private:int sign_;vector<int>val_;};Bigint::Bigint(long long num):sign_(0){if(num<0)sign_=-1,num=-num;else if(num>0)sign_=1;do{val_.push_back(num%base_);num/=base_;}while(num);}Bigint::Bigint(const string&str){sign_=str[0]=='-'?-1:1;int be=str[0]=='-'?1:0,en=str.size();while((en-=width_)>=be){stringstream ss(str.substr(en,width_));int temp;ss>>temp;val_.push_back(temp);}if((en+=width_)>be){stringstream ss(str.substr(be,en-be));int temp;ss>>temp;val_.push_back(temp);}delZero();}Bigint Bigint::operator+(const Bigint&obj)const{if(sign_*obj.sign_==1){Bigint temp;return cmp(obj,without_sign)>=0?(temp=*this).add(obj):(temp=obj).add(*this);}else if(sign_*obj.sign_==-1)return*this- -obj;else return sign_==0?obj:*this;}Bigint Bigint::operator-(const Bigint&obj)const{if(sign_*obj.sign_==1){Bigint temp;return cmp(obj,without_sign)>=0?(temp=*this).sub(obj):(temp=-obj).sub(*this);}else if(sign_*obj.sign_==-1)return*this+-obj;else return sign_==0?-obj:*this;}inline Bigint Bigint::operator*(const Bigint&obj)const{Bigint temp;return(temp.sign_=sign_*obj.sign_)==0?temp:temp.mul(*this,obj);}inline Bigint Bigint::operator/(const Bigint&obj)const{Bigint temp,mod=*this;return cmp(obj,without_sign)<0||(temp.sign_=sign_*obj.sign_)==0?temp:temp.div(mod,obj);}inline Bigint Bigint::operator%(const Bigint&obj)const{Bigint temp,mod=*this;return cmp(obj,without_sign)<0||(temp.sign_=sign_)==0?mod:temp.div(mod,obj,remainder);}inline Bigint Bigint::operator++(int){Bigint temp=*this;++*this;return temp;}inline Bigint Bigint::operator--(int){Bigint temp=*this;--*this;return temp;}inline istream&operator>>(istream&in,Bigint&obj){string str;if(in>>str)obj=str;return in;}ostream&operator<<(ostream&out,const Bigint&obj){if(obj.sign_==-1)cout<<'-';out<<obj.val_.back();for(int i=obj.val_.size()-2;i>=0;i--)out<<setw(Bigint::width_)<<setfill('0')<<obj.val_[i];return out;}int Bigint::cmp(const Bigint&obj,cmp_type typ)const{if(typ==with_sign&&sign_!=obj.sign_)return sign_-obj.sign_;int sign=typ==with_sign?sign_:1;if(val_.size()!=obj.val_.size())return sign*(val_.size()-obj.val_.size());for(int i=val_.size()-1;i>=0;i--)if(val_[i]!=obj.val_[i])return sign*(val_[i]-obj.val_[i]);return 0;}inline Bigint&Bigint::delZero(){while(val_.back()==0&&val_.size()>1)val_.pop_back();if(val_.back()==0)sign_=0;return*this;}Bigint&Bigint::add(const Bigint&obj){int ts=val_.size(),os=obj.val_.size();for(int i=0;i<os;i++)val_[i]+=obj.val_[i];val_.push_back(0);for(int i=0;i<ts;i++)if(val_[i]>=base_)val_[i]-=base_,++val_[i+1];return delZero();}Bigint&Bigint::sub(const Bigint&obj){int pos=obj.val_.size();for(int i=0;i<pos;i++)if((val_[i]-=obj.val_[i])<0)val_[i]+=base_,--val_[i+1];while(val_[pos]<0)val_[pos]+=base_,--val_[++pos];return delZero();}Bigint&Bigint::mul(const Bigint&a,const Bigint&b){int as=a.val_.size(),bs=b.val_.size();val_.resize(as+bs);for(int i=0;i<as;i++)for(int j=0;j<bs;j++){int x=i+j;val_[x]+=a.val_[i]*b.val_[j];val_[x+1]+=val_[x]/base_;val_[x]%=base_;}return delZero();}Bigint&Bigint::div(Bigint&a,Bigint b,div_type typ){int move=a.val_.size()-b.val_.size();val_.resize(move+1);b.val_.insert(b.val_.begin(),move,0);for(int i=move;i>=0;i--){int left=0,right=base_;while(left+1<right){int mid=(left+right)>>1;if(a.cmp(b*Bigint(mid),without_sign)>=0)left=mid;else right=mid;}val_[i]=left;a.sub(b*Bigint(left));b.val_.erase(b.val_.begin());}return typ==division?delZero():a;}

int a[kMaxN], sum[kMaxN], n, cnt = 1;
Bigint f1 = 1, f2 = 1, ret;
vector<int> ans;

int main() {
    cin >> n;
    for (int i = 1, x; i <= n; i++) {
        cin >> a[i] >> x, a[i] += D, sum[a[i]] += x, cnt = max(cnt, a[i]);
    }
    sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) - (a + 1); //排序
    for (int i = 0; i <= a[n]; i++) {
        if (sum[i]) { //计算当前位置的斐波那契额和
            ret += (f2 * sum[i]);
        }
        swap(f1, f2), f2 = f1 + f2;
    }
    for (; f1 < ret; swap(f1, f2), f2 = f1 + f2, cnt++);
    for (; ~cnt; cnt--) { //贪心放
        if (ret >= f2) {
            ret = ret - f2, ans.push_back(cnt);
        }
        swap(f1, f2), f1 = f1 - f2;
    }
    sort(ans.begin(), ans.end());
    for (auto v : ans) {
        cout << v - D + 1 << ' ';
    }
    return 0;
}