[[构造]]

B. Siga ta Kymata

时间限制：每个测试 1.5 秒
内存限制：每个测试 256 MB

问题描述

给定一个从 $1$ 到 $n$ 的每个整数的排列 $p$ 。你还拥有一个大小为 $n$ 的二进制字符串 $s$ ，初始时对于所有 $1 \leq i \leq n$ 都有 $s_i = 0$ 。你最多可以进行 $5$ 次以下操作：

选择任意两个整数 $l$ 和 $r$ ，满足 $1 \leq l \leq r \leq n$ 。
然后，对于每个满足 $l < i < r$ 且 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 同时成立的 $i$ ，将 $s_i$ 设置为 $1$ 。

你还会得到一个二进制字符串 $x$ ，大小为 $n$ 。在执行操作后，对于每个 $1 \leq i \leq n$ ，如果 $x_i = 1$ ，则必须有 $s_i = 1$ 。注意如果 $x_i = 0$ ，则 $s_i$ 可以是任意值。

找出一个最多包含 $5$ 个操作的序列，使得上述条件得到满足，或者报告说不可能这样做。注意你不必最小化操作次数。

$*$ 从 $1$ 到 $n$ 的每个整数的排列 $p$ 是一个包含从 $1$ 到 $n$ 的元素的序列，其中每个元素恰好出现一次。

$†$ 当且仅当对于所有 $1 \leq i \leq m$ 都有 $b_i = 0$ 或 $b_i = 1$ 时，大小为 $m$ 的字符串 $b$ 被认为是二进制字符串。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \leq t \leq 10^4$ )。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ( $3 \leq n \leq 2 \cdot 10^5$ ) —— 数组的大小。

第二行包含恰好 $n$ 个整数 $p_1, p_2, \dots, p_n$ ( $1 \leq p_i \leq n$ ， $p$ 的元素两两不同) —— 表示排列的第 $i$ 个元素。

第三行包含一个大小为 $n$ 的二进制字符串 $x$ 。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，如果不可能执行操作以满足约束，则输出 $-1$ 。

否则，输出一个整数 $0 \leq k \leq 5$ ，表示操作的数量。在接下来的 $k$ 行中，第 $i$ 行输出两个整数 $1 \leq l_i \leq r_i \leq n$ ，表示第 $i$ 个操作的边界。如果有多个正确的解决方案，输出其中任何一个。

样例输入

6
3
1 2 3
010
5
3 4 2 1 5
11111
6
1 3 2 4 6 5
001100
6
6 2 3 4 5 1
110110
5
2 1 4 3 5
00000
5
2 5 3 1 4
00100

样例输出

样例说明

在第一个样例中， $p = [1, 2, 3]$ ， $x = 010$ 。我们可以执行一次操作， $l = 1$ 和 $r = 3$ 。操作后，我们将 $s_2$ 设置为 $1$ ，因为 $l < 2 < r$ 且 $\min(p_l, p_r) < p_2 = 2 < \max(p_l, p_r)$ 同时成立。结果， $s = 010$ 。

在第二个样例中，可以证明不存在最多 $5$ 个操作的正确序列，因此我们输出 $-1$ 。

在第三个样例中， $p = [1, 3, 2, 4, 6, 5]$ 且 $x = 001100$ 。执行 $l = 1$ 和 $r = 5$ 的操作后， $s = 011100$ 。如果我们再执行 $l = 2$ 和 $r = 6$ 的操作， $s$ 将保持不变。字符串 $s = 011100$ 是有效的，因为在 $x$ 为 $1$ 的每个位置上， $s$ 在该位置也是 $1$ 。

赛时WA2代码

// Problem: CF 2163 B
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;


