题解：P17278 『__OI R1』Hikari

· · 题解

题意简述

序列满足 x_0=0，且每一项都有 |x_i|=|x_{i-1}+1|。给定若干项的值，求所有合法序列中 |\sum_{i=0}^n x_i| 的最小值；若不存在合法序列，输出 -1。

解题思路

把序列再向后扩展一个辅助点。对 0\le i\le n 定义 v_i=|x_i|，并令 v_{n+1}=|x_n+1|。根据原递推，若 x_i\ge0，下一高度为 v_i+1；若 x_i<0，下一高度为 v_i-1。因此：

\begin{aligned} v_0 & =0 \\ v_i & \ge0 \\ |v_{i+1}-v_i| & =1 \end{aligned}

也就是说，v 是从高度 0 出发的非负格路。反过来，任取这样的路径：若第 i 步上升，就令 x_i=v_i；若它下降，就令 x_i=-v_i。这会唯一还原满足原条件的 x_i。

限制 x_w=c 等价于同时固定两个点：

v_w=|c|,v_{w+1}=|c+1|

第一个点固定绝对值，第二个点固定离开该点时的方向。因此，这两个高度条件也足以推出 x_w=c。

两个已知点 (l,a) 与 (r,b) 之间存在合法路径，当且仅当：

|a-b|\le r-l,r-l-|a-b|\equiv0\pmod 2

必要性来自每步只能变化 1。对于充分性，先用单调路径消除高度差。剩余步数为非负偶数，可以反复插入一上一下；若当前位于高度 0，先向上即可，所以路径始终非负。

把初始条件转换为 (0,0) 与 (1,1)，再为每条限制加入上述两个点。按横坐标排序后，同一位置必须具有相同高度。不同位置之间只需检查相邻固定点，因为拼接各段可行路径即可得到整条路径。

可行性解决后，再化简目标。原条件两边平方可得：

x_i^2=x_{i-1}^2+2x_{i-1}+1

对 i=1\sim n 求和时，中间平方项全部抵消。再把 x_n 补入总和，得到：

\sum_{i=0}^n x_i=\frac{x_n^2+2x_n-n}{2} =\frac{(x_n+1)^2-(n+1)}{2} =\frac{v_{n+1}^2-(n+1)}{2}

所以目标只与格路终点高度 v_{n+1} 有关，需要让它的平方尽量接近 n+1。

设最后一个固定点为 (w,v)，还剩 d=n+1-w 步。每步改变一个单位。由两点可达条件，终点高度恰好遍历下列区间内的同奇偶整数：

\left[\max(0,v-d),v+d\right],v_{n+1}\equiv v+d\pmod 2

平方函数在非负数上递增。离 \sqrt{n+1} 越近，目标值越小。因此，只需检查两个区间端点，以及根号两侧最近的两个合法奇偶整数。

每组数据的时间复杂度为 O(m\log m)，空间复杂度为 O(m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
bool reach(pair<ll,ll> a,pair<ll,ll> b)
{
    ll d=b.first-a.first;
    ll h=abs(b.second-a.second);
    return h<=d&&(d-h)%2==0;
}
ll root(ll x)
{
    ll s=static_cast<ll>(sqrtl(static_cast<long double>(x)));
    while((s+1)*(s+1)<=x)s++;
    while(s*s>x)s--;
    return s;
}
ll cost(ll x,ll n)
{
    return abs(x*x-n-1);
}
void solve()
{
    ll n;
    int m;
    cin>>n>>m;
    vector<pair<ll,ll>> a={{0,0},{1,1}};
    for(int i=0;i<m;i++)
    {
        ll w,c;
        cin>>w>>c;
        a.push_back({w,abs(c)});
        a.push_back({w+1,abs(c+1)});
    }
    sort(a.begin(),a.end());
    bool ok=1;
    ll w=a[0].first,v=a[0].second;
    int tot=a.size();
    for(int i=1;i<tot;i++)
    {
        ll x=a[i].first,y=a[i].second;
        if(x==w)
        {
            if(y!=v)ok=0;
            continue;
        }
        if(!reach({w,v},a[i]))ok=0;
        w=x;
        v=y;
    }
    if(!ok)
    {
        cout<<-1<<'\n';
        return;
    }
    ll d=n+1-w,l=max(0LL,v-d),r=v+d;
    if(l%2!=(v+d)%2)l++;
    ll s=root(n+1);
    ll y=s;
    if(y%2!=l%2)y--;
    ll ans=min(cost(l,n),cost(r,n));
    if(l<=y&&y<=r)ans=min(ans,cost(y,n));
    y+=2;
    if(l<=y&&y<=r)ans=min(ans,cost(y,n));
    cout<<ans/2<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}