头像

起名真难

QQ家族




离线:1天前


最近来访(1422)
用户头像
kindred
用户头像
南笙离梦
用户头像
耳朵龙
用户头像
一之为逸
用户头像
lizhuang
用户头像
su尔
用户头像
浩qsh
用户头像
种花家的兔兔
用户头像
Heming
用户头像
陌上花开Charlie
用户头像
Tiffen
用户头像
默_1
用户头像
zhuiyi
用户头像
77777777777
用户头像
SUPERDOGE
用户头像
云衣醉梦
用户头像
刘子涵
用户头像
KkkkkkkkkKK
用户头像
宇宙有边
用户头像
xiezere

新鲜事 原文

班上有个同学很喜欢蔡徐坤,在他每本书上面都写了蔡徐坤的名字。 然后我去问他借书,借回家后,奶奶看到我借的书上面有蔡徐坤的名字,就说“你要什么书,奶奶给你买,不用老跟蔡徐坤同学借。”(因为我之前也问那个同学借过几本书)


新鲜事 原文

不知道为啥,最近阅读量差的出奇,之前随便写个分享都能上100,现在每一篇都是30不到


新鲜事 原文

小区里搬来一户人家,孩子叫黄军。 黄军:我爸的公司在我的学校旁边,所以我们经常一起做8路公交车上学上班 我:那你们父子关系不错咯? 黄军:是啊,就是别人看我们赶公交一个个笑出强大 我:为啥 黄军:我也不知道,反正我到时经常赖床,有时赶不上公交,所以我爸老师催我‘黄军,快跑,8路来啦!’


新鲜事 原文

一次采访: 我:爸爸当你与我妈发生冲突时是怎么做的? 我爸:画画 我:难道是把我妈画的丑不拉几? 我爸:拿你妈的化妆品当颜料画的 我:妈妈当你与我爸发生冲突时是怎么做的? 我妈:去厕所 我:可是吃屎解决不了问题啊 我妈:找打?(啪啪啪) 我(揉脸):那是怎么做的? 我妈:拉完屎后冲水刷马桶 我:难道刷马桶有助于缓解愤怒?还是说拉完再吃新鲜的... 我妈:你等我拿拖鞋 我(揉屁股):为啥刷马桶啊? 我妈:拿你爸的牙刷刷的 从此我一直提倡我们家使用公筷公勺



董卓大家想必都听过吧。

(建议大家看看这个视频 以更好地了解董卓)

大家看完都知道了,董卓那边的人都喜欢用拳头说话

但,要是那边打起架来了,怎么记录谁打赢谁呢?

这就是我们今天要讲的——胜者树!

(往期分享点赞和阅读量都非常惨淡,希望各位可以点个赞或者帮忙宣传一下)

一,建树

先来看看胜者树的建树方法:

利用类似于树状数组的形式,运用二分,如果两端在同一个位置,则不需要打擂台,直接讲数据输入,并记录下标,如果不同,则建立左子树和右子树,随后将左子树和右子树的最强节点打擂台记录。

//a为原始数组,c储存原始数组下标,s储存胜者下标
void build(int l,int r,int rt)//l为左端点,r为右端点,rt为当前节点下标
{
    if(l==r)//如果两端重叠
    {
        cin>>a[l];//就剩一个不用打(总不能自己打自己)
        s[rt]=l;
        c[l]=rt;
        //记录
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    //建左右子树
    s[rt]=a[s[rt*2]]<a[s[rt*2+1]]?s[rt*2]:s[rt*2+1];//这里可以自行更改,本例使用的是求最小值,下面也一样
}

二,求a数组中的最小值

不断除以2,直到根节点,途中不断求最优解,即可得到最小值

void adjust(int rt)
{
    while(rt>1)
    {
        rt=rt/2;
        s[rt]=a[s[rt*2]]<a[s[rt*2+1]]?s[rt*2]:s[rt*2+1];//这里与建树函数的最后一句相同
    }
}

三,求a数组一段的最小值

与建树差不多的思路,也是不断分两段

void query(int l,int r,int ll,int rr,int rt)//ll和rr为我们要求的区间
{
    if(ll<=l && rr>=r) return s[rt];//区间包含则直接输出
    int mid=(l+r)/2
    int p1=0,p2=0;
    if(ll<=mid) p1=query(l,mid,ll,rr,rt*2);//左子树
    if(rr>mid) p2=query(mid+1,r,ll,rr,rt*2+1);//右子树
    return a[p1]<a[p2]?p1:p2;//打擂台
}
...
cout<<a[query(原数组起始坐标,原数组末尾坐标,区间左端编号,区间右端编号,根节点位置)];

胜者树,就这么简单



新鲜事 原文

终于摆脱树的噩梦了 胜者树,线段树,树状数组,最近公共祖先,树上倍增......学这些我还不如去学汇编!


新鲜事 原文

以下句子千万别倒着读 1.我是霸王 2.清晨我和猪上山 3.我的圆珠笔 4.我吃桶饭


新鲜事 原文

又是一年夏日,西瓜冰棍雪糕,空调连开一天,又交电费,竟然到了三千 往年夏天, 泳池里泡。 今年夏天, 空调不开。 冰棍雪糕, 化的贼快。 我有多热, 谁能知道!


新鲜事 原文

当你爸妈不让你玩游戏的时候,把这段话给他们看: 我的世界告诉我们:每一件事,只有你去试过才知道难不难 和平精英告诉我们:你不去拼搏,就没有赢的希望。 王者荣耀告诉我们:只有团队的人一起协作,才有可能战胜别人 皇室战争告诉我们:只有你足够强大,别人才不能打败你


新鲜事 原文

当你成绩不好的时候,把这段话给你爸妈看: 语文学不好正常,你骂人用得着修辞手法吗? 数学学不好正常,你上街买菜用得着函数吗? 英语学不好正常,咱们是中国人嘛。 物理学不好正常,你打架还需要懂力学定律吗? 生物学不好正常,你杀鸡还要研究鸡的身体构造吗? 化学学不好正常,你喝气泡水用得着研究哪来的气泡吗? 地理学不好正常,你没事干去种地啊。 体育学不好正常,你买菜还需要跑八百米吗? 美术学不好正常,你家画壁画还要你自己来吗? 音乐学不好正常,你要去街头学盲人卖艺吗? OI学不好正常,你长大要当计算机吗?