2026牛客暑期多校 7——Problem D. 天下第一武道会(要多手摸样例啊,然后猜测一些结论啊,想一想样例为什么做出这样的选择)(不想要卡死=尽量晚卡死啊 / 所谓的让区间最大,就是找到最大的右端点) · znzryb
## 题目大意
这是一份为您整理好的整洁、规范的中文题面,去除了杂乱的内容且未包含任何解题思路:
## 题目描述:天下一武道会 (Tenkaichi Budōkai)
**时间限制:** C/C++/Rust/Pascal 1秒,其他语言2秒
**空间限制:** C/C++/Rust/Pascal 1024 MB,其他语言2048 MB
**特殊判定 (Special Judge):** 是,64位整数输入输出格式:%lld
天下一武道会汇聚了来自世界各地的 $n$ 名武术家。武术家们的编号为 $1, 2, \ldots, n$。
在比赛开始前,两名官员分别提交了固定的优先级列表 $P$ 和 $Q$。每个列表都恰好包含每位武术家一次,尽管武术家在两个列表中的排列顺序可能不同。
初始时,列表为:
$$
P = (p_1, p_2, \ldots, p_n)
$$
$$
Q = (q_1, q_2, \ldots, q_n)
$$
其中这两个序列都是 $1, 2, \ldots, n$ 的排列。一旦提交,两个列表的顺序都不允许被重新排列。
比赛委员会使用以下规则来模拟比赛。只要至少还有两名武术家剩余,就可以进行一场比赛:
设 $u$ 和 $v$ 分别为当前列表 $P$ 和 $Q$ 中排在最前面的未被淘汰的武术家。
- 如果 $u = v$,说明两位官员提名了同一位武术家。由于武术家不能与自己对战,且任何一位官员都不能跳过他们列表中的第一位武术家,此时模拟过程将陷入**停滞状态**,无法继续进行后续比赛。
- 否则(即 $u \neq v$),$u$ 和 $v$ 将进行对决。在模拟中,可以从 $\{u, v\}$ 中任意选择一名武术家 $z$ 作为败者。武术家 $z$ 将被淘汰出局,他也会同时从 $P$ 和 $Q$ 两个列表中被移除。移除后,每个列表中剩余武术家的相对顺序保持不变。
经过恰好 $n-1$ 场成功的比赛后,最终将只剩下一名武术家。这名武术家将被宣布为天下一武道会的冠军。
现在,你支持武术家 $x$。请判断:是否存在一种合法的比赛胜负序列,使得整个模拟过程永远不会陷入停滞状态,并且武术家 $x$ 最终成为冠军?
如果存在这样的序列,请输出任意一个符合条件的被淘汰武术家序列。
## 输入格式
第一行包含两个整数 $n$ 和 $x$($2 \le n \le 2\times 10^5$,$1 \le x \le n$),分别表示武术家的数量和你希望成为冠军的武术家编号。
第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$。保证序列 $P$ 是 $1, 2, \ldots, n$ 的一个排列。
第三行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$。保证序列 $Q$ 是 $1, 2, \ldots, n$ 的一个排列。
## 输出格式
如果在不陷入停滞状态的前提下,无法使武术家 $x$ 成为冠军,请输出一行 `NO`。
否则,第一行输出 `YES`。
第二行输出 $n-1$ 个整数 $z_1, z_2, \ldots, z_{n-1}$,其中 $z_i$ 表示在第 $i$ 场比赛中被淘汰的武术家。
**注意:**
在进行第 $i$ 场比赛前,设 $u_i$ 和 $v_i$ 分别为 $P$ 和 $Q$ 中剩余排在最前面的武术家。你的输出必须满足 $u_i \neq v_i$ 且 $z_i \in \{u_i, v_i\}$。在执行完全部的 $n-1$ 场淘汰操作后,剩余的唯一武术家必须是 $x$。
如果存在多个符合条件的淘汰序列,输出其中任意一个均视为正确。
## 样例
### 样例 1
**输入:**
Plaintext
```
3 3
2 3 1
3 1 2
```
**输出:**
Plaintext
```
NO
```
### 样例 2
**输入:**
Plaintext
```
3 1
2 1 3
3 2 1
```
**输出:**
Plaintext
```
YES
2 3
```
### 样例 3
**输入:**
Plaintext
```
5 1
2 4 3 1 5
4 3 5 2 1
```
**输出:**
Plaintext
```
YES
4 3 2 5
```
## 样例解释
下面是对 **样例 3** 输出的详细解释:
初始时,$P$ 和 $Q$ 中剩余排在最前面的武术家分别是 2 和 4。他们进行对决,武术家 4 被淘汰。列表更新为:
$$
P = (2, 3, 1, 5)
$$
$$
Q = (3, 5, 2, 1)
$$
下一场比赛在武术家 2 和 3 之间进行。武术家 3 被淘汰,列表更新为:
$$
P = (2, 1, 5)
$$
接下来,被提名的武术家是 2 和 5。武术家 2 被淘汰,此时:
$$
P = (1, 5)
$$
$$
Q = (5, 1)
$$
最后,武术家 1 和 5 面对面进行对决,武术家 5 被淘汰。两个列表现在都只剩下武术家 1。
因此,模拟过程从未陷入停滞,武术家 1 成功成为了天下一武道会的冠军。
## 思路讲解
**不想要卡死=尽量晚卡死啊**


