题解：CF1956B Nene and the Card Game

原题链接

• 洛谷 CF1956B Nene and the Card Game

题意简述

一副牌有 $1\sim n$ 各 $2$ 张，分给 $2$ 名玩家并轮流出牌，当桌上有相同牌时能获得 $1$ 分，求最优策略下先手的最大得分。

解题思路

每种牌各有 $2$ 张，有两种情况：

• 对子：$2$ 张牌都在同一名玩家手里，无论如何迟早会得分。
• 单牌：双方各有 $1$ 张，后出牌的玩家会得分。

对于每一回合，分类讨论：

• 若先手出对子，后手也出对子（双方的对子数量相同）。
• 若先手出单牌，后手出对应的单牌。

不难发现先手在单牌中无法得分，所以先手的最终得分为先手牌中的对子数量。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=200005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int t;
			cin>>t;
			a[t]++;
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==2)ans++;
		}
		cout<<ans<<'\n';
		for(int i=1;i<=n;i++)a[i]=0;
	}
	return 0;
}