CF1956B Nene and the Card Game

前言

题目算比较简单的思维题目，很符合 CF 的出题特点。

题目大意

现在有 $1$ 到 $n$ 的牌每个两张。你现在有 $n$ 张，并且在输入中给出。另一个人有剩下的 $n$ 张牌。

你和那个人进行一个游戏：

两人轮流。你先手，另一个人后手。一共进行 $2 \times n$ 轮。
每轮的那个人需要出一张牌。
如果那张牌上的数字是之前出过的，那么这个人的一分，否则不得分。
牌出完后就扔掉，无论你有没有得分。

注意每个人都可以看见出过的牌。

思路

我们假设第一个人有 $s$ 对相同的牌。

那么这个人就有 $n - 2s$ 张不成对的牌。

那么你也有 $n - 2s$ 张不成对的牌。

所以你有 $\frac{n - (n - 2s)}{2} = s$ 对相同的牌。（修正了一下楼上的题解）。

我们发现两个人有着相同多对的牌，所以我们可以发现一个这样的后手必胜策略：

两个人都把对子出完，两个人各得 $s$ 分。
由于现在两个人的牌都是完全一样的了，所以每次先手出了一张牌的时候，后手就可以出相同的牌，这样后手就得分了。

所以，在两个人都极其聪明的情况下，最后的得分是：

先手 $s$ 分，后手 $n-2s+s=n-s$ 分。

由于 $s$ 一定小于 $n$ 的一半，所以答案只用输出 $s$ 就行了。

代码

#include <bits/stdc++.h>

using namespace std;
int a[200005];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) {
        int n; cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + n + 1);
        int same = 0;
        for (int i = 1; i <= n; i ++) if (a[i] == a[i - 1]) same ++;
        cout << same << "\n";
    }
    return 0;
}

AC 记录：https://codeforces.com/contest/1956/submission/256619999。

前言

题目大意

思路

代码

评论 (0)