关于 P7339 『MdOI R4』Kotori

· · 题解

水博客太快乐了。。。

刚打完月赛，来水一发 T3 的题解。。。
T3 有一定思维难度，但是如果理解了题意应该很快就可以想出来。。。
本蒟蒻写的是分治，貌似大佬们都用了各种神仙算法。但本蒟蒻只想到了分治。显然复杂度不是最优的。。。

以下是正文

题意

为了让大家更好理解题目中世盟的比赛规则，我特意找来了今年萌王的赛程。（虽然题中是燃王但也差不多了。。。把第一位选手想成士道就好了。

//恭喜雪之下雪乃以 218 票的微弱优势战胜炮姐成为新一届萌王！！！
看到这张图怎么也会想到分治、线段树之类的和二有关的东西吧。。

实际上就是淘汰赛制，题中也正是是这么描述的。
一轮比赛包含一竖列中的多场比赛，一场比赛只有两个选手。

但是题中的世萌和现实中的世萌并不完全一样，因为萌王 Kotori 已经在暗中操纵了比赛。。。
Kotori 可以在一轮比赛的每场比赛中给任意一位选手加上 m 票，同时也可以决定平局时的胜负。

思路

这样的话,为了让士道得到燃王，我们只需要保证一号选手每次对战的对手战力都小于等于 a[1]+m 即可（可以等于，因为 Kotori 可以决定平局的胜负）。

接下来，我们观察士道的对手分别来自哪里：
第一轮的对手显然是 a[2]；
第二轮的对手来自区间 [3,4]；
第三轮的对手来自区间 [5,8]；
第四轮的对手来自区间 [9,16]；
。。。
第n轮的对手来自区间 [2^{n-1}+1,2^{n}].

知道了每位对手的位置，就可以考虑直接枚举（或递归）找到每一个区间，再在区间内寻找：按照比赛规则，Kotori 能否为士道“安排”一个战力小于等于 a[1]+m 的对手。

接下来就是重点了：

如何找到这样的一位选手呢？

直接瞎搞。

我们可以考虑分治。

假设要在区间 [l,r] 内找一个战力小于等于x的选手，那么先在左子区间 [l,mid] 和右子区间 [mid+1,r] 内寻找小于等于 x 的选手；
若两个子区间内都能找到这样的选手，那么显然区间 [l,r] 内可以找到小于等于 x 的选手；
若两个子区间都没有找到，那么显然区间 [l,r] 内无法找到小于等于x的选手；
若一个子区间内找到了小于等于 x 的选手，而另一个子区间没有找到，那么设找到了的选手的战力是 y ，然后在没有找到的区间内找小于等于y+m的选手，这样他就可以被 y 淘汰掉，区间 [l,r] 内也就可以找到小于等于 x 的选手。

代码如下：

int del(int l,int r,int x){
    if(l==r) return a[l]<=x ? a[l] : 0;
    int mid=(l+r)>>1;
    int l1=del(l,mid,x),r1=del(mid+1,r,x);
    if(l1&&r1) return max(l1,r1);//两个子区间都可以找到
    if(!l1&&!r1) return 0;//两个子区间都找不到
    else if(!l1) l1=del(l,mid,r1+m);//只有一个子区间找到了
    else if(!r1) r1=del(mid+1,r,l1+m);
    if(!l1||!r1) return 0;
    else return min(l1,r1);
}

//码风丑陋大家不要在意。。。

最后再来整理一下思路：
首先递归找到所有对手的区间；
再在每个区间内分治，寻找小于等于 a[1]+m 的选手；
若每个区间都能找到，则输出 “Kotori”，否则输出 “Yoshino”。

思路非常简单，代码也非常好写，就是稍有一些思维难度。。。

代码

贴上Ac代码：

#include<bits/stdc++.h>
using namespace std;
const int Max=(1<<20)+10;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int t;
int k,m;
int a[Max];
int del(int l,int r,int x){
    if(l==r) return a[l]<=x ? a[l] : 0;
    int mid=(l+r)>>1;
    int l1=del(l,mid,x),r1=del(mid+1,r,x);
    if(l1&&r1) return max(l1,r1);
    if(!l1&&!r1) return 0;
    else if(!l1) l1=del(l,mid,r1+m);
    else if(!r1) r1=del(mid+1,r,l1+m);
    if(!l1||!r1) return 0;
    else return min(l1,r1); 
}
bool che(int l,int r){
    if(l==r) return 1;
    int mid=(l+r)>>1;
    if(!che(l,mid)) return 0;
    int x=del(mid+1,r,a[1]+m);
    if(x) return 1;
    return 0;
}
int main(void){
    t=read();
    while(t--){
        k=read(),m=read();
        if(k==0){ printf("Kotori\n"); continue; } 
        for(int i=1;i<=(1<<k);++i){ a[i]=read();a[i]++; }
        if(che(1,(1<<k))) printf("Kotori\n");
        else printf("Yoshino\n");
    }
    return 0;
}

关于贪心

乍一看这道题很容易陷入贪心的误区（我一开始也是这么想的）。
巨佬 yummy 成功 hack 了所有我能想到的贪心，基本上也 hack 了此题的所有骗分方法。
如果想知道自己是怎么被 hack 的，建议跳转至 这篇博客。

关于复杂度

实不相瞒，本蒟蒻在构思代码时并没有细想复杂度的问题，只觉得大约是个 O(nlogn) （即 O(k*\ 2^{k})），显然属于 O(能过) 的范围，于是就这么写了。
写题解的时候，才发现不会证复杂度，于是就这么一直卡着。。。
太弱了，一直也没证出来。。。
直到后来巨佬 yummy 证出了复杂度。。。
因此本题解中并没有代码复杂度的证明，想看复杂度证明建议跳转至 还是这篇博客。

如有不足还请指出。

蒟蒻第一次提交题解，望管理大大通过。。。

//实不相瞒，月赛前一天鄙人正与一位巨佬彻夜谈论世盟。。。图也是那位巨佬提供的。。。