模拟赛题讲解[33]

来自 yukuai26 2023-08-06 noi.ac #3280

题目描述：

emoairx 有一个长度为 $n$ 的初始 $(a_i=i,1 \leq i \leq n)$ 的数组, 和长度为 $m$ 的交换序列, 他会按照序列顺序每次交换 $2$ 个数

你需要准确地删除恰好一个交换操作, 使得数字 $1$ 最后交换到第 $k$ 个位置, 并输出需要删掉的交换操作的序号

如果有多个答案，输出序号最小的交换操作的序号。数据保证有解。

输入格式：

第一行 $3$ 个正整数 $n,m,k$ , 表示 $n$ 个数, $m$ 个交换，最终希望数字 $1$ 交换到第 $k$ 个位置

接下来 $m$ 行每行 $2$ 个数 $a,b$ , 表示交换 $a,b$ 位置上的数字

输出格式：

输出一个数表示序号最小的交换操作的序号，删掉这个序号后数字 $1$ 可以交换到位置 $k$

输入样例：

10 10 9
1 8
8 3
3 4
4 7
7 2
6 2
9 10
3 10
9 3
6 9

输出样例：

7

数据范围：

对于 $100\%$ 的数据，$n,m \leq 100000$

题解：

考虑删除一个修改 $i$ 会有什么影响，即本应交换的 $a_i$ 和 $b_i$ 没有交换。

相当于这个调位置的人把 小 A 和 小 B 认错了，结果就是把修改做完以后，小 A 和 小 B 的原位置正好相反

因此我们可以先算出数组最终状态 $T$ ，然后依次考虑每个修改，直到发现某一步把 $1$ 和 $T_k$ 认错了。

时间复杂度 $\mathcal{O}(m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,m,k,a[N],b[N],p[N],x[N],y[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) a[i] = i, b[i] = i;
    for(int i = 1; i <= m; i++) { cin >> x[i] >> y[i]; swap(b[x[i]], b[y[i]]); }
    for(int i = 1; i <= n; i++) p[b[i]] = i;
    for(int i = 1; i <= m; i++)
    {
        int l = a[x[i]], r = a[y[i]];
        swap(b[p[l]], b[p[r]]);
        if(b[k] == 1) return cout << i << '\n', 0;
        swap(b[p[l]], b[p[r]]); swap(a[x[i]], a[y[i]]);
    }
    return 0;
}