题解归档 - cf755B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755B
• 本地来源：problems/cf755B/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/B
• 原始标题：CF755B PolandBall and Game

思路

CF755B PolandBall and Game

题意

两人轮流说单词，不能说已说过的。Poland 先手，词库各自给定，可重叠。无法继续说新词者输。问最优博弈下 Poland 是否必胜。

做法

设 Poland 独占词数 a、Enemy 独占 b、公共词 c。

• a > b：Poland 先用独占词耗死对方 → YES
• a < b：NO
• a == b：只剩公共词轮流说，先手胜当且仅当 c 为奇 → c%2==1 则 YES

验证

样例 + stress.py -n 500 与 minimax 暴力对拍。

代码

来源：problems/cf755B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:55:50
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
set<string>ss;
string s;
ll n,m,i,zc,cur,cnt;
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>s;
        ss.insert(s);
    }
    cnt=0;
    cur=0;
    for(i=1;i<=m;i++){
        cin>>s;
        if(ss.count(s)) cnt++;
        else cur++;
    }
    zc=n-cnt;
    if(zc>cur) cout<<"YES\n";
    else if(zc<cur) cout<<"NO\n";
    else if(cnt%2) cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}