题解：P17001 [NWERC 2019] 晾画绳 / Canvas Line

LotleTos · 2026-08-07 15:30:12 · 题解

对于每个画布，计算他上面已经有的夹子数量。

如果初始已经有画布上有 2 个以上的夹子则输出无解。

然后贪心的夹夹子，优先夹在两个头尾相接的画布中间，这样可以同时夹到两个画布：枚举每个画布，检查他和下一个画布是否头尾相接且都未达到两个夹子的标准且中间没有夹子，成立就在中间夹一个。

检查完所有连接点后，再扫一遍，如果有画布还是没达到标准，那么随便找到里面一个没夹子的地方夹。

可以使用一个 set 集合维护已有的夹子位置，避免重复夹在同个地方。

#include<bits/stdc++.h>
using namespace std;
int l[1145],r[4514];
int s[1145];
set<int> b;
vector<int> ans;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        b.insert(x);
        for(int j=1;j<=n;j++){
            if(x>=l[j]&&x<=r[j]){
                s[j]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(s[i]>2){
            cout<<"impossible";
            return 0;
        }
    }
    for(int i=1;i<n;i++){
        if(r[i]==l[i+1]){
            if(s[i]<2&&s[i+1]<2){
                if(!b.count(r[i])){
                    ans.push_back(r[i]);
                    b.insert(r[i]);
                    s[i]++;
                    s[i+1]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=l[i];j<=r[i]&&s[i]<2;j++){
            if(i!=1&&j==r[i-1]){
                continue;
            }
            if(i!=n&&j==l[i+1]){
                continue;
            }
            if(!b.count(j)){
                b.insert(j);
                s[i]++;
                ans.push_back(j);
            }
        }
        if(s[i]!=2){
            cout<<"impossible";
            return 0;
        }
    }
    cout<<ans.size()<<endl;
    for(auto i:ans){
        cout<<i<<" ";
    }
}