题目概述

AtCoder Regular Contest 104C

解题报告

我英语太渣题目读错了😭，以为只要存在某两个人满足 $C_i=C_j$ 就行了，实际上应该是只要出现两个人在电梯上，就必须有 $C_i=C_j$ 。

很明显，如果一个人是 $i\to i+k$ ，那么 $\forall x\in[i,i+k-1]$ ，都有 $x\to x+k$ 。

所以 $2n$ 个楼层可以分成若干段，因此考虑DP：$f_i$ 表示以 $i$ 楼结尾，前 $i$ 楼是否都能满足。

只要存在 $f_{i-2k}$ 为真，且 $\forall x\in [i-2k+1,i-k]$ ，$x\to x+k$ 不违法，那么 $f_i$ 就为真。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100,maxm=200;

int n,m,a[maxn+5],b[maxn+5],ID[maxm+5];bool f[maxm+5];

bool check(int L,int R){
    int k=R-L+1>>1;
    for (int i=L,j=i+k;j<=R;i++,j++){
        if (ID[i] && ID[j] && ID[i]!=ID[j]) return false;
        if (ID[i] && b[ID[i]]==i) return false;
        if (ID[j] && a[ID[j]]==j) return false;
    }
    return true;
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for (int i=1;i<=n;i++) if (~a[i]) {if (ID[a[i]]) goto GG;ID[a[i]]=i;}
    for (int i=1;i<=n;i++) if (~b[i]) {if (ID[b[i]]) goto GG;ID[b[i]]=i;}
    m=n<<1;f[0]=true;f[1]=false;
    for (int i=2;i<=m;i++)
        for (int j=i-2;j>=0;j-=2)
            if (f[j] && check(j+1,i)) {f[i]=true;break;}
    if (!f[m]) goto GG;
    puts("Yes");return 0;GG:puts("No");return 0;
}