题解归档 - cf104114G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114G
• 本地来源：problems/cf104114G/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/G
• 原始标题：cf104114G - Gears

思路

cf104114G - Gears

Let d[i]=x[i+1]-x[i]. A valid assignment satisfies

s[i] + s[i+1] = d[i].

Choose a=s[1]. Then every radius is forced and has the form

s[i] = (+/-) a + b[i],

where signs alternate and b[1]=0, b[i+1]=d[i]-b[i].

Now find a from the multiset of radii:

• if n is odd, the signs have one extra +, so sum(s) determines a;
• if n is even, use sum(s^2), giving a quadratic equation with at most two integer candidates.

For each candidate, build the sequence and verify its sorted multiset equals the input radii.

Complexity: O(n log n).

代码

来源：problems/cf104114G/solution.cpp

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128_t;

ll isqrt128(i128 x){
    if(x<0) return -1;
    long double d=sqrt((long double)x);
    ll r=(ll)d;
    while((i128)(r+1)*(r+1)<=x) r++;
    while((i128)r*r>x) r--;
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<ll>x(n),r(n);
    for(ll &v:x) cin>>v;
    for(ll &v:r) cin>>v;

    vector<ll>b(n,0);
    for(int i=0;i+1<n;i++){
        ll d=x[i+1]-x[i];
        b[i+1]=d-b[i];
    }

    vector<ll> sr=r;
    sort(sr.begin(),sr.end());

    auto build=[&](ll a)->vector<ll>{
        vector<ll>s(n);
        for(int i=0;i<n;i++){
            s[i]=(i%2==0)?a+b[i]:b[i]-a;
        }
        return s;
    };

    auto ok=[&](const vector<ll>&s)->bool{
        vector<ll> t=s;
        sort(t.begin(),t.end());
        return t==sr;
    };

    vector<ll> cand;
    i128 sumr=0,sumb=0,sumr2=0,sumb2=0,cross=0;
    for(ll v:r) sumr+=v,sumr2+=(i128)v*v;
    for(int i=0;i<n;i++){
        int sg=(i%2==0)?1:-1;
        sumb+=b[i];
        sumb2+=(i128)b[i]*b[i];
        cross+=(i128)sg*b[i];
    }

    if(n%2==1){
        i128 a=sumr-sumb;
        if(a>=1&&a<=(i128)4000000000000000000LL) cand.push_back((ll)a);
    }else{
        i128 delta=cross*cross-(i128)n*(sumb2-sumr2);
        ll sq=isqrt128(delta);
        if(sq>=0&&(i128)sq*sq==delta){
            i128 a1=-cross+sq;
            i128 a2=-cross-sq;
            if(a1%n==0) cand.push_back((ll)(a1/n));
            if(a2%n==0) cand.push_back((ll)(a2/n));
        }
    }

    sort(cand.begin(),cand.end());
    cand.erase(unique(cand.begin(),cand.end()),cand.end());
    for(ll a:cand){
        vector<ll>s=build(a);
        if(ok(s)){
            for(int i=0;i<n;i++){
                if(i) cout<<" ";
                cout<<s[i];
            }
            cout<<"\n";
            return 0;
        }
    }
    return 0;
}