那么维护这样子的一个距离啊,可以使用这个 pbds。
```cpp
int choose_p_or_q() {
if (aliveP.empty() || aliveQ.empty()) {
return -1;
}
auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
ll pval = P[pid];
ll qval = Q[qid];
if (pval == qval) {
return -1;
}
ll disp = aliveQ.order_of_key(valToQPos[pval]);
ll disq = aliveP.order_of_key(valToPPos[qval]);
auto erase_q = [&]() {
++ans_idx;
Ans[ans_idx] = Q[qid];
aliveQ.erase(qid);
aliveP.erase(valToPPos[qval]);
};
auto erase_p = [&]() {
++ans_idx;
Ans[ans_idx] = P[pid];
aliveP.erase(pid);
aliveQ.erase(valToQPos[pval]);
};
if (pval == X) {
erase_q();
} else if (qval == X) {
erase_p();
} else if (disp >= disq) {
erase_q();
} else {
erase_p();
}
return 0;
}
```
不断反复调用 `choose_p_or_q()`,即可啊。
```cpp
while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
int res = choose_p_or_q();
if (res == -1) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
for (int i = 1; i <= ans_idx; ++i) {
cout << Ans[i] << " ";
}
```
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: Tenkaichi Budōkai
* Contest:
* Judge: NowCoder
* URL: https://ac.nowcoder.com/acm/contest/133882/D
* Created: 2026-08-08 01:42:06
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* 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 fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
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;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);
ll lT, testcase;
/*
*
*/
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag,
tree_order_statistics_node_update>;
ll N, X;
int P[MAXN], Q[MAXN], valToQPos[MAXN], valToPPos[MAXN];
ll ans_idx = 0;
ll Ans[MAXN];
ordered_set<ll> aliveP;
ordered_set<ll> aliveQ;
void init() {
ans_idx = 0;
aliveP.clear();
aliveQ.clear();
}
int choose_p_or_q() {
if (aliveP.empty() || aliveQ.empty()) {
#ifdef LOCAL
cerr << "aliveP:" << SZ(aliveP) << " aliveQ:" << SZ(aliveQ) << "\n";
#endif
return -1;
}
auto [pid,qid] = make_tuple(*aliveP.begin(), *aliveQ.begin());
ll pval = P[pid];
ll qval = Q[qid];
if (pval == qval) {
return -1;
}
ll disp = aliveQ.order_of_key(valToQPos[pval]);
ll disq = aliveP.order_of_key(valToPPos[qval]);
auto erase_q = [&]() {
++ans_idx;
Ans[ans_idx] = Q[qid];
aliveQ.erase(qid);
aliveP.erase(valToPPos[qval]);
};
auto erase_p = [&]() {
++ans_idx;
Ans[ans_idx] = P[pid];
aliveP.erase(pid);
aliveQ.erase(valToQPos[pval]);
};
if (pval == X) {
erase_q();
} else if (qval == X) {
erase_p();
} else if (disp >= disq) {
erase_q();
} else {
erase_p();
}
return 0;
}
void Solve() {
cin >> N >> X;
init();
for (int i = 1; i <= N; ++i) {
cin >> P[i];
valToPPos[P[i]] = i;
aliveP.insert(i);
}
for (int i = 1; i <= N; ++i) {
cin >> Q[i];
valToQPos[Q[i]] = i;
aliveQ.insert(i);
// valToQPos.set(Q[i],i);
}
while (SZ(aliveP) >= 2 || SZ(aliveQ) >= 2) {
int res = choose_p_or_q();
if (res == -1) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
for (int i = 1; i <= ans_idx; ++i) {
cout << Ans[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://ac.nowcoder.com/acm/contest/view-submission?submissionId=84410045
*/
```
:::
## 心路历程(WA,TLE,MLE……)