题解：CF1415F Cakes for Clones

Collapsarr · 2026-11-11 16:39:54 · 题解

抛弃官解的做法，考虑带上值域暴力 dp，对 t_i 升序考虑，令 f_{i,j,k} 表示在第 i 轮时，人物在 j 处，分身在 k 处是否能收集到前 i 位置的全部蛋糕，转移是简易的，时间复杂度是 O(nV^2)。

发现对于一个轮次 i，对于一个限制 x_i，一定存在有 j=x_i 或 k=x_i，则考虑处理出来当人物在 x_i 处时分身可以合法在的位置，以及分身在 x_i 处时人物可以在的合法位置，不妨分别令其集合为 A,B，则单次转移时枚举 A_i,B_i 中的元素，贡献给 A_{i+1},B_{i+1}，对于一个原本在 A,B 中的合法位置，向新集合中贡献的位置一定是一个区间，两个限制的情况同理，不再另外考虑。按照合法位置递增处理后可以做到 O(V) 的转移，时间复杂度 O(nV)。

考虑集合 A,B 本身的性质，不妨令 A_0=B_0={0}，则有 |A_i|,|B_i|\le 2，考虑证明一下：

不妨令在 i,i+1 时 x 的限制均只有一个，两个的情况是简易的，将区间改成单点即可，以下令 d=t_{i+1}-t_i。

考虑对于 A_{i+1} 的所有贡献：

1. 保留原有的旧分身：若 |x_{i+1}-x_i|\le d，则可以将 A_i 整体贡献给 A_{i+1}；若存在 a\in B 满足 |x_{i+1}-a|\le d，则可以贡献一个单点 x_i 给 A_{i+1}。
2. 新增现有的新分身：考虑所有的可能的在 i 时刻合法的人物位置集合 S，对于所有满足 p\in S, |x_{i+1}-p|\le d 的 p，其会对分身的可能位置贡献一个区间，且区间均包含位置 x_{i+1}，则总体也会构成一个区间 I。

故而所有可能对 A_{i+1} 贡献的只有 I,A_{i},{x_i}。若 A_{i} 不可以继承，则至多只有 I\bigcup \{x_i\} 的两个区间，若 A_{i} 可以继承，故而 x_i\in A_{i}，且 I 必定包含 [x_i,x_{i+1}]，则只有 I\bigcup A_{i} 的两个区间。

考虑对于 B_{i+1} 的所有贡献：

故而所有可能对 B_{i+1} 贡献的只有 B_i 的段数并上 [x_i-d,x_i+d]，若 B_i 中有两段，则一定可以从之前的 B_{j} 中找到一条从 x_j\to x_i 的路径，这个时候会将 x_i 加入到 B_{i} 中，则此时合并后 B_{i} 中仍然至多只会有两段且有一段包含 x_i，故而最终的 B_{i+1} 也至多只会有两段。

故而对于所有的 A_i,B_i，均至多只有两个区间，转移时分别考虑转移即可，时间复杂度 O(n)。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define int long long
#define double long double
#define uint unsigned int
#define intt __int128
#define pbds __gnu_pbds
#define endl '\n'

