[EOJ 1837] 小强的烦恼

Deuchie edited 9 月,2 周前

要好好理解「敌人的敌人是朋友」这句话。重点分析一下把 add_rival(a, b) 的正确性。其实应该分四种情况讨论,但像我这么写的话就避免了显式的 if 判断(虽然有一定性能损失)。

void add_rival(u64 const a, u64 const b) {
    connect(a, real_rival_of(b).value_or(a)); // real_rival_of returns an optional rival, if a is in no gang
    connect(b, real_rival_of(a).value_or(b)); // returns nothing, in which case 2nd param. would be what's in value_or().
    direct_rivals_[a] = real_boss_of(b);
    direct_rivals_[b] = real_boss_of(a);
}
  1. 如果 a 和 b 都没有帮派:

    前两行会把 aa 自己连接起来,约等于无效。后两行设置好 rival 关系。

  2. 如果其中一个有帮派:

    前两行会把不在帮派里的连接到相应帮派中去。后两行设置好 abrival 关系(主要是那个新加入帮派的)。

  3. 如果两个都有帮派:

    这种情况下最多可能涉及到四个帮派的关系。前两行把有共同敌人的帮派合并,后两行其实可有可无,是一个性能的 overhead。

上面这样的写法比较简洁所以我这么写了。两个赋值带来的 overhead 不一定就比 if 跳转和增大的代码长度的影响大哦(boki⭐)。


完整代码:

#include <iostream>
#include <vector>
#include <optional>

using namespace std;
using u64 = uint64_t;

class ConnectivitySet {
  public:
    ConnectivitySet(u64 const size) : direct_bosses_(size) {
        for (u64 i = 0; i < size; ++i) {
            direct_bosses_[i] = i;
        }
    }

    void connect(u64 const a, u64 const b) {
        auto const kRealBossA = real_boss_of(a);
        auto const kRealBossB = real_boss_of(b);
        direct_bosses_[kRealBossA] = kRealBossB;
    }

    bool is_connected(u64 const a, u64 const b) { return real_boss_of(a) == real_boss_of(b); }

  private:
    vector<u64> direct_bosses_;

  protected:
    u64 real_boss_of(u64 const a) {
        if (direct_bosses_[a] == a) {
            return a;
        }
        return direct_bosses_[a] = real_boss_of(direct_bosses_[a]);
    }
};

class GangRival : protected ConnectivitySet {
  public:
    GangRival(u64 size) : ConnectivitySet(size), direct_rivals_(size) {}

    void add_rival(u64 const a, u64 const b) {
        connect(a, real_rival_of(b).value_or(a));
        connect(b, real_rival_of(a).value_or(b)); // if no rival do not connect (connect with self)
        direct_rivals_[a] = real_boss_of(b);
        direct_rivals_[b] = real_boss_of(a);
    }

    enum class GangMemberRelation { kNull, kFriend, kRival };
    GangMemberRelation query(u64 const a, u64 const b) {
        auto const kRealBossOfA = real_boss_of(a);
        auto const kRealBossOfB = real_boss_of(b);
        if (kRealBossOfA == kRealBossOfB) {
            return GangMemberRelation::kFriend;
        }
        if (real_rival_of(kRealBossOfA) == kRealBossOfB) {
            return GangMemberRelation::kRival;
        }
        return GangMemberRelation::kNull;
    }

  private:
    vector<optional<u64>> direct_rivals_;

    bool not_in_gang(u64 const kMemberId) const { return direct_rivals_[kMemberId] == nullopt; }

    optional<u64> real_rival_of(u64 const a) {
        if (direct_rivals_[a] == nullopt) {
            return nullopt;
        }
        return real_boss_of(direct_rivals_[a].value());
    }
};

int main() 
    u64 t;
    cin >> t;
    for (u64 i = 0; i < t; ++i) {
        u64 n, m;
        cin >> n >> m;
        GangRival gr_set(n);
        for (u64 i = 0; i < m; ++i) {
            char kOrder[2];
            u64 a, b;
            cin >> kOrder >> a >> b;
            a -= 1, b -= 1;
            switch (*kOrder) {
            case 'A': {
                gr_set.add_rival(a, b);
            } break;
            case 'Q': {
                switch (gr_set.query(a, b)) {
                case GangRival::GangMemberRelation::kFriend: {
                    cout << "In the same gang.\n";
                } break;
                case GangRival::GangMemberRelation::kNull: {
                    cout << "Not sure yet.\n";
                } break;
                case GangRival::GangMemberRelation::kRival: {
                    cout << "In different gangs.\n";
                } break;
                }
            } break;
            }
        }
    }
}

Comments

Deuchie

呃,发现代码里夹了一个 not_in_ganglegacy code……

你当前正在回复 博客/题目
存在问题!