题解：CF1956B Nene and the Card Game

· · 题解

题意简述

一副牌有 1\sim n 各 2 张，分给 2 名玩家并轮流出牌。

当桌上有相同牌时能获得 1 分，求最优策略下先手的最大得分。

解题思路

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

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

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

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

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

参考代码

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

using ll=long long;
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;
}