1

极寒神冰 · 2022-01-01 17:24:43 · 题解

一个想法，不知道对不对，就是这个翻译有些细小的偏差

令每张照片的可以拍摄开区间为 Q_i=(a_i,b_i)，实际拍摄的开区间 P_i=(x_i,x_i+t)，需要有 P_i\subseteq Q_i，且 P_i 两两不交。

首先可以想到各种一眼就是错的贪心。

假设现在有 t=3,Q_1=(0,7),Q_2=(1,4)。

然后现在从左往右扫，考虑怎么求出 P_1。

假如直接贪心把 (0,3) 填上，那么此时 (1,3) 就被覆盖，P_2 无解。

因此，由于问题也只是求是否有解且 t 固定，Q_2 成立也就当且仅当不存在一个 P_i 的左端点在 (-2,1) 中。称这个为 Q_2 禁止区间。

一般化的，对于一个指标集 S=\{i_1,i_2,\cdots,i_k\}，设一组合法的方案的区间簇为 \{P_{i_j}\},i\le j \le k。其左端点 \inf(\cup P_i)=N，左端点 \inf(\cup Q_i)=M。则 S 的禁止区间 F_S=(N-t,M)。

可以发现，如果存在一组合法方案 P，则所有区间的左端点 a_i=\inf P_i 不属于任意一个禁止区间。

然后继续考虑贪心：记所有禁止区间的并集为 F_x，从左往右扫，扫的时候跳过 F_x 中的所有点。如果找到某个 a\ge\inf Q_i，找到未匹配区间中 \sup Q_i 最小的。然后 P_i=(a,a+t)，然后继续从 a+t 开始扫。这样一定可以构造出一组合法的解。

证明可以考虑归纳。。

但是这样子禁止区间高达 2^n 种，考虑减少所需要的禁止区间数量。

令 S=\{i_1,i_2,\cdots,i_k\}，\inf(\cup Q_i)=L,\sup (\cup Q_i)=R。

如果存在 x\not\in S 满足 \inf Q_x\ge L。将 x 加入 S 后，由于需要的区间多了一个 P_x\subseteq (L,+\infty)，所以 \inf ((\cup P_i)\cup P_x)\le \inf(\cup P_i)=N，F_S\subseteq F_{S\cup \{x\}}。

所以事实上 F_S 对禁止区间的并集没有任何贡献，所需要考虑的禁止区间只有 \mathcal O(n) 个：即对于每一个 a_i，所有左端点 \ge a_i 的区间构成的集合的禁止区间。（下面的 F_i 表示用上面这句定义的禁止区间）。

考虑按照左端点排序，假设 a_i<a_{i+1}。

依次对 i=n,n-1,\cdots,2,1 计算 F。

根据前面从左往右的贪心，此时从右往左同样也是对的，答案就是最大的左端点 N。

但是这样会出现当前位置不在禁止区间内，但是也没有区间可以匹配。此时可以将这整个问题分成两个更小的子问题，如果出现不可分割的子问题，可以发现一定不存在这种情况。

因此考虑对每一对 (i,R) 维护出只考虑左端点 \ge a_i，右端点 \le R 的区间，只考虑不经过禁止区间，不考虑是否有区间匹配，匹配完之后终点数量。

因此

然后考虑从 (i+1,R) 转移到 (i,R)，因为 F_i 的右端点 a_i 随着 i 递减而递减，因此可以通过双指针跳过禁止区间。

具体，先令 dp_{i,R}=dp_{i+1,R-t}，然后由于禁止区间控制的是左端点，因此依次用双指针检验每个 i，若当前 x<a_i，则对 \inf F_i 取 \min 即可。

判断无解时，就是看 f_{i,R} 是否 \ge a_i。

时间复杂度 \mathcal O(n^2)

#include<bits/stdc++.h>
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
using namespace std;
int n,t;
pair<int,int>a[11111];
int rr[11111],to[11111],now[11111];
int dp[11111];
inline int ckmin(int &x,const int y)
{
    return x>y?x=y,1:0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>t;
    R(i,1,n)
    {
        cin>>a[i].first>>a[i].second;
        rr[i]=a[i].second;
    }
    R(i,1,n) now[i]=n;
    sort(a+1,a+n+1),sort(rr+1,rr+n+1);
    R(i,1,n) dp[i]=rr[i],to[i]=1<<30;
    L(i,1,n) 
    {
        int r=n;
        for(;rr[r]>=a[i].second;--r)
        {
            dp[r]-=t;
            for(;i<now[r]&&dp[r]<a[now[r]].first;--now[r]) ckmin(dp[r],to[now[r]]);
            if(dp[r]<a[i].first) return cout<<"no"<<endl,0;
            ckmin(to[i],dp[r]-t);
        }
    }
    cout<<"yes"<<endl;
}