2015-06-29

b413. 虛擬女友

1. Problem
2. Sample Input
3. Sample Output
4. Solution

Problem

曾經有一部採訪影片《BBC 紀錄片：別和日本人談性 No Sex. We’re Japanese.》在網路上流傳，其中有一段談到虛擬遊戲中的生活，不少男性以遊戲中的女角發生關係，其中以一款遊戲「Love Plus」為大宗，即使是擁有現實和虛擬的生活，若要選擇其中一方站，不少男性仍然「我選擇死亡」回答。

現在先不解決男女雙方的問題、在彼此關係上要如何運作，如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活，只有同性朋友要怎麼交流呢？於是有一場專門為這些男性舉行的一場交友會，規則如下所述：

一開始全場男性都彼此不認識
每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
每一個時刻，其中兩個男性會因談論遊戲而成為朋友
自己朋友的朋友也會成為朋友
如果朋友的虛擬女友的類型不同，他們有可能會因偏好女友類型不同而爭吵，稱為不穩定對。

請問每一個時刻下，有多少穩定對朋友。

Sample Input

Sample Output

Solution

IPSC 2015 F 那一題發生於男女雙方都會進行聯集，而這一題只有男方會進行聯集。

合併兩團男時，只有下標 (女友類型) 相同會成為穩定對，可以利用合併排序來完成，能發生合併表示男的彼此之間不認識，只要考慮有多少女方相同即可。每一次將小堆合併到大堆中，由於要計數合併複雜度需要 $O(min(|A|, |B|) \times \log N)$，若搭配 hash 可以降到 $O(min(|A|, |B|)$。一般并查集 joint 複雜度為 $O(1)$，整體操作只需要 $O(N)$，但為了要計數，整體的複雜度為 $O(N \log N)$。

可以選擇合併排序來完成，每一次把兩堆的女方列出來，把兩堆相同類型的次數相乘，列出來可以循序做，或者是串列完成，每一次保證堆裡面的女方順序是由小排到大，合併複雜度就為 $O(|A| + |B|)$，均攤下複雜度為 $O(N \log N)$，當測資不夠隨機複雜度會掉到 $O(N^2)$，情況是每一次只把大小為 1 的堆合併到大小 i-1 的堆。

在測資隨機生成下，第二種作法會來得比第一種快。第一種做法要搭配 ordered_map 或者是 unordered_map，寫起來會比較不方便。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65536;
vector<int> son[MAXN];
int parent[MAXN], A[MAXN];
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        long long tot_pair = 0;
        int x, y;
        map< pair<int, int>, int > R;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            son[i].resize(1, i);
            R[pair<int, int>(i, A[i])] = 1;
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            x = parent[x], y = parent[y];
            if (x != y) { // merge small to large
                if (son[x].size() > son[y].size())
                    swap(x, y);
                for (auto &e: son[x]) {
                    pair<int, int> t(parent[e], A[e]);
                    R[t]--;
                    if (R[t] == 0)  R.erase(t);
                    parent[e] = y;
                    son[y].push_back(e);
                    tot_pair += R[pair<int, int>(parent[e], A[e])];
                }
                for (auto &e: son[x])
                    R[pair<int, int>(parent[e], A[e])]++;
                son[x].clear();
            }
            printf("%lld\n", tot_pair);
        }
    }
    return 0;
}

Morris' Blog

b413. 虛擬女友

contents

Problem

Sample Input

Sample Output

Solution