The 2025 ICPC 德国 German Collegiate Programming Contest——K. Karlsruhe Skyline

题目大意

题目描述
你需要构造一个包含整数 $1$ 到 $n$ 的排列（即长度为 $n$ 的序列，其中 $1 \sim n$ 每个数字出现且仅出现一次）。
在这个序列中，我们将数字视为楼房的高度。定义“可见性”规则如下：

• 从某一侧观察，如果一个数字严格大于它和观察点之间的所有数字，则该数字是可见的（即较高的楼会挡住后面较矮的楼）。

请构造一个排列，同时满足以下两个条件：

1. 从左向右看，恰好有 $a$ 个数字是可见的。

2. 从右向左看，恰好有 $b$ 个数字是可见的。

输入格式
输入包含一行三个整数 $n, a, b$。
数据范围：$2 \le n \le 1000$，$1 \le a, b \le n$。

输出格式

• 如果存在满足条件的排列，首先输出一行 yes，随后输出 $n$ 个整数，表示构造出的排列。如果有多个解，输出任意一个即可。

• 如果不存在满足条件的排列，输出 no。

样例解释

样例 1
输入：5 2 2
输出：yes 1 5 2 3 4
解释：

• 左侧视角：看到 1，接着看到 5（5 > 1）。后面的 2, 3, 4 都比 5 小，被 5 挡住。共看见 2 个，满足 $a=2$。

• 右侧视角：看到 4，3 和 2 被 4 挡住。接着看到 5（5 > 4）。1 被 5 挡住。共看见 2 个（4 和 5），满足 $b=2$。

样例 2
输入：5 3 4
输出：no
解释：在 $n=5$ 的情况下，无法构造出左看 3 个、右看 4 个的排列。

样例 4
输入：4 1 4
输出：yes 4 3 2 1
解释：

• 左侧视角：第一个是 4（最大值），挡住了后面所有的数。共看见 1 个，满足 $a=1$。

• 右侧视角：从右往左依次是 1, 2, 3, 4，每一个都比右边的前序数字大。共看见 4 个，满足 $b=4$。

思路讲解

这个这道题目还是很简单的。这个无解的情况已经高亮出来了。A 等于等于一，B 等于等于一，肯定是不可能的。因为你一定能够看到一个次高的和一个最高的。所以说你你是不可能你是不可能就是只看到一个建筑的。那么 A 加 B 大于 N 加一的话也是不可能的。因为两边看，从一边看过去，再从另外一边看过去的总和加在一起，不可能超过 N 加一。因为一定有一个最高的建筑会把你给挡住的。所以两边的总和其实就是两边，这边就是，两边它加起来最大就是 N 加一。

后面构造也是比较简单，反正就是要注意这个顺序的，就是要注意一下顺序，就是要注意一下顺序。然后还有最高的建筑一定能被看到这个限制。就是记住这个，然后你用一个 DQ 去构造会简单一点。

void Solve() {
    ll N,a,b;
    cin >> N >> a >> b;
    //  无解的情况
    if (a==1 && b==1) {
        cout<<"no\n";
        return;
    }
    if (a+b>N+1) {
        cout<<"no\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    deque<ll> q;
    for (int i=1;i<=N-2;++i) {
        q.push_back(i);
    }
    if (a==1) {
        ans_ls[1]=N;
        for (ll i=N;i>=2;--i) {
            if (i==N-b+2) {
                ans_ls[i]=N-1;
            }else {
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else if (b==1){
        // ll cnt=0;
        ans_ls[N]=N;
        for (int i=1;i<=N-1;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else {
                // ++cnt;
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else {
        ll cnt=0;
        for (int i=1;i<=N;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else if (i==N-b+1) {
                ans_ls[i]=N;
            }else if (i<a-1){
                ans_ls[i]=q.front();
                q.pop_front();
            }else {
                ans_ls[i]=q.back();
                q.pop_back();
            }
        }
    }
    cout<<"yes\n";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2026555

源代码

/**
 * Problem: Karlsruhe Skyline
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-14570
 * Created: 2026-02-11 13:14:57
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,a,b;
    cin >> N >> a >> b;
    if (a==1 && b==1) {
        cout<<"no\n";
        return;
    }
    if (a+b>N+1) {
        cout<<"no\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    deque<ll> q;
    for (int i=1;i<=N-2;++i) {
        q.push_back(i);
    }
    if (a==1) {
        ans_ls[1]=N;
        for (ll i=N;i>=2;--i) {
            if (i==N-b+2) {
                ans_ls[i]=N-1;
            }else {
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else if (b==1){
        // ll cnt=0;
        ans_ls[N]=N;
        for (int i=1;i<=N-1;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else {
                // ++cnt;
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else {
        ll cnt=0;
        for (int i=1;i<=N;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else if (i==N-b+1) {
                ans_ls[i]=N;
            }else if (i<a-1){
                ans_ls[i]=q.front();
                q.pop_front();
            }else {
                ans_ls[i]=q.back();
                q.pop_back();
            }
        }
    }
    cout<<"yes\n";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2026555

WA
https://qoj.ac/submission/2026545

*/

心路历程（WA，TLE，MLE……）