题解归档 - cf2236D

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

• 本地编号：cf2236D
• 本地来源：problems/cf2236D/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/D
• 原始标题：cf2236D Brand New Tatar TV Show

思路

cf2236D Brand New Tatar TV Show

题意

给定 multiset a 与整数 k。正常规则：Dabir 先手，第一步可删任意元素；之后每步在剩余元素中选 y，满足 0 ≤ y - x ≤ k（x 为上一步删掉的值），无法操作者输。

Arseniy 代替 Dabir 做开局第一步（可删任意元素），之后 Egor 先走，再 Dabir、Egor 交替。问是否存在 Arseniy 的开局删法，使得在双方最优下 Egor 必胜。

结论

排序后压成 (值, 频次) 列表，从最大值开始模拟「被迫删最大」的过程：

1. 若当前最大值的频次为偶数 → YES（Arseniy 删掉一个最大后，Egor 按对称策略赢）。
2. 若只剩一种值且频次为奇数 → NO。
3. 若 mx - second_mx ≤ k → YES（删掉最大后，Egor 可以一步跳到次大，逼 Dabir 无子可走）。
4. 否则删掉整个最大值种类，继续看新的最大。

证明要点

• Arseniy 最优只会考虑删某个最大值（删非最大不会比删最大更「限制」Egor）。
• 删掉一个最大后，Egor 先手。若剩余最大频次为偶数，Egor 镜像 Dabir 的删法即可。
• 若最大频次为奇数且与次大距离 ≤ k，Egor 删次大后 Dabir 无法合法删除（次大已空，更大的也空）。
• 若距离 > k，则无论 Arseniy 怎么删最大，局面等价于在更小值上重复同样分析 → pop 最大种类。

复杂度

每组 O(n log n) 排序 + O(不同值个数) ≤ O(n log n)。

实现

见 solution.cpp：排序计数 + 从尾部贪心判定。

校验

brute.cpp 用小值域 minimax 递归，gen.cpp 生成 n<=6 随机数据，可用于本地对拍。

代码

来源：problems/cf2236D/solution.cpp

/* Author: likely
 * Time: 2026-06-19 10:51:42
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll p[maxn+5],n,k,i,j,m;
vector<pair<ll,ll>>a;
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        for(i=1;i<=n;i++) scanf("%lld",&p[i]);
        sort(p+1,p+n+1);
        a.clear();
        a.push_back({p[1],1});
        for(i=2;i<=n;i++){
            if(p[i]==p[i-1]) a.back().second++;
            else a.push_back({p[i],1});
        }
        while(a.size()){
            m=a.size();
            if(a[m-1].second%2==0){
                printf("YES\n");
                break;
            }
            if(m==1){
                printf("NO\n");
                break;
            }
            if(a[m-1].first-a[m-2].first<=k){
                printf("YES\n");
                break;
            }
            a.pop_back();
        }
    }
    return 0;
}