题解：AT_abc399_d [ABC399D] Switch Seats

题意

N

组数字对（称为“情侣对”）排成一列。
请统计满足以下所有条件的 两对不同的情侣对

(a, b)

的组数：

在原序列中， $a$ 的两个出现位置不邻接。
在原序列中， $b$ 的两个出现位置不邻接。
通过执行以下操作（次数不限），可以使 $a$ $a$ 的两个出现位置邻接，同时 $b$ $b$ 的两个出现位置也邻接：
- 选择两个位置 $(i, j)$ 满足 $A_i = a$ 且 $A_j = b$ ，并交换这两个位置的值。

给定一个长度为

2N

的序列

A = (A_1, A_2, \dots, A_{2N})

，其中每个

1, 2, \dots, N

恰好出现两次。
对于

T

个测试用例，分别输出答案。
~~我是天才。~~
好了，不整了。
下面是正片：求存在多少个数对

(a,b)

满足上述条件。
~~我是天才。~~

思路

对于每一个

a_i(2\le i \le 2n)

，判断:

是否在之前出现过
- 使用数组记录最后一个数并判断
是否连续
前一个或后一个是否是下一次出现的前一个或后一个

代码

CPP

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

int a[1000010];
int lst[1000010];

void solve() {
    int n;
    cin >> n; 
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
        lst[a[i]] = i;
    }
    a[2 * n + 1] = 0;
    int ans = 0;
    for (int i = 2; i <= 2 * n; i++) {
        if(lst[a[i]] <= i + 1) continue;
        if(a[lst[a[i]] + 1] == a[i + 1] || a[lst[a[i]] - 1] == a[i - 1]) ans ++;
    }
    cout << ans << "\n";
}

signed main() {
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

题解：AT_abc399_d [ABC399D] Switch Seats

文章操作

题意

思路

代码

相关推荐

评论

题解：AT_abc399_d [ABC399D] Switch Seats