void solve() {
    int n;
    cin>>n;

    vector<int> a(n+3,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    string s;
    cin>>s;
    vector<int> cnt(2,0);
    if(s[0]=='1'||s[n-1]=='1'){
        printf("-1\n");
        return ;
    }

    vector<int> pre(n+2,0),suf(n+2,0);
    for(int i=1;i<=n;i++){
        if(a[i]>a[pre[i-1]]){
            pre[i]=i;
        }else pre[i]=pre[i-1];
    }
    for(int i=n;i>0;i--){
        if(a[i]>a[suf[i+1]]){
            suf[i]=i;
        }else suf[i]=suf[i+1];
    }
    // for(int i=1;i<=n;i++) printf("%d ",pre[i]);
    // printf("\n");

    printf("5\n");
    printf("%d %d\n",1,pre[1]);
    printf("%d %d\n",1,pre[n]);
    printf("%d %d\n",suf[n],n);
    printf("%d %d\n",suf[1],n);
    printf("%d %d\n",pre[1],suf[n]);

    return;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

看哥哥AC代码

// Problem: CF 2163 B
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;


void solve() {
    int n;
    cin>>n;

    vector<int> a(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    string s;
    cin>>s;
   for(int i=0;i<n;i++){
        if(s[i]=='1'&&(i==0||i==n-1||a[i+1]==1||a[i+1]==n)){
            printf("-1\n");
            return ;
        }
   }

   int x=find(a.begin()+1,a.end(),1)-a.begin();
   int y=find(a.begin()+1,a.end(),n)-a.begin();
   if(x>y) swap(x,y);
   printf("5\n");
   printf("%d %d\n",x,y);
   printf("%d %d\n",1,x);
   printf("%d %d\n",1,y);
   printf("%d %d\n",x,n);
   printf("%d %d\n",y,n);
    return;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

jiangly 代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> p(n);
    for (int i = 0; i < n; i++) {
        std::cin >> p[i];
    }

    std::string x;
    std::cin >> x;

    for (int i = 0; i < n; i++) {
        if (x[i] == '1' && (i == 0 || i == n - 1 || p[i] == 1 || p[i] == n)) {
            std::cout << -1 << "\n";
            return;
        }
    }

    int a = std::find(p.begin(), p.end(), 1) - p.begin() + 1;
    int b = std::find(p.begin(), p.end(), n) - p.begin() + 1;

    if (a > b) {
        std::swap(a, b);
    }

    std::cout << 5 << "\n";
    std::cout << 1 << " " << a << "\n";
    std::cout << 1 << " " << b << "\n";
    std::cout << a << " " << b << "\n";
    std::cout << a << " " << n << "\n";
    std::cout << b << " " << n << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

AI 对于题目的分析

好的，我们来一起分析这道题。

这是一道很棒的构造题。它的时间限制是 1.5 秒，但 $n$ 的总和达到了 $2 \cdot 10^5$ ，这意味着我们的 solve() 函数需要是一个接近 $O(n)$ 的解法。

你拿到了 WA2，并且 jiangly 的代码 A 了，这是提升的绝佳机会！我们来一步步拆解 jiangly 的思路。

步骤 1：理解这个操作的“死穴”

我们先来仔细分析这个操作：

对于每个 $l < i < r$ 且 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ ，将 $s_i$ 设置为 $1$ 。

这里有两个_绝对_限制：

位置限制: $l < i < r$ 。
- 这意味着 $i$ 永远不可能等于 $l$ 或 $r$ 。
- 更重要的是， $i$ 永远不可能等于 $1$ （因为它不能 $< l$ ）或 $n$ （因为它不能 $> r$ ）吗？不，这个推论是错的。比如 $l=1, r=3$ ， $i=2$ 是可以的。
- 但是，如果我们选 $l=1$ ，那么 $i$ 必须 $\ge 2$ 。如果我们选 $r=n$ ，那么 $i$ 必须 $\le n-1$ 。
- 一个 $i$ 要被操作，它必须严格位于 $l$ 和 $r$ 之间。这意味着 $s_1$ 和 $s_n$ 永远无法被设为 $1$ ，因为 $i=1$ 无法满足 $l < 1$ ， $i=n$ 无法满足 $n < r$ 。
值限制: $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 。
- 这意味着 $p_i$ 的值必须严格位于 $p_l$ 和 $p_r$ 之间。
- $p_i$ 永远不可能等于 $\min(p_l, p_r)$ 或 $\max(p_l, p_r)$ 。
- 更重要的是， $p$ 是一个 $1$ 到 $n$ 的排列。如果 $p_i = 1$ ，它永远无法满足 $p_i > \min(p_l, p_r)$ 。
- 如果 $p_i = n$ ，它永远无法满足 $p_i < \max(p_l, p_r)$ 。

步骤 2：找到所有“不可能”的情况 ( `-1` )

根据上面的“死穴”，我们知道有些 $s_i$ 是永远无法被设为 $1$ 的。

因此，如果目标字符串 $x$ 要求我们在一个“不可能”的位置上设置 $1$ ，我们就必须输出 -1。

“不可能”的位置 $i$ 满足以下任意一个条件：

$i = 1$ (因为 $i$ 必须 $> l$ )
$i = n$ (因为 $i$ 必须 $< r$ )
$p_i = 1$ (因为 $p_i$ 必须 $>\min$ )
$p_i = n$ (因为 $p_i$ 必须 $<\max$ )

现在，我们来看 jiangly 的代码：

C++

    for (int i = 0; i < n; i++) { // 0-indexed
        if (x[i] == '1' && (i == 0 || i == n - 1 || p[i] == 1 || p[i] == n)) {
            std::cout << -1 << "\n";
            return;
        }
    }

这完美地对应了我们分析出的 4 个“不可能”的条件。

💡 为什么你的代码 WA2 了？

我们来看你的 -1 判断：

C++

    if(s[0]=='1'||s[n-1]=='1'){ // s 是 0-indexed 的 x
        printf("-1\n");
        return ;
    }

你只检查了条件 1 ( $i=1$ ) 和条件 2 ( $i=n$ )。

你遗漏了条件 3 ( $p_i = 1$ ) 和条件 4 ( $p_i = n$ )！

这就是你 WA2 的关键原因。你的代码没有判掉一种不可能的情况，而是进入了构造环节，但你构造的操作（基于前缀/后缀最大值）无法覆盖这种不可能的情况，导致最终 $s_i$ 仍然是 $0$ 而 $x_i$ 是 $1$ 。

步骤 3：构造一个“万能”解

"你最多可以进行 5 次以下操作"

"你不必最小化操作次数"

这是本题最强烈的提示。它暗示我们：不要去为 $x$ 里的每一个 $1$ 精确地构造操作，那太复杂了。我们应该找到一个固定的、数量很少（ $\le 5$ ）的操作组合，这个组合“火力强大”，足以覆盖所有“可能”被设为 $1$ 的位置。

如果 $x_i = 1$ ，我们必须让 $s_i = 1$ 。

如果 $x_i = 0$ ，我们不在乎 $s_i$ 是 $0$ 还是 $1$ 。

所以，我们的目标是：用 5 次操作，把所有“可能”的 $i$ （即那 4 个条件都不满足的 $i$ ）都设为 $1$ 。

怎么构造最“强”的操作？

位置上: $l=1, r=n$ 是最强的，它覆盖了 $i \in [2, n-1]$ 。
值上: 要让 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 尽量容易满足，我们应该让这个值的区间 $\max - \min$ 最大。
什么能让区间最大？当然是 $p_l = 1$ 和 $p_r = n$ 。

核心思路： 解决方案一定与值为 $1$ 的位置和值为 $n$ 的位置有关。

我们来看 jiangly 的构造：

他首先找到了 $1$ 和 $n$ 的位置（1-indexed）：

C++

int a = std::find(p.begin(), p.end(), 1) - p.begin() + 1;
int b = std::find(p.begin(), p.end(), n) - p.begin() + 1;

他确保 $a \le b$ ( $a$ 是 $1$ 的位置, $b$ 是 $n$ 的位置)。
然后他输出一个固定的“操作组合”，完全不看 $x$ 是什么：

C++
```
std::cout << 5 << "\n";
std::cout << 1 << " " << a << "\n";
std::cout << 1 << " " << b << "\n";
std::cout << a << " " << b << "\n";
std::cout << a << " " << n << "\n";
std::cout << b << " " << n << "\n";
```
(注意：如果 $a=1$ 或 $b=n$ ，有些操作 (l,r) 可能会有 $l=r$ 或 $l, r$ 靠得太近，导致 $l < i < r$ 无法满足，但这些操作是无害的。)

为什么这个“万能组合”有效？

这个组合是一个“火力网”。它试图覆盖所有 $i$ 可能在的区域：

$i$ 在 $a$ 和 $b$ 之间：cout << a << " " << b << "\n"; 这一对是“主力”，它使用了 $p_a=1$ 和 $p_b=n$ ，提供了 $1 < p_i < n$ 这个最强的范围。
$i$ 在 $1$ 和 $a$ 之间：cout << 1 << " " << a << "\n";
$i$ 在 $b$ 和 $n$ 之间：cout << b << " " << n << "\n";
以及 $1$ 和 $b$ / $a$ 和 $n$ 之间的组合。

这 5 对 $(l, r)$ 共同构成了一个充分条件。出题人已经保证，只要一个 $i$ 不是那 4 种“不可能”的情况，那么它一定会被这 5 对 $(l, r)$ 中的至少一个所覆盖并设为 $1$ 。

总结

你的 WA2 原因： -1 的条件判断不完整，漏掉了 $p_i=1$ 和 $p_i=n$ 这两种情况。
jiangly 的解题思路：
- 排除法： 先用 4 个条件把所有 $x_i=1$ 但不可能实现的情况判为 -1。
- 构造法： 如果没判 -1，说明所有 $x_i=1$ 的位置都是“可能”的。此时，直接输出一个固定的、足够强大的 5 操作组合，这个组合是基于 $1$ 的位置 ( $a$ ) 和 $n$ 的位置 ( $b$ ) 构造的。
你的代码和 jiangly 代码的差距：
- 你的 WA 代码试图自己去构造 $(l,r)$ （用了前缀后缀最大值），这太复杂了，而且因为 -1 判错了，所以这个构造一定也是错的。
- jiangly 的 AC 代码意识到这道题的关键是“排除不可能”，而不是“构造可行解”。构造可行解的部分，直接用了题目给的 5 次机会扔了一个“万能”解。

这个分析清楚吗？你想不想试试用 $a$ （ $1$ 的位置）和 $b$ （ $n$ 的位置）来重新思考一下你自己的构造？

这道题目在考什么

这道题非常典型，它在 $1500 \sim 1700$ 分段很常见。你在这道题上遇到困难（WA）并不可怕，相反，攻克它对你冲上 1600 分极有价值。

我们来总结一下。

🧐 这一题主要在考验什么？

这道题表面上是“构造”，但核心是“分析与排除”。它主要考验你两种能力：

分析操作的“死穴” (寻找不可能)
- 绝大多数构造题的第一个突破口，不是“我怎么构造”，而是“我怎么构造都做不到什么？”
- 这道题的操作 $(l, r)$ 有两个硬性限制：
  1. 位置限制: $l < i < r$ 。这直接排除了 $i=1$ 和 $i=n$ 永远不可能被设为 $1$ 。
  2. 值限制: $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 。这直接排除了 $p_i = 1$ (因为它不可能 $> \min$ ) 和 $p_i = n$ (因为它不可能 $< \max$ ) 的位置。
- 你的首要任务就是找出这 4 种“死穴”。一旦 $x$ 字符串要求你在“死穴”上取 $1$ ，你就必须立刻输出 -1。你 WA 的原因就是因为只判断了前两种。
解读题目的“弦外之音” (寻找充分条件)
- 题目给出了两个强力提示：
  - "你最多可以进行 5 次操作"
  - "你不必最小化操作次数"
- 当你看到这种话，要立刻在脑中拉响警报：“这题不需要我为 $x$ 精确构造，而是要我找一个‘万能’的、火力足够猛的固定操作组合！”
- 我们的目标变成了：用 $\le 5$ 次操作，覆盖所有“可能”被点亮的 $i$ 。既然 $x_i=0$ 时 $s_i$ 可以是 $1$ ，那我们就“用力过猛”一点，把所有能点亮的 $i$ 全都点亮。
- jiangly 的代码就是这么做的。他找到了排列中最重要的两个“锚点”—— $1$ 的位置 $a$ 和 $n$ 的位置 $b$ ——然后用 $(1, a), (1, b), (a, b), (a, n), (b, n)$ 这几组操作（或类似的组合）构成了一个“火力网”，确保把所有“非死穴”的位置全都覆盖了。

🚀 以后我如何提升？

要从 $1200$ 提升到 $1600$ ，你必须学会超越“算法模板”，开始掌握这类“思维型”题目。

1. 训练你的“逆向思维”

下次遇到构造题时， 强迫自己停下 1 分钟。
不要先想 "How to do it?" (如何实现)
首先问自己 "What can I NOT do?" (什么做不到)
在草稿纸上列出操作的所有限制。这些限制就是你 if (...) { cout << -1; return; } 语句的来源。在 CF 比赛中，这能帮你至少拿到 30% 的分数 (WA on test X)，而不是 WA on test 2。

2. 识别“提示性约束”

"最多 $k$ 次" (且 $k$ 很小, 比如 5, 8, 20) $\rightarrow$ 提示你答案可能是一个固定的、小的操作集，或者是一个简单的搜索/暴力。
"时间限制 3.0 秒" $\rightarrow$ 提示算法复杂度可能比较高，比如 $O(n \sqrt{n})$ 或者 $O(n \log^2 n)$ 。
"你不必最小化/最大化" $\rightarrow$ 强提示！说明你只需要找到一个可行解，赶紧去找“万能”的、最暴力的构造方法。

3. 将其纳入你的 Obsidian 知识库

我建议你不要只为这道题建一个笔记，而是为你这种“思维模式”建一个笔记。

建一个新笔记： [[思维模式 - 构造题]]
标签： #ProblemSolving/Constructive #ThinkingPattern
内容：
- ## 构造题的黄金法则：先找“-1”
- > "What can I NOT do?"
- > 仔细分析操作的“死穴”或“不变性”。
- > - **案例：** [[CF2163B - Siga ta Kymata]]
- > - **位置死穴：** $i=1$ 和 $i=n$ 无法被操作。
- > - **值死穴：** $p_i=1$ 和 $p_i=n$ 的位置无法被操作。
- ## 识别“弦外之音”
- > 题目的约束条件本身就是提示。
- > - "不必最小化" $\rightarrow$ 寻找一个“万能”的、覆盖所有情况的充分条件，而不是精确的必要条件。
- > - **案例：** [[CF2163B - Siga ta Kymata]]
- > - "最多 5 次" + "不必最小化" $\rightarrow$ 直接用 $1$ 和 $n$ 的位置构造一个固定的“火力网”，覆盖所有“可能”的点。

通过这种方式，你下次再遇到构造题时，就可以先打开 [[思维模式 - 构造题]] 这个笔记，它会立刻提醒你正确的思考路径。

你觉得这个总结有帮助吗？我们是继续分析下一道题，还是你想找一道类似的“构造题”来练习一下这种思维？

CF 题解思路

设整数 $x$ 在置换 $p$ 中的位置为 $pos_x$ 。让我们看看对于哪些索引 $i$ ，我们永远不能将 $s_i$ 设置为 $1$ ，即使有无限多的操作。

首先，在操作 $(l, r)$ 中，我们只考虑索引 $i$ ，使得 $l < i < r$ 。这意味着我们永远不能将 $s_1$ 或 $s_n$ 设置为 $1$ 。此外，我们只考虑指数 $i$ ，使得 $p_i$ 在 $p_l$ 和 $p_r$ 之间，但不等于这些。这意味着我们永远不能将 $s_{pos_1}$ 或 $s_{pos_n}$ 设置为 $1$ 。通常，如果 $x_1 = 1$ 、 $x_n = 1$ 、 $x_{pos_1} = 1$ 或 $x_{pos_n} = 1$ ，则无法解决问题。现在我将证明，对于任何二进制串 $x$ ，使得 $x_1 = x_n = x_{pos_1} = x_{pos_n} = 0$ ，在 $5$ 运算中，该问题总是可解的。

WLOG，假设 $pos_1 < pos_n$ 。考虑使用 $pos_1$ 和 $pos_n$ 作为我们操作的端点是很自然的。

例如，通过使用操作 $(1, pos_1)$ 和 $(1, pos_n)$ ，我们将为每个 $1 < i < pos_1$ 设置 $s_i = 1$ 。同样，对于操作 $(pos_1, n)$ 和 $(pos_n, n)$ ，我们将为每个 $pos_n < i < n$ 设置 $s_i = 1$ 。通过使用操作 $(pos_1, pos_n)$ ，我们为每个 $pos_1 < i < pos_n$ 设置了 $s_i = 1$ 。通过这些 $5$ 操作，我们最终为 $(1, pos_1) \cup (pos_1, pos_n) \cup (pos_n, n)$ 中的每个 $i$ 设置了 $s_i = 1$ ，这保证我们已经解决了问题。

CF 题解代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n+1);
    int mn = 1, mx = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[mn]) mn = i;
        if (a[i] > a[mx]) mx = i;
    }
    string t; cin >> t;
    t = " " + t;
    if (t[1] == '1' || t[n] == '1') {
        cout << -1 << "\n";
        return;
    }
    if (t[mn] == '1' || t[mx] == '1') {
        cout << -1 << "\n";
        return;
    }
    cout << 5 << "\n";
    cout << 1 << " " << mn << "\n";
    cout << 1 << " " << mx << "\n";
    cout << mn << " " << n << "\n";
    cout << mx << " " << n << "\n";
    cout << min(mn, mx) << " " << max(mn, mx) << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}