前言
题目算比较简单的思维题目,很符合 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。