inline int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    while('0'>ch||ch>'9')
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x = (x<<3) + (x<<1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int inf = 1e18,N = 1e6 + 10;

int n;
pair<int,int> a[N];

struct node
{
    vector<array<int,2>> A;
    inline bool empty()
    {
        return A.empty();
    }
    inline int size()
    {
        return A.size();
    }
}A,B;

inline bool check(array<int,2> x,array<int,2> y)
{
    return (y[0]<=x[1]&&x[1]<=y[1]) || (x[0]<=y[1]&&y[1]<=x[1]);
}

inline void cap(array<int,2> &x,array<int,2> y)
{
    x[0] = max(x[0],y[0]),x[1] = min(x[1],y[1]);
}

inline void cup(array<int,2> &x,array<int,2> y)
{
    if(x[0]==-inf&&x[1]==inf)
    {
        x = y;
    }
    else
    {
        x[0] = min(x[0],y[0]),x[1] = max(x[1],y[1]);
    }
}

inline void CUP(node &A,int it)
{
    if(A.size()==0)
    {
        return ;
    }
    else if(A.size()==1)
    {
        auto [l,r] = A.A[0];
        if(l<=it&&it<=r)
        {
            A.A[0] = {it,it};
        }
        else
        {
            A.A.pop_back();
        }
    }
    else
    {
        auto [l,r] = A.A[0];
        if(l<=it&&it<=r)
        {
            A.A[0] = {it,it},A.A.pop_back();
        }
        else
        {
            swap(A.A[0],A.A[1]),A.A.pop_back();
            auto [L,R] = A.A[0];
            if(L<=it&&it<=R)
            {
                A.A[0] = {it,it};
            }
            else
            {
                A.A.pop_back();
            }
        }
    }
}

inline void DP(int lst,int d,vector<int> tmp)
{
    int now = tmp.front(),len = max(lst,now) - min(lst,now);
    node a,b;array<int,2> I = {-inf,inf};bool falg = 0;
    if(!A.empty()&&abs(lst-now)<=d)
    {
        I = {min(lst,now)-(d-len)/2,max(lst,now)+(d-len)/2};
    }
    for(auto x : B.A)
    {
        array<int,2> y = {now-d,now+d};
        if(check(x,y))
        {
            cap(x,y),cup(I,{(x[0]+now-d+1)>>1,(x[1]+now+d)>>1});
        }
        auto [l,r] = x;falg |= (l<=now&&now<=r) || (min(abs(now-l),abs(now-r))<=d);
    }
    if(!A.empty()&&abs(now-lst)<=d)
    {
        a = A;
        if(a.size()==1)
        {
            if(check(a.A[0],I))
            {
                cup(a.A[0],I);
            }
            else
            {
                a.A.push_back(I);
            }
        }
        else
        {
            if(check(a.A[0],I)&&check(a.A[1],I))
            {
                cup(I,a.A[0]),cup(I,a.A[1]);
                a.A.clear(),a.A.push_back(I);
            }
            else if(check(a.A[0],I))
            {
                cup(a.A[0],I);
            }
            else
            {
                cup(a.A[1],I);
            }
        }
    }
    else
    {
        if(falg)
        {
            if(check(I,{lst,lst}))
            {
                cup(I,{lst,lst});
                a.A.push_back(I);
            }
            else
            {
                a.A.push_back(I),a.A.push_back({lst,lst});
            }
        }
    }
    if(lst==now)
    {
        b = B;
        bool falg = 0;
        for(auto &[l,r] : b.A)
        {
            falg |= (l<=now&&now<=r);
            l -= d,r += d;
        }
        if(!A.empty()&&!falg)
        {
            b.A.push_back({now-d,now+d});
        }
        if(b.size()==2&&check(b.A[0],b.A[1]))
        {
            cup(b.A[0],b.A[1]),b.A.pop_back();
        }
    }
    else
    {
        bool falg = 0;
        for(auto [l,r] : A.A)
        {
            falg |= l <= now && now <= r;
        }
        if(falg)
        {
            b.A.push_back({lst-d,lst+d});
        }
        array<int,2> I = {-inf,inf};
        if(abs(now-lst)<=d&&!A.empty())
        {
            I = {now-d+abs(now-lst),now+d-abs(now-lst)};
        }
        for(auto x : B.A)
        {
            array<int,2> y = {now-d,now+d};
            if(check(x,y))
            {
                cap(x,y);auto [l,r] = x;
                cup(I,{now-d+max({l-now,now-r,0ll}),now+d-max({l-now,now-r,0ll})});
            }
        }
        if(I[0]!=-inf&&I[1]!=inf)
        {
            if(!b.empty()&&check(b.A[0],I))
            {
                cup(b.A[0],I);
            }
            else
            {
                b.A.push_back(I);
            }
        }
    }
    swap(a,A),swap(b,B);
    if(tmp.size()==2)
    {
        CUP(A,tmp.back()),CUP(B,tmp.back());
    }
}

signed main()
{
    cerr<<fixed<<setprecision(6);
    auto START = chrono::high_resolution_clock::now();
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    n = read();
    for(int i = 1;i<=n;i++)
    {
        a[i] = {read(),read()};
    }
    A.A.push_back({0,0}),B.A.push_back({0,0});
    for(int i = 1,j,lst = 0;i<=n;)
    {
        j = i;vector<int> tmp;pbds::gp_hash_table<int,int> mp;
        while(j<=n&&a[i].first==a[j].first)
        {
            mp[a[j++].second] = 1;
        }
        for(auto [x,y] : mp)
        {
            tmp.push_back(x);
        }
        int d = a[i].first - a[i-1].first;i = j;
        if(tmp.size()>2)
        {
            cout<<"NO"<<endl;
            return 0;
        }
        DP(lst,d,tmp),lst = tmp.front();
    }
    cout<<(A.empty()&&B.empty()?"NO":"YES")<<endl;
    auto END = chrono::high_resolution_clock::now();
    chrono::duration<double> ELAPSED = END - START;
    cerr<<"Use Time: "<<ELAPSED.count()<<" seconds."<<endl;
    return 0;
}