P10247 Pairing Pairs题解

· · 题解

题意

一共有 m 对数对，要对于每个数对，找到一个数对，满足这两个数对中没有相同的数字。

赛事记录

分析

与官方题解不一样的是，我万万没想到这题是道图论题。

咱们首先思考一个问题，对于某个数对，对于它来说能满足题意的数对的 u 肯定与这个数对的 u 不相同，也就是我们首先可以排除 u 与这个数对相同的数对。

那么对于这个问题，我们可以想到什么？

当然是排序，以 u 为第一关键字按照升序排序（降序也行）。

那么接下来，我们能得出的一点是，在排完序后，对于当前要判断的数对，我们可以用二分的方法找出最后一个数对的 u 小于该数对的 u 的位置，与第一个数对的 u 大于该数对的 u 的位置（也就是前驱与后缀）。接下来要找出前驱与后缀中满足题意的数对。

如果直接枚举前驱后缀复杂度肯定是错的，那么如何优化呢？

对于前驱后缀中的每一个数对，我们能保证的是，它的 u 不等于当前数对的 u，且由题意可知，每个数对的 u 和 v 都不相同。

那么我们不能保证什么？

  1. 前驱后缀中的数对的 u 与该数对的 v 是否相同;
  2. 前驱后缀中的数对的 v 与该数对的 u 是否相同;
  3. 前驱后缀中的数对的 v 与该数对的 v 是否相同;

也就是对于某个数对的 u，可能会与该数对的 v 相同；对于某个数对的 v，可能会与该数对的 u,v 相同。

但是！

如果我们有了两个不同的 u 值，那么它们中至少有一个 u 与该数对的 v 不同；同理，如果我们有了三个不同的 v 值，那么它们中至少有一个 v 与该数对的 v 不同。

所以，对于每个前缀、后缀，我们只需记录最多 6 个数对，在判断时，枚举每个存下来的数对，看看其中有没有符合的。

容易知道，改复杂度绝对正确。

Code

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

struct node {
    int x;
    int y;
    int id;
    friend bool operator<(node l, node r) {
        if (l.x != r.x)
            return l.x < r.x;
        return l.y < r.y;
    }
} s[300005];
int tot;
int tmp[300005];
vector<int>qian[300005];
map<pair<int, int>, int>q;
map<int, int>qx, qy;
vector<int>hou[300005];
map<pair<int, int>, int>qq;
map<int, int>qqx, qqy;

int ch(int a, int b) {
    return (s[a].x != s[b].y && s[a].y != s[b].y && s[a].y != s[b].x);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (x != y)//其实这个判断没啥用
            s[++tot].id = i, s[tot].x = x, s[tot].y = y;
    }
    sort(s + 1, s + tot + 1);
    for (int i = 1; i <= tot; i++) {//重点
        qian[i] = qian[i - 1];
        if (qian[i].size() < 6) {
            if (!q[make_pair(s[i].x, s[i].y)] && qx[s[i].x] <= 1 && qy[s[i].y] <= 2) {
                q[make_pair(s[i].x, s[i].y)] = 1;
                qx[s[i].x]++;
                qy[s[i].y]++;
                qian[i].push_back(i);
            }
        }
    }
    for (int i = tot; i >= 1; i--) {
        hou[i] = hou[i + 1];
        if (hou[i].size() < 6) {
            if (!qq[make_pair(s[i].x, s[i].y)] && qqx[s[i].x] <= 1 && qqy[s[i].y] <= 2) {
                qq[make_pair(s[i].x, s[i].y)] = 1;
                qqx[s[i].x]++;
                qqy[s[i].y]++;
                hou[i].push_back(i);
            }
        }
    }
    for (int i = 1; i <= tot; i++) {
        if (s[i].x == s[i].y || tmp[s[i].id])
            continue;
        int ans = 0;
        int l = 1, r = i - 1;//手写二分
        while (l <= r) {
            int mid = (l + r) / 2;
            if (s[mid].x < s[i].x) {
                ans = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        if (ans != 0) {
            int f = 0;
            for (int j = 0; j < (int)qian[ans].size(); j++) {
                int u = qian[ans][j];
                if (ch(u, i)) {
                    f = s[u].id;
                    break;
                }
            }
            if (f) {
                tmp[s[i].id] = f;
                tmp[f] = s[i].id;
                continue;
            }
        }
        ans = 0;
        l = i + 1, r = tot;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (s[mid].x > s[i].x) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        if (ans != 0) {
            int f = 0;
            for (int j = 0; j < (int)hou[ans].size(); j++) {
                int u = hou[ans][j];
                if (ch(u, i)) {
                    f = s[u].id;
                    break;
                }
            }
            if (f) {
                tmp[s[i].id] = f;
                tmp[f] = s[i].id;
                continue;
            }
        }
    }
    for (int i = 1; i <= m; i++)
        cout << tmp[i] << " ";
}