模拟赛题讲解[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;
}