题解：P7339 『MdOI R4』Kotori

_LogicFish_qwq · 2026-07-20 21:14:54 · 题解

有人能教教我 Kotori，Shido，Yoshino 这些名字分别怎么读吗……还有世界最萌大会是什么啊……

Part 0: 准备工作

你需要了解二分（或归并排序）的核心思想。不了解也没关系，通过此题你可以加深对它们的理解。

Part 1: 思路

题意简述

假设你是 Kotori，有 2^k 名选手参赛，票数为 a_i；使用淘汰赛的赛制（每轮刷掉一半的选手）。与以往不同的是，在每场比赛，你都可以给任意一方增加 m 票，且平局时你可以决定谁胜谁负。你的目标，是让序号 1 的 Shido 获得最终胜利。

从哪开始

首先分析 Shido 要和哪些人对决。

在第一轮，Shido 要和序号 2 对战；
在第二轮，Shido 要和 [3,4] 的赢家对战；
在第三轮，Shido 要和 [5,8] 的赢家对战；
那么在第 i 轮，Shido 要和 [2^{i-1}+1,2^i] 的赢家对战。

接下来，如果 Shido 要赢这些选手，要具备什么条件。显然是 a_1+m\ge a_{winner}，毕竟 Kotori 不仅可以给哥哥 m 票，平局时还能决定哥哥是冠军！
所以我们着手设计一个 find 函数，来寻找 [l,r] 中，是否有票数不超过 x 的选手存在。要是能找到，那么 Kotori 暗中操作一下就可以让 ta 光荣地被 Shido 打败啦（~~怎么有内幕口牙~~）。此外，淘汰赛这种涉及 2 的次幂的题目，预处理一个数组 pow2 存储这些次幂值总是好的。

`find` 函数的设计

首先，我们简单模拟（计算）可得：对于区间 [l,r]，要找这一区间的胜者，就是找出区间 \left[l,\dfrac{l+r-1}{2}\right] 和区间 \left[\dfrac{l+r+1}{2},r\right] 的胜者，再让两个胜者对决。而分别寻找这两个区间的胜者，又可以分成更小的区间取找……因此，我们知道了，这个 find 函数大概率是个递归。
那么递归的出口是什么呢？显然是在区间变成单点，即 l=r 的时候。返回什么呢？鉴于我们要找的是“在 [l,r] 里，票数不超过 x 的人（的票数，毕竟题目和“这个人是谁”关系不大）”，那么肯定是满足 a_l\le x 就返回 a_l，没找到就返回 -1（因为有 a_i=0 的情况，所以哨兵值就不能是 0）。
接下来，递归的部分怎么写？必然是需要求出中值 mid 的，用这个 mid 把区间划成左右两段，再分别找到其结果（假设叫做 lft 和 rgt 吧）。这个结果可能有这些情况：

如果不好理解，干脆这样思考：让**更厉害**的家伙和 Shido 对决，如果 Shido 依然是冠军，那他就**一定**是冠军啦！
问题是，我们能不能让这个胜利者晋级呢？毕竟 $-1$ 表示，这一区间里所有数都 $\gt x$，那么很可能也会把胜利者刷下去（票数仍然不够）。因此，我们需要“降低标准”，至少保证胜利者可以晋级，因此我们要在另一段寻找票数 $\le winner+m$ 的人。

这样层层筛选后，我们看看为 Shido 精心挑选的选手实力如何（就是比大小啦），如果返回值为 -1，说明找不到这样一个“可以让 Shido 胜利”的对手，那么 Shido 自然加冕无望了。
大概就是这样，所以我们快点写吧！

Part 2: 代码

:::success[AC Code]

//Someone tell Vedal there is a problem with my AI.
#include<iostream>
#include<cstdio>
//#include<vector>
#define int long long
const int MAXN=1<<20,INF=1e10+987;
int k,n,m,a[MAXN+5];
int pow2[30],flag;
int find(int l,int r,int x);
void Init(),PreSolve(),Input(),Solve(),Answer(),AC();
signed main(){
    AC();
    return 0;
}
void Init(){
    std::ios::sync_with_stdio(false),
    std::cin.tie(0),std::cout.tie(0);
    #ifndef ONLINE_JUDGE
    std::freopen("FLIE.in" ,"r",stdin );
    std::freopen("FLIE.out","w",stdout);
    #endif
}
void AC(){
    Init();
    int T=1;
    std::cin>>T;
    PreSolve();
    while(T--){
        Input();
        Solve();
        Answer();
    }
}
void PreSolve(){
    pow2[0]=1;
    for(int i=1;i<30;i++) pow2[i]=pow2[i-1]<<1;
}
void Input(){
    std::cin>>k>>m;
    n=pow2[k];
    for(int i=1;i<=n;i++) std::cin>>a[i];
}
void Solve(){
    flag=0;
    for(int i=0;i<k;i++) if(!(~find(pow2[i]+1,pow2[i+1],a[1]+m))) return (void)(flag=-1);
    //波浪线"~"表示按位取反，而-1的二进制表示是111...111，取反后变成000...000，即~x表示"判断x是否不是-1"
    //记得把每个区间的可能获胜的人都拉出来比一比！
}
void Answer(){
    std::cout<<(flag^-1?"Kotori":"Yoshino")<<'\n';
}
int find(int l,int r,int x){
    if(l==r) return a[l]<=x?a[l]:-1;
    int mid=l+r>>1;
    int lft=find(l,mid,x),rgt=find(mid+1,r,x);
    //找左右区间的赢家
    if(~lft&&~rgt) return std::max(lft,rgt);//都有就返回更大值
    if(~lft){//候选人在左侧，看右侧的人是否“能让候选人晋级”
        rgt=find(mid+1,r,lft+m);
        if(~rgt) return lft;
    }else if(~rgt){//右侧同理
        lft=find(l,mid,rgt+m);
        if(~lft) return rgt; 
    }
    return -1;
}

:::

Part 3: 注意事项

读入数据量较大，请使用合理的输入方式。
注意是所有右侧区间里的赢家与 Shido 比较，只有 Shido 一一战胜了所有人才能成为真正的“燃王”。
在 find 函数中，判断一定要带等号，因为 Kotori 可以决定平局的胜负，使我们想要的人胜利。
如果 pow2 数组算错了……嘶……