AtCoder Beginner Contest 206

比赛链接：Here

AB水题，跳过

C - Swappable

在数组中找到满足条件的数对 #card=math&code=%28i%2Cj%29)

• #card=math&code=1%20%5Cle%20i%20%3C%20j%20%20%5Cle%20N%20%28N%5Cin%5B2%2C3e5%5D%29)
• 

一道经典利用 map 减少搜索规模的题，

先假设每个数互不相同：ans = n * (n - 1) / 2

map 存每个数出现的次数，然后减去相同的情况 ans -= x * (x - 1) / 2

【AC Code】

void solve() {
    ll n;
    cin >> n;
    ll ans = n * (n - 1) / 2;
    map<ll, ll>mp;
    for (int i = 1; i <= n; ++i) {
        ll x; cin >> x;
        mp[x]++;
    }
    for (auto x : mp) 
        ans -= x.second * (x.second - 1) / 2;
    cout << ans;
}

D - KAIBUNsyo

在数组 中有 个正整数，给定一种操作：

• 选择 和 ，将数组中全部 替换为

请问最少次数是多少可以使得数组$A $ 回文

首先一个重要的点：

• 对于每一个 的数对，最终都会被某一个相同的数替代

让我们将其视为连接无向图中顶点 之间的边。

然后，我们可以看到以下事实：

• 对于每个整数对 #card=math&code=%28i%2Cj%29) ，如果 和 属于图的同一个连通分量，则 和 都应该用相同的整数代替。

现在，我们如何最小化操作次数以使连通分量中的所有整数都相同？

如果一个连通分量有 个整数，显然我们需要 次或更多次操作才能使它们成为相同的整数。 即目标可以在 次替换中实现，如下所述：

在连通分量中固定一个整数，并将连通分量中的所有其他整数更改为固定整数。

因此，该问题的解决方案是（ 中不同整数的数量）-（图的连通分量的数量）。

有几种方法可以找到这个值； 两种典型的方法是：

• 对每个连接的组件执行 DFS 或 BFS。#card=math&code=%5Cmathcal%7BO%7D%28N%29)
• 使用并查集。#card=math&code=%5Cmathcal%7BO%7D%28N%5C%20log%5C%20N%29)

这里采用 DFS 解决问题

【AC Code】

using G = vector<vector<int>>;
void dfs(int u, vector<bool> &f, G &g) {
    if (!f[u]) {return;}
    f[u] = false;
    for (auto &v : g[u]) dfs(v, f, g);
}
void solve() {
    int n; cin >> n;
    vector<int>a(n);
    vector<bool>f(2e5 + 10, false);
    G g(2e5 + 10);
    int cnt = 0;
    for (auto &x : a) {
        cin >> x;
        if (!f[x]) {f[x] = true, cnt++;}
    }
    int p = 0, q = n - 1;
    while (p < q) {
        g[a[p]].emplace_back(a[q]);
        g[a[q]].emplace_back(a[p]);
        p++, q--;
    }
    for (int i = 1; i <= 2e5; ++i) 
        if (f[i]) { cnt--; dfs(i, f, g); }
    cout << cnt << "\n";
}

F - Interval Game 2

Alice 和 Bob 又在玩游戏了，

他们有 个半开区间 #card=math&code=%5BL_i%2CR_i%29) 来进行 Game：

• Alice 和 Bob 交替进行以下操作，Alice 先行。
  从 个间隔中，选择一个不与任何已选择的间隔相交的间隔。

无法进行操作的玩家失败，其他玩家获胜。

如果两个玩家都以最佳操作，哪个玩家会获胜？

https://drken1215.hatenablog.com/entry/2021/06/19/224100

const int N = 100;
int n;
vector<int>L, R;
vector<vector<int>>dp;
int solve(int l = 0, int r = N) {
    if (l == r) return 0;
    if (dp[l][r] != -1)return dp[l][r];
    set<int>s;
    for (int i = 0; i < n; ++i) {
        if (l <= L[i] and R[i] <= r) {
            int tmp = solve(l, L[i]) ^ solve(R[i], r);
            s.insert(tmp);
        }
    }
    int grundy = 0;
    while (s.count(grundy)) ++grundy;
    return dp[l][r] = grundy;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        cin >> n;
        L.resize(n), R.resize(n);
        for (int i = 0; i < n; ++i) {
            cin >> L[i] >> R[i];
            L[i]--, R[i]--;
        }
        dp.assign(N, vector<int>(N + 1, -1));
        cout << (solve() > 0 ? "Alice\n" : "Bob\n");
    }
}